cayleyR is an R package for analyzing Cayley graphs of permutation groups, with a focus on the TopSpin puzzle and similar combinatorial problems. The package implements algorithms for cycle detection, state space exploration, and finding optimal operation sequences in permutation groups generated by shift and reverse operations.
-
Basic permutation operations: cyclic left/right shifts, prefix reversal
-
Cycle analysis: find cycles in Cayley graphs with detailed information about visited states
-
Sequence optimization: search for operation sequences that produce maximum cycle length
-
Fast processing: lightweight version for batch testing of combinations
shift_left(state) — performs a cyclic left shift, moving the first element of the vector to the end.
shift_right(state) — performs a cyclic right shift, moving the last element of the vector to the beginning.
reverse_prefix(state, k) — reverses the order of the first k elements of the state vector (the “turnstile” operation in TopSpin).
apply_operations(state, operations, k) — sequentially applies a set of operations to the state. Operations are specified by symbols: “L”/“1” (left), “R”/“2” (right), “X”/“3” (reverse).
get_reachable_states(start_state, allowed_positions, k) — finds the complete cycle in the Cayley graph for a given operation sequence. Returns all visited states, a data frame with the trajectory, and cycle statistics.
get_reachable_states_light(start_state, allowed_positions, k) — lightweight version of the cycle search function. Returns only cycle length and the number of unique states without storing all intermediate states. Used for fast testing of many sequences.
find_best_random_combinations(moves, combo_length, n_samples, n_top, start_state, k) — generates random operation sequences of a given length and finds those that produce maximum cycle length. Returns the top-N best combinations with their characteristics.
The package can be useful for:
-
Investigating mathematical properties of permutation puzzles
-
Analyzing Cayley graphs and their structure
-
Finding optimal algorithms for solving combinatorial problems
-
Educational purposes in group theory and combinatorics
The package uses:
- digest — for efficient state hashing during cycle search