| Title: | Cayley Graph Analysis for Permutation Puzzles |
|---|---|
| Description: | Implements algorithms for analyzing Cayley graphs of permutation groups for the TopSpin puzzle. Provides methods for cycle detection, state space exploration, bidirectional BFS pathfinding, and finding optimal operation sequences in permutation groups generated by shift and reverse operations. Includes C++ implementations of core operations via 'Rcpp' for performance, including a depth-limited BFS path shortener implemented entirely in C++. |
| Authors: | Yuri Baramykov [aut, cre] |
| Maintainer: | Yuri Baramykov <[email protected]> |
| License: | MIT + file LICENSE |
| Version: | 0.2.3 |
| Built: | 2026-05-29 19:29:24 UTC |
| Source: | https://github.com/zabis13/cayleyr |
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.
analyze_top_combinations(top_combos, start_state, k)analyze_top_combinations(top_combos, start_state, k)
top_combos |
Data frame or data.table with a |
start_state |
Integer vector, the initial permutation state |
k |
Integer, parameter for reverse operations |
Data frame with columns V1..Vn, operation, step, combo_number, nL, nR, nX, theta, phi, omega_conformal
combos <- data.frame(combination = c("13", "23"), stringsAsFactors = FALSE) # result <- analyze_top_combinations(combos, 1:10, k = 4)combos <- data.frame(combination = c("13", "23"), stringsAsFactors = FALSE) # result <- analyze_top_combinations(combos, 1:10, k = 4)
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.
state |
Integer vector representing the current permutation state |
operations |
Character vector of operations ("1"/"L", "2"/"R", "3"/"X") |
k |
Integer, parameter for reverse operations |
coords |
Optional list of current celestial coordinates. If NULL, starts from zero coordinates. |
List with components:
state |
Integer vector after all operations applied |
coords |
List of final celestial coordinates (nL, nR, nX, theta, phi, omega_conformal) |
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$stateresult <- 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
Applies a sequence of permutation operations to multiple states simultaneously using matrix multiplication on the Vulkan backend.
apply_operations_batch_gpu(states_matrix, operations, k)apply_operations_batch_gpu(states_matrix, operations, k)
states_matrix |
Numeric matrix (nrow x n), each row is a state |
operations |
Character vector of operation codes (e.g., c("L", "R", "X")) |
k |
Integer, parameter for reverse operations |
Numeric matrix (nrow x n) with transformed states
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) }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) }
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.
bidirectional_bfs(n, state1, state2, max_level, moves, k)bidirectional_bfs(n, state1, state2, max_level, moves, k)
n |
Integer, size of the permutation |
state1 |
Integer vector, start state |
state2 |
Integer vector, goal state |
max_level |
Integer, maximum BFS depth in each direction |
moves |
Character vector, allowed operations (e.g., c("1", "2", "3")) |
k |
Integer, parameter for reverse operations |
Character vector of operations forming the shortest path, or NULL if no path found within max_level
# 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# 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
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.
breakpoint_distance(start_state, target_state)breakpoint_distance(start_state, target_state)
start_state |
Integer vector, first state |
target_state |
Integer vector, second state |
Integer, the number of breakpoints
breakpoint_distance(1:5, 5:1) breakpoint_distance(1:5, 1:5)breakpoint_distance(1:5, 5:1) breakpoint_distance(1:5, 1:5)
Computes the angular distance on the celestial sphere between two points
given as coordinate lists (each with a z component).
calculate_angular_distance_z(result1, result2)calculate_angular_distance_z(result1, result2)
result1 |
List with component |
result2 |
List with component |
Numeric, angular distance in radians
c1 <- convert_LRX_to_celestial(10, 5, 3) c2 <- convert_LRX_to_celestial(1, 1, 2) calculate_angular_distance_z(c1, c2)c1 <- convert_LRX_to_celestial(10, 5, 3) c2 <- convert_LRX_to_celestial(1, 1, 2) calculate_angular_distance_z(c1, c2)
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.
calculate_differences( start_state, reachable_states_start, method = "manhattan", use_gpu = FALSE )calculate_differences( start_state, reachable_states_start, method = "manhattan", use_gpu = FALSE )
start_state |
Integer vector, the reference state |
reachable_states_start |
Data frame with V-columns |
method |
Character, distance method (currently only "manhattan") |
use_gpu |
Logical, use GPU acceleration via ggmlR if available (default FALSE) |
Data frame sorted by difference (ascending)
df <- data.frame(V1 = c(1, 2), V2 = c(2, 1)) calculate_differences(c(1, 2), df)df <- data.frame(V1 = c(1, 2), V2 = c(2, 1)) calculate_differences(c(1, 2), df)
Computes the midpoint on the celestial sphere between two coordinate sets by averaging Cartesian unit-sphere positions and re-projecting.
calculate_midpoint_z(coords1, coords2)calculate_midpoint_z(coords1, coords2)
coords1 |
List with theta, phi, omega_conformal (and optionally nL, nR, nX) |
coords2 |
List with theta, phi, omega_conformal (and optionally nL, nR, nX) |
List with theta, phi, z, z_bar, omega_conformal, nL, nR, nX
c1 <- convert_LRX_to_celestial(10, 5, 3) c2 <- convert_LRX_to_celestial(1, 1, 2) mid <- calculate_midpoint_z(c1, c2) mid$thetac1 <- convert_LRX_to_celestial(10, 5, 3) c2 <- convert_LRX_to_celestial(1, 1, 2) mid <- calculate_midpoint_z(c1, c2) mid$theta
Checks whether ggmlR is installed and Vulkan GPU is present.
cayley_gpu_available()cayley_gpu_available()
Logical
cayley_gpu_available()cayley_gpu_available()
Free GPU backend resources
cayley_gpu_free()cayley_gpu_free()
Invisible NULL
Lazily initializes the Vulkan backend. Safe to call multiple times.
cayley_gpu_init(device = 0L, force = FALSE)cayley_gpu_init(device = 0L, force = FALSE)
device |
Integer, Vulkan device index (0-based) |
force |
Logical, force re-initialization |
Invisible backend pointer
if (cayley_gpu_available()) { cayley_gpu_init() }if (cayley_gpu_available()) { cayley_gpu_init() }
Get GPU status information
cayley_gpu_status()cayley_gpu_status()
List with availability, device info, and backend status
cayley_gpu_status()cayley_gpu_status()
Identifies states that appear in both tables by comparing V-columns. Used for finding intersections between forward and backward searches.
check_duplicates(df1, df2)check_duplicates(df1, df2)
df1 |
Data frame (first set of states) |
df2 |
Data frame (second set of states) |
Data frame of duplicate states with a source column, or NULL if none
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)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)
Parses a string of digits or space-separated numbers into an integer vector. Useful for converting operation sequences or state representations.
convert_digits(s)convert_digits(s)
s |
Character string. Either a string of single digits (e.g., "123") or space-separated numbers (e.g., "1 2 3" or "10 11 12"). |
Integer vector of parsed numbers
convert_digits("123") convert_digits("1 5 4 3 2") convert_digits("10 11 12 13")convert_digits("123") convert_digits("1 5 4 3 2") convert_digits("10 11 12 13")
Maps cumulative operation counts (Left, Right, Reverse) to spherical celestial coordinates via stereographic projection.
convert_LRX_to_celestial(nL, nR, nX)convert_LRX_to_celestial(nL, nR, nX)
nL |
Integer, cumulative count of left shift operations |
nR |
Integer, cumulative count of right shift operations |
nX |
Integer, cumulative count of reverse operations |
List with components:
z |
Complex number, stereographic projection coordinate |
z_bar |
Complex conjugate of z |
theta |
Numeric, zenith angle (from X axis) |
phi |
Numeric, azimuthal angle (in LR plane) |
omega_conformal |
Numeric, conformal energy (magnitude of momentum vector) |
coords <- convert_LRX_to_celestial(10, 5, 3) coords$theta coords$phicoords <- convert_LRX_to_celestial(10, 5, 3) coords$theta coords$phi
Creates a C++ StateStore object for compact, incremental storage of permutation states with hash-indexed lookup.
create_state_store(perm_length, init_capacity = 10000L)create_state_store(perm_length, init_capacity = 10000L)
perm_length |
Integer, length of each permutation state |
init_capacity |
Integer, initial capacity (default 10000) |
External pointer to StateStore (XPtr)
store <- create_state_store(6L) state_store_size(store)store <- create_state_store(6L) state_store_size(store)
Generates random sequences of operations and evaluates their cycle lengths to find sequences that produce the best cycles in the Cayley graph. Uses C++ with OpenMP for parallel evaluation of combinations.
find_best_random_combinations( moves, combo_length, n_samples, n_top, start_state, k, sort_by = c("longest", "most_unique") )find_best_random_combinations( moves, combo_length, n_samples, n_top, start_state, k, sort_by = c("longest", "most_unique") )
moves |
Character vector of allowed operation symbols (e.g., c("1", "2", "3") or c("L", "R", "X")) |
combo_length |
Integer, length of each operation sequence to test |
n_samples |
Integer, number of random sequences to generate and test |
n_top |
Integer, number of top results to return |
start_state |
Integer vector, initial permutation state |
k |
Integer, parameter for reverse operations |
sort_by |
Character vector of sorting criteria, applied in order. Available criteria:
Default: |
Data frame with columns:
combo_number |
Integer sequence number |
combination |
String representation of the operation sequence |
total_moves |
Cycle length for this sequence |
unique_states_count |
Number of unique states visited in the cycle |
repetition_ratio |
Ratio total_moves / unique_states_count |
# Default: longest cycles 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 ) # Short cycles with many unique states best2 <- find_best_random_combinations( moves = c("1", "2", "3"), combo_length = 10, n_samples = 50, n_top = 5, start_state = 1:10, k = 4, sort_by = c("shortest", "most_unique") )# Default: longest cycles 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 ) # Short cycles with many unique states best2 <- find_best_random_combinations( moves = c("1", "2", "3"), combo_length = 10, n_samples = 50, n_top = 5, start_state = 1:10, k = 4, sort_by = c("shortest", "most_unique") )
Searches a table of reachable states for the state whose celestial coordinates are closest to a target coordinate set.
find_closest_to_coords(reachable_states, target_coords, v_cols)find_closest_to_coords(reachable_states, target_coords, v_cols)
reachable_states |
Data frame with columns theta, phi, omega_conformal, and V-columns for state |
target_coords |
List with component |
v_cols |
Character vector of V-column names |
Single-row data frame of the closest state (with angular_distance column added)
# Typically used with output from get_reachable_states # find_closest_to_coords(states_df, target_coords, paste0("V", 1:n))# Typically used with output from get_reachable_states # find_closest_to_coords(states_df, target_coords, paste0("V", 1:n))
Searches for a specific permutation state in a reachable states table and returns the first matching row with metadata.
find_combination_in_states(reachable_states_start, search_state)find_combination_in_states(reachable_states_start, search_state)
reachable_states_start |
Data frame with V-columns and metadata |
search_state |
Integer vector, the state to search for |
Data frame row with state and metadata columns, or NULL if not found
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))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))
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)
find_path_bfs( start_state, final_state, k, bfs_levels = 500L, bfs_n_hubs = 7L, bfs_n_random = 3L, distance_method = "manhattan", verbose = TRUE, ... )find_path_bfs( start_state, final_state, k, bfs_levels = 500L, bfs_n_hubs = 7L, bfs_n_random = 3L, distance_method = "manhattan", verbose = TRUE, ... )
start_state |
Integer vector, the starting permutation state |
final_state |
Integer vector, the target permutation state |
k |
Integer, parameter for reverse operations |
bfs_levels |
Integer, depth of sparse BFS from each side (default 500) |
bfs_n_hubs |
Integer, top-degree nodes per BFS level (default 7) |
bfs_n_random |
Integer, random nodes per BFS level (default 3) |
distance_method |
Character, "manhattan" or "breakpoints" (default "manhattan") |
verbose |
Logical, print progress (default TRUE) |
... |
Additional arguments passed to find_path_iterative |
List with path, found, cycles, bfs_info
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.
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", sort_by = c("longest", "most_unique"), verbose = TRUE )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", sort_by = c("longest", "most_unique"), verbose = TRUE )
start_state |
Integer vector, the starting permutation state |
final_state |
Integer vector, the target permutation state |
k |
Integer, parameter for reverse operations |
moves |
Character vector, allowed operations (default c("1", "2", "3")) |
combo_length |
Integer, length of random operation sequences (default 20) |
n_samples |
Integer, number of random sequences to test per iteration (default 200) |
n_top |
Integer, number of top sequences to analyze fully (default 10) |
max_iterations |
Integer, maximum number of search iterations (default 10) |
potc |
Numeric in (0,1], fraction of cycle states to keep (default 1) |
ptr |
Integer, max intersections to process per iteration (default 10) |
opd |
Logical, if TRUE filters states to only combos containing bridge state (default FALSE) |
reuse_combos |
Logical, if TRUE generates random combos only once per side (cycle 1) and reuses them in subsequent cycles. Saves time but reduces diversity (default FALSE) |
distance_method |
Character, method for comparing states during bridge selection. One of "manhattan" (sum of absolute differences) or "breakpoints" (number of adjacency violations). Default "manhattan". |
sort_by |
Character vector of sorting criteria for combo selection.
See |
verbose |
Logical, if TRUE prints progress messages (default TRUE) |
Uses a compact C++ StateStore backend for O(1) incremental hash-indexed state storage, eliminating quadratic memory growth from repeated rbind.
List containing:
path |
Character vector of operations, or NULL if not found |
found |
Logical, whether a path was found |
cycles |
Number of iterations used |
selected_info |
Details about the selected intersection |
bridge_states_start |
List of forward bridge states |
bridge_states_final |
List of backward bridge states |
# 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)# 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)
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.
generate_state( n, k = n, n_moves = 25L, moves = c("1", "2", "3"), max_attempts = 100L )generate_state( n, k = n, n_moves = 25L, moves = c("1", "2", "3"), max_attempts = 100L )
n |
Integer, the size of the permutation |
k |
Integer, parameter for reverse_prefix operation |
n_moves |
Integer, number of random operations to apply (default 25) |
moves |
Character vector, allowed operations (default c("1", "2", "3")) |
max_attempts |
Integer, maximum attempts to generate a non-identity state (default 100) |
Integer vector representing a reachable permutation state
set.seed(42) generate_state(10, k = 4) generate_state(10, k = 4, n_moves = 100)set.seed(42) generate_state(10, k = 4) generate_state(10, k = 4, n_moves = 100)
Generates a data frame with unique random permutation states.
generate_unique_states_df(n, n_rows)generate_unique_states_df(n, n_rows)
n |
Integer, size of each permutation state |
n_rows |
Integer, number of unique states to generate |
Data frame with n_rows rows and columns V1, V2, ..., Vn
set.seed(42) df <- generate_unique_states_df(5, 10) head(df)set.seed(42) df <- generate_unique_states_df(5, 10) head(df)
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.
get_reachable_states(start_state, allowed_positions, k, verbose = FALSE)get_reachable_states(start_state, allowed_positions, k, verbose = FALSE)
start_state |
Integer vector, the initial permutation state |
allowed_positions |
Character vector, sequence of operations to repeat |
k |
Integer, parameter for reverse operations |
verbose |
Logical; if TRUE, prints progress and cycle information (default FALSE) |
List containing:
states |
List of all visited states |
reachable_states_df |
Data frame with states, operations, steps, and celestial coordinates |
operations |
Vector of operations applied |
coords |
List of celestial coordinate objects per step |
nL_total |
Total left shifts |
nR_total |
Total right shifts |
nX_total |
Total reverse operations |
total_moves |
Total number of moves in the cycle |
unique_states_count |
Number of unique states visited |
cycle_info |
Summary string with cycle statistics |
result <- get_reachable_states(1:10, c("1", "3"), k = 4) writeLines(result$cycle_info)result <- get_reachable_states(1:10, c("1", "3"), k = 4) writeLines(result$cycle_info)
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.
get_reachable_states_light(start_state, allowed_positions, k)get_reachable_states_light(start_state, allowed_positions, k)
start_state |
Integer vector, the initial permutation state |
allowed_positions |
Character vector, sequence of operations to repeat |
k |
Integer, parameter for reverse operations |
List containing:
total_moves |
Total number of moves to return to start state |
unique_states_count |
Number of unique states in the cycle |
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")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")
Reverses and inverts a sequence of operations. "1" (shift left) becomes "2" (shift right) and vice versa. "3" (reverse) stays the same.
invert_path(path)invert_path(path)
path |
Character vector of operations |
Character vector of inverted operations in reverse order
invert_path(c("1", "3", "2")) invert_path(c("1", "1", "3"))invert_path(c("1", "3", "2")) invert_path(c("1", "1", "3"))
Computes the sum of absolute differences between corresponding elements of two permutation states.
manhattan_distance(start_state, target_state)manhattan_distance(start_state, target_state)
start_state |
Integer vector, first state |
target_state |
Integer vector, second state |
Numeric, the Manhattan distance
manhattan_distance(1:5, 5:1) manhattan_distance(1:5, 1:5)manhattan_distance(1:5, 5:1) manhattan_distance(1:5, 1:5)
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.
manhattan_distance_matrix_gpu(states1, states2, batch_size = 256L)manhattan_distance_matrix_gpu(states1, states2, batch_size = 256L)
states1 |
Numeric matrix (N1 x n), first set of states |
states2 |
Numeric matrix (N2 x n), second set of states |
batch_size |
Integer, number of states2 rows to process at once (default 256) |
For large matrices, computation is batched over columns of the result to avoid GPU memory overflow.
Numeric matrix (N1 x N2) of Manhattan distances
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) }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) }
Traces back from target_key to the root (start state) using the parent_key/child_key edges in the BFS result.
reconstruct_bfs_path(bfs_result, target_key)reconstruct_bfs_path(bfs_result, target_key)
bfs_result |
data.frame returned by sparse_bfs() |
target_key |
Character string — state key to trace back from |
Character vector of operations from start to target
Reverses the first k elements of the state vector (turnstile operation). Tracks celestial coordinates (LRX momentum).
state |
Integer vector representing the current permutation state |
k |
Integer, number of elements to reverse from the beginning |
coords |
Optional list of current celestial coordinates. If NULL, starts from zero coordinates. |
List with components:
state |
Integer vector with first k elements reversed |
coords |
List of updated celestial coordinates (nL, nR, nX, theta, phi, omega_conformal) |
result <- reverse_prefix(1:10, k = 4) result$stateresult <- reverse_prefix(1:10, k = 4) result$state
Simple prefix reversal without coordinate tracking.
state |
Integer vector representing the current permutation state |
k |
Integer, number of elements to reverse from the beginning |
Integer vector with first k elements reversed
reverse_prefix_simple(1:10, k = 4)reverse_prefix_simple(1:10, k = 4)
Writes a list of bridge states (each with state and cycle fields)
to a CSV file.
save_bridge_states(bridge_states, filename)save_bridge_states(bridge_states, filename)
bridge_states |
List of lists, each containing |
filename |
Character, output CSV file path |
Invisible NULL. Side effect: writes a CSV file.
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"))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"))
Removes duplicate rows based on state columns (V1, V2, ..., Vn).
select_unique(df)select_unique(df)
df |
Data frame |
Data frame with unique states
df <- data.frame(V1 = c(1, 1, 2), V2 = c(2, 2, 1), op = c("a", "b", "c")) select_unique(df)df <- data.frame(V1 = c(1, 1, 2), V2 = c(2, 2, 1), op = c("a", "b", "c")) select_unique(df)
Performs a cyclic left shift on the state vector, moving the first element to the end. Tracks celestial coordinates (LRX momentum).
state |
Integer vector representing the current permutation state |
coords |
Optional list of current celestial coordinates. If NULL, starts from zero coordinates. |
List with components:
state |
Integer vector with elements shifted left by one position |
coords |
List of updated celestial coordinates (nL, nR, nX, theta, phi, omega_conformal) |
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$nLresult <- 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
Simple cyclic left shift without coordinate tracking.
state |
Integer vector representing the current permutation state |
Integer vector with elements shifted left by one position
shift_left_simple(1:5)shift_left_simple(1:5)
Performs a cyclic right shift on the state vector, moving the last element to the front. Tracks celestial coordinates (LRX momentum).
state |
Integer vector representing the current permutation state |
coords |
Optional list of current celestial coordinates. If NULL, starts from zero coordinates. |
List with components:
state |
Integer vector with elements shifted right by one position |
coords |
List of updated celestial coordinates (nL, nR, nX, theta, phi, omega_conformal) |
result <- shift_right(1:5) result$stateresult <- shift_right(1:5) result$state
Simple cyclic right shift without coordinate tracking.
state |
Integer vector representing the current permutation state |
Integer vector with elements shifted right by one position
shift_right_simple(1:5)shift_right_simple(1:5)
For each position along the path, explores all reachable states within
depth BFS steps. If any of those states appear later in the original
path (beyond current position + BFS steps taken), the algorithm "jumps"
to the farthest such match, replacing the skipped segment with the shorter
BFS route. States are indexed in a hash map supporting duplicate entries
to catch the farthest possible jumps in paths with repeated states.
short_path_bfs(path, start_state, k, depth = 5L)short_path_bfs(path, start_state, k, depth = 5L)
path |
Character vector of operations ("1"/"2"/"3" or "L"/"R"/"X") |
start_state |
Integer vector, the starting permutation state |
k |
Integer, parameter for reverse_prefix operation |
depth |
Integer, BFS exploration depth (default 5) |
List with path (shortened), original_length, new_length, savings
Removes redundant operations from a path: cancels inverse pairs ("1"+"2", "3"+"3"), reduces chains of shifts modulo n, and simplifies blocks between reverses.
short_position(allowed_positions, n)short_position(allowed_positions, n)
allowed_positions |
Character vector of operations to simplify |
n |
Integer, size of the permutation ring (used for modular reduction) |
Character vector of simplified operations
short_position(c("1", "2"), n = 5) short_position(c("3", "3"), n = 5) short_position(c("1", "1", "1", "1", "1"), n = 5)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
sparse_bfs(start_state, k, n_hubs = 7L, n_random = 3L, max_levels = 1000L)sparse_bfs(start_state, k, n_hubs = 7L, n_random = 3L, max_levels = 1000L)
start_state |
Integer vector — starting permutation |
k |
Integer — parameter for reverse_prefix operation |
n_hubs |
Number of top-degree candidates to keep per level (exploitation) |
n_random |
Number of random candidates to keep per level (exploration) |
max_levels |
Maximum BFS depth (default 1000) |
data.frame with columns: parent_key, child_key, operation, level
Returns the number of states currently stored in the StateStore.
xp |
External pointer to StateStore |
Integer, number of stored states
store <- create_state_store(6L) state_store_size(store)store <- create_state_store(6L) state_store_size(store)
Converts a data.frame/data.table of states (as returned by
analyze_top_combinations) into the compact C++ store.
store_add_from_df(store, df, cycle_val)store_add_from_df(store, df, cycle_val)
store |
External pointer to StateStore |
df |
Data frame with V1..Vn columns plus metadata |
cycle_val |
Integer, cycle number to assign |
Number of rows added (invisible)
C++ implementation that runs full cycle expansion for each combination and writes states + coordinates directly into the StateStore, bypassing data.frame creation entirely.
store_analyze_combos(store, top_combos, start_state, k, cycle_val)store_analyze_combos(store, top_combos, start_state, k, cycle_val)
store |
External pointer to StateStore |
top_combos |
Data frame with |
start_state |
Integer vector, the initial permutation state |
k |
Integer, parameter for reverse operations |
cycle_val |
Integer, cycle number to assign |
Number of states added (invisible)
GPU-accelerated version of store_analyze_combos. Processes all
combinations in parallel, step by step, grouping by operation type (L/R/X)
for GPU matrix multiplication. Falls back to CPU if GPU is unavailable.
store_analyze_combos_gpu(store, top_combos, start_state, k, cycle_val)store_analyze_combos_gpu(store, top_combos, start_state, k, cycle_val)
store |
External pointer to StateStore |
top_combos |
Data frame with |
start_state |
Integer vector, the initial permutation state |
k |
Integer, parameter for reverse operations |
cycle_val |
Integer, cycle number to assign |
Number of states added (invisible)
Clear All OPD Filters
store_clear_opd(store)store_clear_opd(store)
store |
External pointer to StateStore |
Find Combo Numbers Containing a State in a Cycle
store_combos_for_state(store, state, target_cycle)store_combos_for_state(store, state, target_cycle)
store |
External pointer to StateStore |
state |
Integer vector |
target_cycle |
Integer |
Integer vector of combo_numbers
Returns 0-based indices of states in the given cycle, excluding the first skip_first and last skip_last steps per combo.
store_filter_middle(store, target_cycle, skip_first = 5L, skip_last = 5L)store_filter_middle(store, target_cycle, skip_first = 5L, skip_last = 5L)
store |
External pointer to StateStore |
target_cycle |
Integer |
skip_first |
Integer (default 5) |
skip_last |
Integer (default 5) |
Integer vector of 0-based indices
Find Best Match by Manhattan Distance
store_find_best_match(store, target, candidate_indices = integer(0))store_find_best_match(store, target, candidate_indices = integer(0))
store |
External pointer to StateStore |
target |
Integer vector, target state |
candidate_indices |
Integer vector of 0-based indices to search (empty = search all) |
Integer, 0-based index of best match
Returns state keys present in both stores. O(min(N,M)) via hash lookup.
store_find_intersections(store_a, store_b)store_find_intersections(store_a, store_b)
store_a |
External pointer to StateStore |
store_b |
External pointer to StateStore |
Character vector of common state keys
Retrieves metadata (step, combo_number, cycle, operation, coordinates) for a single state by 0-based index.
store_get_meta(store, idx)store_get_meta(store, idx)
store |
External pointer to StateStore |
idx |
Integer, 0-based index |
Named list
Retrieves a single permutation state by 0-based index.
store_get_state(store, idx)store_get_state(store, idx)
store |
External pointer to StateStore |
idx |
Integer, 0-based index |
Integer vector of length perm_length
Lookup State Indices by State Vector
store_lookup(store, state)store_lookup(store, state)
store |
External pointer to StateStore |
state |
Integer vector |
Integer vector of 0-based indices
Traces back through cycle chain using bridge states to build the correct operation sequence. Each bridge state defines which combo path to follow in each cycle.
store_reconstruct_path( store, bridge_states, target_state, target_cycle, target_combo )store_reconstruct_path( store, bridge_states, target_state, target_cycle, target_combo )
store |
External pointer to StateStore |
bridge_states |
List of bridge state entries, each with |
target_state |
Integer vector |
target_cycle |
Integer |
target_combo |
Integer |
Character vector of operations, or NULL
Restricts indices_for_cycle and filter_middle_indices to only return states from the specified combo_numbers for the given cycle.
store_set_opd(store, target_cycle, combos)store_set_opd(store, target_cycle, combos)
store |
External pointer to StateStore |
target_cycle |
Integer, cycle number to filter |
combos |
Integer vector of allowed combo_numbers |
For debugging and backward compatibility. Converts the entire store contents to a data.frame with V1..Vn + metadata columns.
store_to_dataframe(store)store_to_dataframe(store)
store |
External pointer to StateStore |
data.frame
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.
validate_and_simplify_path(path_candidate, start_state, final_state, k)validate_and_simplify_path(path_candidate, start_state, final_state, k)
path_candidate |
Character vector of operations |
start_state |
Integer vector, start state |
final_state |
Integer vector, target state |
k |
Integer, parameter for reverse operations |
List with components:
valid |
Logical, whether the path is valid |
path |
Simplified or original path, or NULL if invalid |
res <- validate_and_simplify_path(c("1", "3"), 1:5, c(5, 2, 3, 4, 1), k = 2) res$validres <- validate_and_simplify_path(c("1", "3"), 1:5, c(5, 2, 3, 4, 1), k = 2) res$valid