Learn R Programming
cayleyR (version 0.2.1)

cayleyR-package: 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 C++ implementations of core operations via Rcpp, cycle detection, state space exploration, bidirectional BFS pathfinding, and finding optimal operation sequences in permutation groups generated by shift and reverse operations. Optional GPU acceleration via ggmlR Vulkan backend for batch distance calculations and parallel state transformations.

Arguments

Author

Yuri Baramykov lbsbmsu@mail.ru

Details

Main 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

Main Functions

Basic Operations (C++):

  • shift_left() / shift_right() - Cyclic shifts with coordinate tracking

  • shift_left_simple() / shift_right_simple() - Simple cyclic shifts (no coords)

  • reverse_prefix() / reverse_prefix_simple() - Reverse first k elements

  • apply_operations() - Apply sequence of operations

Analysis Tools:

  • 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

GPU (optional, requires ggmlR):

  • cayley_gpu_available() / cayley_gpu_init() / cayley_gpu_status() - GPU management

  • calculate_differences() with use_gpu = TRUE - Manhattan distance on GPU

  • apply_operations_batch_gpu() - Batch operations via matrix multiplication

  • manhattan_distance_matrix_gpu() - Pairwise distance matrix

Utilities:

  • convert_digits() - Parse operation strings

  • generate_state() / generate_unique_states_df() - Random state generation

  • manhattan_distance() - Distance between states

  • convert_LRX_to_celestial() - Map operations to celestial coordinates

References

See Also

Useful links: