cayleyR: Cayley Graph Analysis for Permutation Puzzles

Description

Implements algorithms for analyzing Cayley graphs of permutation groups, with a focus on the TopSpin puzzle and similar combinatorial problems. Provides methods for cycle detection, state space exploration, and finding optimal operation sequences in permutation groups generated by shift and reverse operations.

Details

Main Features

• Basic permutation operations: cyclic left/right shifts, prefix reversal

• Cycle analysis: find cycles in Cayley graphs with detailed state information

• Sequence optimization: search for operation sequences with maximum cycle length

• Fast processing: lightweight version for batch testing of combinations

Main Functions

Basic Operations:

• shift_left - Cyclic left shift

• shift_right - Cyclic right shift

• reverse_prefix - Reverse first k elements (turnstile operation)

Analysis Tools:

• apply_operations - Apply sequence of operations

• get_reachable_states - Full cycle analysis with state tracking

• get_reachable_states_light - Lightweight cycle detection

Optimization:

• find_best_random_combinations - Find best random sequences

After installation from GitHub, visit: https://github.com/Zabis13/cayleyR

Getting Started

library(cayleyR)

# Basic operations
shift_left(1:5)
reverse_prefix(1:10, k = 4)

# Cycle analysis for TopSpin 20-4
result <- get_reachable_states(
  start_state = 1:20,
  allowed_positions = c("L", "X"),
  k = 4
)

Author(s)

Yuri Baramykov lbsbmsu@mail.ru

References

• TopSpin puzzle: https://www.jaapsch.net/puzzles/topspin.htm

• Cayley graphs: https://en.wikipedia.org/wiki/Cayley_graph

See Also

Useful links:

• https://github.com/Zabis13/cayleyR

• Report bugs at https://github.com/Zabis13/cayleyR/issues

Apply Operation Sequence

Description

Applies a sequence of operations to a permutation state. Operations can be specified as "L"/"1" (shift left), "R"/"2" (shift right), or "X"/"3" (reverse first k elements).

Usage

apply_operations(state, operations, k)

Arguments

Value

Integer vector representing the state after all operations

Examples

# Basic usage with numeric codes
apply_operations(1:5, c("1", "3"), k = 3)

# TopSpin puzzle example
start_state <- 1:20
operations <- c("1", "3", "2")  # Left, Reverse(4), Right
result <- apply_operations(start_state, operations, k = 4)
print(result)

# Using letter codes
apply_operations(1:5, c("L", "X", "R"), k = 3)

Find Best Random Operation Sequences

Description

Generates random sequences of operations and evaluates their cycle lengths to find sequences that produce the longest cycles in the Cayley graph. Useful for discovering interesting operation sequences in permutation puzzles.

Usage

find_best_random_combinations(
  moves,
  combo_length,
  n_samples,
  n_top,
  start_state,
  k
)

Arguments

Details

The returned data frame reachable_states_df has the following structure:

step | state           | operation
-----|-----------------|----------
1    | 1 2 3 4 5...    | 1         <- INITIAL, operation="1" (next operation)
2    | 2 3 4 5 6...    | 1         <- after applying op1 from row 1
3    | 3 4 5 6 7...    | 2         <- after applying op1 from row 2
4    | 4 5 6 7 8...    | 3         <- after applying op2 from row 3
5    | 5 6 7 8 9...    | 1         <- after applying op3 from row 4
...
20   | 20 1 2 3 4...   | 1         <- after applying all ops from rows 1-19
NA   | 1 2 3 4 5...    | NA        <- after applying op1 from row 20 = initial

Value

Data frame with columns:

Examples

# Find top 10 sequences from 100 random samples
best <- find_best_random_combinations(
  moves = c("1", "2", "3"),
  combo_length = 10,
  n_samples = 100,
  n_top = 10,
  start_state = 1:10,
  k = 4
)
print(best)

# Quick search with letter codes
top5 <- find_best_random_combinations(
  moves = c("L", "R", "X"),
  combo_length = 5,
  n_samples = 100,
  n_top = 5,
  start_state = 1:10,
  k = 3
)
print(top5)

Find Cycle in Permutation Group

Description

Explores the Cayley graph starting from an initial state and applying a sequence of operations repeatedly until returning to the start state. Returns detailed information about all visited states and the cycle structure.

Usage

get_reachable_states(start_state, allowed_positions, k, verbose = FALSE)

Arguments

Value

List containing:

Examples

# Simple example with letter codes
result <- get_reachable_states(1:20, c("L", "X"), k = 4)
writeLines(result$cycle_info)

# Example with numeric codes
n <- 20
k <- 4
start_state <- 1:n
allowed_positions <- c("1", "3", "2")
result <- get_reachable_states(start_state, allowed_positions, k)
writeLines(result$cycle_info)
head(result$reachable_states_df)

Find Cycle Length (Lightweight Version)

Description

Fast version of cycle detection that only returns cycle length and unique state count without storing all intermediate states. Useful for testing many operation sequences efficiently.

Usage

get_reachable_states_light(start_state, allowed_positions, k)

Arguments

Value

List containing:

Examples

# Quick cycle length check
result <- get_reachable_states_light(1:20, c("L", "X", "L"), k = 4)
cat("Cycle length:", result$total_moves, "\n")
cat("Unique states:", result$unique_states_count, "\n")

# Compare multiple sequences
seq1 <- get_reachable_states_light(1:20, c("1", "3"), k = 4)
seq2 <- get_reachable_states_light(1:20, c("2", "3"), k = 4)
cat("Sequence 1 cycle:", seq1$total_moves, "\n")
cat("Sequence 2 cycle:", seq2$total_moves, "\n")

Reverse Prefix

Description

Reverses the first k elements of the state vector, analogous to the turnstile operation in the TopSpin puzzle.

Usage

reverse_prefix(state, k)

Arguments

Value

Integer vector with the first k elements reversed

Examples

# Basic example
reverse_prefix(1:10, 4)  # Returns c(4, 3, 2, 1, 5, 6, 7, 8, 9, 10)

# With variables
n <- 10
k <- 4
start_state <- 1:n
demo <- reverse_prefix(start_state, k)
print(demo)

Shift State Left

Description

Performs a cyclic left shift on the state vector, moving the first element to the end.

Usage

shift_left(state)

Arguments

Value

Integer vector with elements shifted left by one position

Examples

# Basic shift operation
shift_left(1:5)

# With variables
start_state <- 1:20
result <- shift_left(start_state)
print(result)

Shift State Right

Description

Performs a cyclic right shift on the state vector, moving the last element to the beginning.

Usage

shift_right(state)

Arguments

Value

Integer vector with elements shifted right by one position

Examples

# Simple example
shift_right(1:5)

# With variable assignment
start_state <- 1:20
result <- shift_right(start_state)
print(result)