Cayley Graph Analysis for Permutation Puzzles.

cayleyR

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, bidirectional BFS pathfinding, and finding optimal operation sequences in permutation groups generated by shift and reverse operations.

Features

• Basic permutation operations (C++): 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
• Bidirectional BFS: find shortest paths between permutation states
• Iterative solver: find paths between arbitrary states via iterative cycle expansion
• Celestial coordinates: map LRX operation counts to spherical coordinates
• GPU acceleration (optional): Vulkan-based batch computations via ggmlR
• Fast processing: lightweight version for batch testing of combinations

Installation

# From GitHub:
devtools::install_github("Zabis13/cayleyR")

Quick start

library(cayleyR)

# Basic operations
state <- 1:10
shift_left(state)              # cyclic left shift
shift_right(state)             # cyclic right shift
reverse_prefix(state, k = 4)  # reverse first 4 elements

# Apply a sequence of operations
apply_operations(state, c("L", "R", "X"), k = 4)

# Find cycle length for an operation sequence
get_reachable_states_light(state, c("1", "3"), k = 4)

# Find best random operation sequences
find_best_random_combinations(
  moves = c("1", "2", "3"),
  combo_length = 10,
  n_samples = 50,
  n_top = 5,
  start_state = 1:10,
  k = 4
)

# Bidirectional BFS shortest path
bidirectional_bfs(start = 1:10, target = c(2:10, 1), k = 4)

GPU acceleration

Optional GPU support via the ggmlR package (Vulkan backend). Install ggmlR separately; cayleyR works without it (CPU fallback).

# Check GPU availability
cayley_gpu_available()
cayley_gpu_status()

# Manhattan distance (GPU vs CPU)
calculate_differences(start_state, states_df, use_gpu = TRUE)

# Batch apply operations to many states at once
apply_operations_batch_gpu(states_matrix, c("1", "3", "2"), k = 4)

# Pairwise distance matrix
manhattan_distance_matrix_gpu(states1, states2)

Package functions

Basic Operations (C++):

• shift_left() / shift_right() — cyclic shifts with coordinate tracking
• shift_left_simple() / shift_right_simple() — simple cyclic shifts
• reverse_prefix() / reverse_prefix_simple() — reverse first k elements
• apply_operations() — apply sequence of operations

Analysis:

• get_reachable_states() — full cycle analysis with state tracking
• get_reachable_states_light() — lightweight cycle detection
• find_best_random_combinations() — find best random sequences
• analyze_top_combinations() — analyze top operation sequences

Pathfinding:

• bidirectional_bfs() — bidirectional BFS shortest path
• find_path_iterative() — iterative path solver via cycle expansion
• find_path_bfs() — find path via BFS highways + iterative connector
• short_path_bfs() — shorten existing path via greedy BFS hopping
• sparse_bfs() — sparse BFS with hybrid hub/random selection
• reconstruct_bfs_path() — reconstruct path from sparse BFS result
• validate_and_simplify_path() — validate and simplify operation path
• invert_path() — reverse an operation path

GPU (optional, requires ggmlR):

• cayley_gpu_available() / cayley_gpu_init() / cayley_gpu_status() / cayley_gpu_free() — GPU management
• calculate_differences(..., use_gpu = TRUE) — Manhattan distance on GPU
• apply_operations_batch_gpu() — batch operations via matrix multiplication
• manhattan_distance_matrix_gpu() — pairwise distance matrix

Distance Metrics:

• manhattan_distance() — Manhattan distance between states
• breakpoint_distance() — breakpoint distance between states
• calculate_differences() — compute distances for all states in a table
• find_best_match_state() — find closest state by distance

Celestial Coordinates:

• convert_LRX_to_celestial() — map LRX operation counts to spherical coordinates
• calculate_angular_distance_z() — angular distance between two coordinate sets
• calculate_midpoint_z() — midpoint between two coordinate sets
• find_closest_to_coords() — find state closest to target coordinates

State Utilities:

• generate_state() / generate_unique_states_df() — random state generation
• select_unique() — deduplicate states by V-columns
• check_duplicates() — find states present in two tables
• find_combination_in_states() — find a specific state in results
• save_bridge_states() — save bridge states to CSV
• short_position() — short string representation of a state
• convert_digits() — parse operation strings

Dependencies

• Rcpp — C++ implementations of core operations (required)
• data.table (optional) — faster rbindlist when available
• ggmlR (optional) — GPU acceleration via Vulkan

License

MIT.