Permutation Groups

Two built-in puzzles

tg <- topspin_group(8, k = 4, moves = c("L", "R", "X"))
tg
#> <perm_group> topspin(n=8, k=4)
#>   state length: 8
#>   moves (3): L R X

cg <- cube_group(3)
cg
#> <perm_group> cube3x3x3
#>   state length: 54
#>   moves (18): U U' R R' F F' D D' L L' B B' M M' E E' S S'

A TopSpin ring of 8 tiles has three moves. X reverses the first k = 4 tiles, and the group fixes k when you build it. A 3x3x3 cube has 54 stickers and 18 quarter turns, slices included.

TopSpin’s moves are named "1", "2", "3" by default. Pass moves = c("L", "R", "X") if you want to write words with letters, as in this vignette.

Applying moves

A state is an integer vector, and the solved state is 1:n. A word can be a vector of move names or one string with spaces:

group_apply(tg, group_identity(tg), "L L X")
#> [1] 6 5 4 3 7 8 1 2

s <- group_apply(cg, group_identity(cg), "R U R' U'")
sum(s != group_identity(cg))   # stickers out of place
#> [1] 18

group_inverse_seq() writes the word that undoes a given one. You never have to declare inverses: the group works them out from the permutations.

undo <- group_inverse_seq(cg, "R U R' U'")
undo
#> [1] "U"  "R"  "U'" "R'"
identical(group_apply(cg, s, undo), group_identity(cg))
#> [1] TRUE

Order of a word

How many times must a word be repeated to return to the start? The answer does not depend on the starting state, and group_order() computes it:

group_order(cg, "R")            # a quarter turn: 4
#> [1] 4
group_order(cg, "R U R' U'")    # the "sexy move": 6
#> [1] 6
group_order(cg, "R U")          # 105
#> [1] 105

group_order(tg, "L")            # going once round the ring
#> [1] 8

Cycles like these drive the iterative solver: one word repeated many times sweeps through a long cycle of states.

A puzzle of your own

perm_group() builds a group from a named list of permutations. Each permutation is read as new[i] <- state[perm[i]], i.e. position i takes its value from position perm[i]. No C++ is needed.

Here is a toy puzzle on five points. It has a rotation a, its inverse a', and a swap of the first two points b:

toy <- perm_group(list(
  a    = c(2L, 3L, 4L, 5L, 1L),
  "a'" = c(5L, 1L, 2L, 3L, 4L),
  b    = c(2L, 1L, 3L, 4L, 5L)
), name = "toy")
toy
#> <perm_group> toy
#>   state length: 5
#>   moves (3): a a' b

group_apply(toy, 1:5, "a a b")
#> [1] 4 3 5 1 2
group_inverse_seq(toy, "a a b")
#> [1] "b"  "a'" "a'"
group_order(toy, "a b")
#> [1] 4

Everything above works on this group straight away, and so does every function in the package that takes group =.

Random states

generate_state() takes a group too. Given one, it only returns states the puzzle can actually reach, rather than an arbitrary permutation of 54 numbers:

scrambled <- generate_state(group = cg, n_moves = 20)
length(scrambled)
#> [1] 54

Subgroups

You can build a cube group that uses only some of the moves. Here the middle slice turns alone:

m_only <- cube_group(3, moves = c("M", "M'"))
m_only
#> <perm_group> cube3x3x3
#>   state length: 54
#>   moves (2): M M'
generate_state(group = m_only, n_moves = 5)
#>  [1]  1 53  3  4 50  6  7 47  9 10 11 12 13 14 15 16 17 18 19  2 21 22  5 24 25
#> [26]  8 27 28 20 30 31 23 33 34 26 36 37 38 39 40 41 42 43 44 45 46 35 48 49 32
#> [51] 51 52 29 54

Old calls still work

Without a group, n, k and moves still describe TopSpin, exactly as before, so existing code does not need to change:

generate_state(10, k = 4, n_moves = 100)
#>  [1]  9 10  8  3  2  5  4  1  6  7