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.

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

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

Single-batch GPU pairwise Manhattan distance

Description

Uses 3D tensors: repeat s1 along dim2, repeat s2 along dim1, then sub -> abs -> sum_rows. Result shape is (1, N1, N2) which gives the N1 x N2 distance matrix.

Usage

.manhattan_distance_matrix_gpu_batch(states1, states2)

Arguments

Value

Numeric matrix (N1 x N2)

Setup GPU backend (internal)

Description

Checks if GPU is available via cayley_gpu_available() and initializes if so.

Usage

.setup_gpu()

Value

Logical, TRUE if GPU is ready

Add State Keys to Data Frame

Description

Computes paste-based state keys for V-columns and adds a state_key column. If keys already exist, only computes for new rows.

Usage

add_state_keys(states_df, new_states, v_cols)

Arguments

Value

Data frame with state_key column

Analyze Top Operation Combinations

Description

For each combination in a data frame of top results, runs a full cycle analysis and collects all states with their celestial coordinates into a single data frame.

Usage

analyze_top_combinations(top_combos, start_state, k)

Arguments

Value

Data frame with columns V1..Vn, operation, step, combo_number, nL, nR, nX, theta, phi, omega_conformal

Examples

combos <- data.frame(combination = c("13", "23"), stringsAsFactors = FALSE)
# result <- analyze_top_combinations(combos, 1:10, k = 4)

Apply Sequence of Operations

Description

Applies a sequence of shift and reverse operations to a permutation state. Operations can be specified as "1"/"L" (shift left), "2"/"R" (shift right), or "3"/"X" (reverse prefix). Tracks celestial coordinates.

Arguments

Value

List with components:

Examples

result <- apply_operations(1:10, c("1", "3", "2"), k = 4)
result$state

# Using letter codes
result <- apply_operations(1:20, c("L", "X", "R"), k = 4)
result$state

Apply operations to batch of states on GPU

Description

Applies a sequence of permutation operations to multiple states simultaneously using matrix multiplication on the Vulkan backend.

Usage

apply_operations_batch_gpu(states_matrix, operations, k)

Arguments

Value

Numeric matrix (nrow x n) with transformed states

Examples

if (cayley_gpu_available()) {
  mat <- matrix(c(1,2,3,4,5, 5,4,3,2,1), nrow = 2, byrow = TRUE)
  result <- apply_operations_batch_gpu(mat, c("1", "3"), k = 4)
}

Bidirectional BFS Shortest Path

Description

Finds the shortest path between two permutation states using bidirectional breadth-first search. Expands from both the start and goal states simultaneously, meeting in the middle.

Usage

bidirectional_bfs(n, state1, state2, max_level, moves, k)

Arguments

Value

Character vector of operations forming the shortest path, or NULL if no path found within max_level

Examples

# Find path between two small states
path <- bidirectional_bfs(5, 1:5, c(2, 3, 4, 5, 1), max_level = 5,
                          moves = c("1", "2", "3"), k = 3)
path

Breakpoint Distance Between Two States

Description

Counts the number of positions where consecutive elements differ by more than 1 (breakpoints). Particularly effective for TopSpin puzzles where operations shift blocks and flip prefixes.

Usage

breakpoint_distance(start_state, target_state)

Arguments

Value

Integer, the number of breakpoints

Examples

breakpoint_distance(1:5, 5:1)
breakpoint_distance(1:5, 1:5)

Build permutation matrix for a single operation

Description

Creates an n x n permutation matrix (column-major, F32) that represents a single operation. When multiplied: new_state = state %*% P.

Usage

build_permutation_matrix(op, n, k)

Arguments

Value

Numeric vector of length n*n (column-major permutation matrix)

Angular Distance Between Two Celestial Points

Description

Computes the angular distance on the celestial sphere between two points given as coordinate lists (each with a z component).

Usage

calculate_angular_distance_z(result1, result2)

Arguments

Value

Numeric, angular distance in radians

Examples

c1 <- convert_LRX_to_celestial(10, 5, 3)
c2 <- convert_LRX_to_celestial(1, 1, 2)
calculate_angular_distance_z(c1, c2)

Calculate Manhattan Distances for All States

Description

Computes the Manhattan distance from a reference state to every row in a table of reachable states, adds a difference column, and sorts by it.

Usage

calculate_differences(
  start_state,
  reachable_states_start,
  method = "manhattan",
  use_gpu = FALSE
)

Arguments

Value

Data frame sorted by difference (ascending)

Examples

df <- data.frame(V1 = c(1, 2), V2 = c(2, 1))
calculate_differences(c(1, 2), df)

Calculate Manhattan Distances on GPU

Description

Computes Manhattan distance from a reference state to each row of a matrix using ggml Vulkan backend: sub -> abs -> sum_rows.

Usage

calculate_differences_gpu(start_state, states_matrix)

Arguments

Value

Numeric vector of Manhattan distances (length nrow)

Midpoint Between Two Celestial Coordinates

Description

Computes the midpoint on the celestial sphere between two coordinate sets by averaging Cartesian unit-sphere positions and re-projecting.

Usage

calculate_midpoint_z(coords1, coords2)

Arguments

Value

List with theta, phi, z, z_bar, omega_conformal, nL, nR, nX

Examples

c1 <- convert_LRX_to_celestial(10, 5, 3)
c2 <- convert_LRX_to_celestial(1, 1, 2)
mid <- calculate_midpoint_z(c1, c2)
mid$theta

Check if GPU acceleration is available

Description

Checks whether ggmlR is installed and Vulkan GPU is present.

Usage

cayley_gpu_available()

Value

Logical

Examples

cayley_gpu_available()

Free GPU backend resources

Description

Free GPU backend resources

Usage

cayley_gpu_free()

Value

Invisible NULL

Initialize GPU backend

Description

Lazily initializes the Vulkan backend. Safe to call multiple times.

Usage

cayley_gpu_init(device = 0L, force = FALSE)

Arguments

Value

Invisible backend pointer

Examples

if (cayley_gpu_available()) {
  cayley_gpu_init()
}

Get GPU status information

Description

Get GPU status information

Usage

cayley_gpu_status()

Value

List with availability, device info, and backend status

Examples

cayley_gpu_status()

Find Duplicate States Between Two Tables

Description

Identifies states that appear in both tables by comparing V-columns. Used for finding intersections between forward and backward searches.

Usage

check_duplicates(df1, df2)

Arguments

Value

Data frame of duplicate states with a source column, or NULL if none

Examples

df1 <- data.frame(V1 = c(1, 2), V2 = c(2, 1))
df2 <- data.frame(V1 = c(2, 3), V2 = c(1, 2))
check_duplicates(df1, df2)

Compose permutation matrices for a sequence of operations

Description

Multiplies individual permutation matrices into one combined matrix.

Usage

compose_permutation_matrix(operations, n, k)

Arguments

Value

Numeric vector of length n*n (combined permutation matrix, column-major)

Convert LRX Counts to Celestial Coordinates

Description

Maps cumulative operation counts (Left, Right, Reverse) to spherical celestial coordinates via stereographic projection.

Usage

convert_LRX_to_celestial(nL, nR, nX)

Arguments

Value

List with components:

Examples

coords <- convert_LRX_to_celestial(10, 5, 3)
coords$theta
coords$phi

Convert String to Integer Vector of Digits

Description

Parses a string of digits or space-separated numbers into an integer vector. Useful for converting operation sequences or state representations.

Usage

convert_digits(s)

Arguments

Value

Integer vector of parsed numbers

Examples

convert_digits("123")
convert_digits("1 5 4 3 2")
convert_digits("10 11 12 13")

Create Hash Index from State Keys

Description

Builds a hash environment mapping state_key strings to row indices for fast lookup.

Usage

create_hash_index(states_df)

Arguments

Value

Environment (hash table) mapping keys to integer vectors of row indices

Filter Middle States

Description

Removes the first and last steps from each combo within cycle data, keeping only middle states.

Usage

filter_middle_states(data, skip_first = 2, skip_last = 2)

Arguments

Value

Data frame with filtered states

Find Best Match State

Description

Finds the state in a table that has the minimum Manhattan distance to a target state. If multiple states tie, selects the one with the smallest step number.

Usage

find_best_match_state(
  target_state,
  reachable_states,
  method = "manhattan",
  use_gpu = FALSE
)

Arguments

Value

Single-row data frame of the best matching state

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. Uses C++ with OpenMP for parallel evaluation of combinations.

Usage

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

Arguments

Value

Data frame with columns:

Examples

best <- find_best_random_combinations(
  moves = c("1", "2", "3"),
  combo_length = 10,
  n_samples = 50,
  n_top = 5,
  start_state = 1:10,
  k = 4
)
print(best)

Find Closest State to Target Coordinates

Description

Searches a table of reachable states for the state whose celestial coordinates are closest to a target coordinate set.

Usage

find_closest_to_coords(reachable_states, target_coords, v_cols)

Arguments

Value

Single-row data frame of the closest state (with angular_distance column added)

Examples

# Typically used with output from get_reachable_states
# find_closest_to_coords(states_df, target_coords, paste0("V", 1:n))

Find a State in Reachable States Table

Description

Searches for a specific permutation state in a reachable states table and returns the first matching row with metadata.

Usage

find_combination_in_states(reachable_states_start, search_state)

Arguments

Value

Data frame row with state and metadata columns, or NULL if not found

Examples

df <- data.frame(V1 = c(1, 2), V2 = c(2, 1), operation = c("1", "2"),
                 step = c(1, 2), combo_number = c(1, 1))
find_combination_in_states(df, c(2, 1))

Find Path via BFS Highways

Description

Builds BFS highway trees from start and final states, finds the closest pair of hub states (one from each highway), then uses find_path_iterative to connect them. Assembles the full path: bfs(start -> hub_s) + iterative(hub_s -> hub_f) + inverted_bfs(final -> hub_f)

Usage

find_path_bfs(
  start_state,
  final_state,
  k,
  bfs_levels = 500L,
  bfs_n_hubs = 7L,
  bfs_n_random = 3L,
  distance_method = "manhattan",
  verbose = TRUE,
  ...
)

Arguments

Value

List with path, found, cycles, bfs_info

Iterative Path Finder Between Permutation States

Description

Finds a path between two permutation states using iterative cycle expansion. Generates random operation sequences, analyzes their cycles, and looks for intersections between forward (from start) and backward (from final) state sets. Uses bridge states to progressively narrow the search space.

Usage

find_path_iterative(
  start_state,
  final_state,
  k,
  moves = c("1", "2", "3"),
  combo_length = 20,
  n_samples = 200,
  n_top = 10,
  max_iterations = 10,
  potc = 1,
  ptr = 10,
  opd = FALSE,
  reuse_combos = FALSE,
  distance_method = "manhattan",
  verbose = TRUE
)

Arguments

Value

List containing:

Examples

# Small example
set.seed(42)
start <- 1:6
final <- c(3L, 1L, 2L, 6L, 4L, 5L)
# result <- find_path_iterative(start, final, k = 3, max_iterations = 5)

Generate Reachable Random State

Description

Generates a random state reachable from 1:n by applying random operations (L, R, X). Guarantees the result is in the same connected component as the starting state.

Usage

generate_state(n, k = n, n_moves = 25L, moves = c("1", "2", "3"))

Arguments

Value

Integer vector representing a reachable permutation state

Examples

set.seed(42)
generate_state(10, k = 4)
generate_state(10, k = 4, n_moves = 100)

Generate Data Frame of Unique Random States

Description

Generates a data frame with unique random permutation states.

Usage

generate_unique_states_df(n, n_rows)

Arguments

Value

Data frame with n_rows rows and columns V1, V2, ..., Vn

Examples

set.seed(42)
df <- generate_unique_states_df(5, 10)
head(df)

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, the cycle structure, and celestial LRX coordinates.

Usage

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

Arguments

Value

List containing:

Examples

result <- get_reachable_states(1:10, c("1", "3"), k = 4)
writeLines(result$cycle_info)

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. Implemented in C++ for performance.

Usage

get_reachable_states_light(start_state, allowed_positions, k)

Arguments

Value

List containing:

Examples

result <- get_reachable_states_light(1:10, c("1", "3"), k = 4)
cat("Cycle length:", result$total_moves, "\n")
cat("Unique states:", result$unique_states_count, "\n")

Invert a Path of Operations

Description

Reverses and inverts a sequence of operations. "1" (shift left) becomes "2" (shift right) and vice versa. "3" (reverse) stays the same.

Usage

invert_path(path)

Arguments

Value

Character vector of inverted operations in reverse order

Examples

invert_path(c("1", "3", "2"))
invert_path(c("1", "1", "3"))

Manhattan Distance Between Two States

Description

Computes the sum of absolute differences between corresponding elements of two permutation states.

Usage

manhattan_distance(start_state, target_state)

Arguments

Value

Numeric, the Manhattan distance

Examples

manhattan_distance(1:5, 5:1)
manhattan_distance(1:5, 1:5)

Compute Pairwise Manhattan Distance Matrix on GPU

Description

Computes all pairwise Manhattan distances between two sets of states. Returns an N1 x N2 matrix where entry (i,j) is the Manhattan distance between row i of states1 and row j of states2.

Usage

manhattan_distance_matrix_gpu(states1, states2, batch_size = 256L)

Arguments

Details

For large matrices, computation is batched over columns of the result to avoid GPU memory overflow.

Value

Numeric matrix (N1 x N2) of Manhattan distances

Examples

if (cayley_gpu_available()) {
  s1 <- matrix(c(1,2,3,4,5, 5,4,3,2,1), nrow = 2, byrow = TRUE)
  s2 <- matrix(c(3,3,3,3,3, 1,1,1,1,1), nrow = 2, byrow = TRUE)
  manhattan_distance_matrix_gpu(s1, s2)
}

Process Final-type Intersection

Description

Handles an intersection where the meeting state equals the original final state. Reconstructs path through the start (forward) search tree.

Usage

process_final_intersection(
  intersection_state,
  reachable_states_start,
  bridge_states_start,
  start_index,
  v_cols
)

Arguments

Value

List with path and info, or NULL

Process Intermediate Intersection

Description

Handles a general intersection found in both forward and backward search trees. Combines paths from both directions.

Usage

process_intermediate_intersection(
  intersection_state,
  reachable_states_start,
  reachable_states_final,
  bridge_states_start,
  bridge_states_final,
  start_index,
  final_index,
  v_cols
)

Arguments

Value

List with path and info, or NULL

Process Start-type Intersection

Description

Handles an intersection where the meeting state equals the original start state. Reconstructs path through the final (backward) search tree.

Usage

process_start_intersection(
  intersection_state,
  reachable_states_final,
  bridge_states_final,
  final_index,
  v_cols
)

Arguments

Value

List with path and info, or NULL

Reconstruct path from sparse BFS result

Description

Traces back from target_key to the root (start state) using the parent_key/child_key edges in the BFS result.

Usage

reconstruct_bfs_path(bfs_result, target_key)

Arguments

Value

Character vector of operations from start to target

Reconstruct Full Path Through Cycle Chain

Description

Traces back through a chain of cycles to build the full operation path from the initial state to a target state.

Usage

reconstruct_full_path(
  reachable_states,
  start_state,
  target_state,
  target_cycle,
  target_combo,
  v_cols
)

Arguments

Value

Character vector of operations, or NULL on error

Reverse First k Elements (with Coordinates)

Description

Reverses the first k elements of the state vector (turnstile operation). Tracks celestial coordinates (LRX momentum).

Arguments

Value

List with components:

Examples

result <- reverse_prefix(1:10, k = 4)
result$state

Reverse First k Elements (Simple)

Description

Simple prefix reversal without coordinate tracking.

Arguments

Value

Integer vector with first k elements reversed

Examples

reverse_prefix_simple(1:10, k = 4)

Save Bridge States to CSV

Description

Writes a list of bridge states (each with state and cycle fields) to a CSV file.

Usage

save_bridge_states(bridge_states, filename)

Arguments

Value

Invisible NULL. Side effect: writes a CSV file.

Examples

bs <- list(
  list(state = 1:5, cycle = 0),
  list(state = c(2, 1, 3, 4, 5), cycle = 1)
)
# save_bridge_states(bs, tempfile(fileext = ".csv"))

Select New Bridge State

Description

Selects a new state from candidate states that is close to an opposite state (by Manhattan distance). Randomly picks from the top 10 closest.

Usage

select_new_state(target_all, opposite_state, method = "manhattan")

Arguments

Value

Integer vector of the selected state

Select Unique States by V-columns

Description

Removes duplicate rows based on state columns (V1, V2, ..., Vn).

Usage

select_unique(df)

Arguments

Value

Data frame with unique states

Examples

df <- data.frame(V1 = c(1, 1, 2), V2 = c(2, 2, 1), op = c("a", "b", "c"))
select_unique(df)

Shift State Left (with Coordinates)

Description

Performs a cyclic left shift on the state vector, moving the first element to the end. Tracks celestial coordinates (LRX momentum).

Arguments

Value

List with components:

Examples

result <- shift_left(1:5)
result$state
result$coords

# Chain operations using coords
r1 <- shift_left(1:5)
r2 <- shift_left(r1$state, r1$coords)
r2$coords$nL

Shift State Left (Simple)

Description

Simple cyclic left shift without coordinate tracking.

Arguments

Value

Integer vector with elements shifted left by one position

Examples

shift_left_simple(1:5)

Shift State Right (with Coordinates)

Description

Performs a cyclic right shift on the state vector, moving the last element to the front. Tracks celestial coordinates (LRX momentum).

Arguments

Value

List with components:

Examples

result <- shift_right(1:5)
result$state

Shift State Right (Simple)

Description

Simple cyclic right shift without coordinate tracking.

Arguments

Value

Integer vector with elements shifted right by one position

Examples

shift_right_simple(1:5)

Shorten Path via Greedy BFS Hopping

Description

Shorten Path via Greedy BFS Hopping

Usage

short_path_bfs(path, start_state, k, n_hits = 5L)

Arguments

Value

List with path (shortened), original_length, new_length, savings

Simplify Operation Path

Description

Removes redundant operations from a path: cancels inverse pairs ("1"+"2", "3"+"3"), reduces chains of shifts modulo n, and simplifies blocks between reverses.

Usage

short_position(allowed_positions, n)

Arguments

Value

Character vector of simplified operations

Examples

short_position(c("1", "2"), n = 5)
short_position(c("3", "3"), n = 5)
short_position(c("1", "1", "1", "1", "1"), n = 5)

Sparse BFS with Look-ahead and Hybrid Selection

Description

Sparse BFS with Look-ahead and Hybrid Selection

Usage

sparse_bfs(start_state, k, n_hubs = 7L, n_random = 3L, max_levels = 1000L)

Arguments

Value

data.frame with columns: parent_key, child_key, operation, level

Validate and Simplify a Path

Description

Verifies that a candidate path correctly transforms start_state into final_state, then attempts to simplify it. Returns the simplified path if it remains valid, otherwise the original.

Usage

validate_and_simplify_path(path_candidate, start_state, final_state, k)

Arguments

Value

List with components:

Examples

res <- validate_and_simplify_path(c("1", "3"), 1:5, c(5, 2, 3, 4, 1), k = 2)
res$valid