Package {cayleyR}

Type:	Package
Title:	Cayley Graph Analysis for Permutation Puzzles
Version:	0.2.6
Description:	Implements algorithms for analyzing Cayley graphs of permutation groups for the TopSpin puzzle. Provides methods for cycle detection, state space exploration and finding optimal operation sequences in permutation groups generated by shift and reverse operations. Also provides rule-defined landmark states for probing graphs too large to enumerate, and convex and non-convex hulls for measuring the solid such states span. The method Iterative Cycle Intersection (ICI) is described in Yuri Baramykov (2026) <doi:10.48550/arXiv.2607.13219>.
License:	MIT + file LICENSE
Encoding:	UTF-8
RoxygenNote:	7.3.3
Imports:	Rcpp
LinkingTo:	Rcpp
Suggests:	testthat (≥ 3.0.0), ggmlR, data.table, knitr, rmarkdown
Config/testthat/edition:	3
VignetteBuilder:	knitr
URL:	https://github.com/Zabis13/cayleyR, https://arxiv.org/abs/2607.13219
BugReports:	https://github.com/Zabis13/cayleyR/issues
NeedsCompilation:	yes
Packaged:	2026-07-29 18:12:02 UTC; yuri
Author:	Yuri Baramykov [aut, cre]
Maintainer:	Yuri Baramykov <lbsbmsu@mail.ru>
Repository:	CRAN
Date/Publication:	2026-07-29 21:50:07 UTC

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

• https://arxiv.org/abs/2607.13219

• 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.

Usage

apply_operations(state, operations, k, coords = NULL, compute_coords = TRUE)

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

Full Breadth-First Search Over the Cayley Graph

Description

Explores every state reachable from start_state by repeatedly applying the allowed operations, recording the graph distance of each state from the start. Unlike sparse_bfs, no pruning is applied: the whole reachable component is enumerated.

Usage

cayley_bfs_full(start_state, k, moves = c("L", "R", "X"))

Arguments

Details

Celestial coordinates are a property of a path rather than of a state, since the same state can be reached by many different operation sequences. The nL, nR, nX counters reported here are those of the shortest path BFS happened to find first, and theta, phi, omega are derived from them via convert_LRX_to_celestial.

Value

Data frame with one row per reachable state:

See Also

cayley_graph_diameter, sparse_bfs

Examples

d <- cayley_bfs_full(1:5, k = 3)
nrow(d)
table(d$dist)

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()

Cayley Graph Diameter and Maximally Distant State Pairs

Description

Computes the diameter of the Cayley graph component reachable from start_state, together with the pairs of states realising it and the eccentricity of each vertex.

Usage

cayley_graph_diameter(
  start_state,
  k,
  moves = c("L", "R", "X"),
  method = c("all_pairs", "from_start"),
  max_pairs = Inf,
  verbose = FALSE
)

Arguments

Details

Two methods are available. "all_pairs" runs a BFS from every vertex and yields the true diameter and every diametral pair; its cost grows as the number of vertices times the cost of one BFS, which in practice limits it to permutations of roughly size 8 or below. "from_start" runs a single BFS and reports the eccentricity of start_state and the pairs ⁠(start_state, v)⁠ realising it; this equals the diameter only when the graph is vertex-transitive, but it scales to much larger graphs.

Value

List containing:

See Also

cayley_bfs_full

Examples

res <- cayley_graph_diameter(1:5, k = 3)
res$diameter
head(res$pairs_df)

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")

Convex Hull of a 3-D Point Cloud

Description

Builds the convex hull of a set of points in three dimensions and reports its triangular faces, surface area and volume. Implemented directly so the package keeps its single dependency on Rcpp; for the handful of points a landmark study produces, the incremental algorithm below is more than fast enough.

Usage

convex_hull_3d(pts, tol = 1e-09)

Arguments

Details

The construction is the classical incremental one. A non-degenerate starting tetrahedron is found first, then the remaining points are added one at a time: every face the new point can "see" (the point lies on the outer side of its plane) is removed, and the boundary of the hole left behind – the horizon – is joined to the new point. Points that see no face are already inside and are skipped.

Volume is the sum of the signed tetrahedra spanned by each face and an interior reference point; because every face is oriented outwards, the signs agree and the total is the enclosed volume.

Value

A list with components:

Examples

cube <- as.matrix(expand.grid(c(0, 1), c(0, 1), c(0, 1)))
h <- convex_hull_3d(cube)
h$area      # 6
h$volume    # 1

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

Create a New State Store

Description

Creates a C++ StateStore object for compact, incremental storage of permutation states with hash-indexed lookup.

Usage

create_state_store(perm_length, init_capacity = 10000L)

Arguments

Value

External pointer to StateStore (XPtr)

Examples

store <- create_state_store(6L)
state_store_size(store)

Shorten a Path by Cutting Across Cycles

Description

Shortens an existing path by looking for cycles that leave it and rejoin it further along. A cycle here is a combo word (say "1231") applied round and round until the state returns to where the cycle started – the same construction find_path_iterative searches with. If some state along that loop also occurs later in the path, the stretch between the two meeting points can be replaced by the stretch of the loop, and whenever the loop covers it in fewer operations the path gets shorter.

Usage

cycle_shortcut(
  path,
  start_state,
  k,
  n_points = 20L,
  moves = c("1", "2", "3"),
  combo_length = 20L,
  n_samples = 200L,
  n_top = 5L,
  sort_by = c("longest", "most_unique"),
  max_cycle_len = 20000L,
  n_threads = NULL,
  verbose = FALSE
)

Arguments

Details

This complements short_path_bfs rather than replacing it. That one sweeps the BFS neighbourhood a few steps deep, so it finds cuts between nearby points; a cycle wanders hundreds of steps from where it started and reaches rejoin points BFS depth cannot see. Running one after the other is reasonable.

Points are processed one at a time, and a cut is applied the moment it is found: every later point is then searched against the already-shortened path. This is why the points are carried as states rather than as positions – a cut renumbers everything downstream of it, but a state is either still somewhere in the path or it is not. Points swallowed by an earlier cut are simply skipped.

Value

List with components:

See Also

short_path_bfs, human_algorithm_to, find_path_iterative

Examples

set.seed(1)
s <- generate_state(20, k = 4, n_moves = 300)
res <- human_algorithm_to(s, k = 4, simplify = FALSE)
cut <- cycle_shortcut(res$path, s, k = 4, n_points = 5)
cut$savings

Distance Methods for Bridge Selection

Description

The registry of methods find_path_iterative may use to score candidate states when picking bridges. Each method is a function f(states, target, k) returning one score per row of states; lower is better. The search takes the lowest-scoring candidate, breaking ties on the smaller step number.

Usage

cayley_distance_methods()

cayley_distance(method)

Arguments

Details

manhattan

Sum of absolute differences to the target. The default, and the only behaviour available before methods became pluggable.

breakpoints

Number of adjacency violations relative to the target – positions where consecutive values are not consecutive in the target's frame. Often a better guide than raw displacement.

human

How far the state is from being solved the way a person solves it: the number of tiles still missing from the sorted run. Scores against the identity 1:n and ignores target, so it applies only to searches heading for the sorted ring. Ties break on the gap phase 1 works to close. See find_best_match_human.

Every method is a function of (states, target, k): a matrix with one candidate state per row, the state being approached, and the flipper width (used by human, ignored by the rest). It returns one score per row, lower being better, with NA marking a candidate it rejects. Those are the arguments of the returned method, not of the two functions here.

Value

cayley_distance_methods() returns the registered names; cayley_distance() returns the method itself, as a function.

See Also

find_path_iterative, human_phase1_rank

Examples

m <- rbind(c(1L, 2L, 3L, 4L), c(4L, 3L, 2L, 1L))
cayley_distance_methods()          # registered method names
cayley_distance("manhattan")(m, 1:4, 4)

Enclosing Hull Through Every Point

Description

Builds a closed triangulated surface whose vertices are all the given points, not just the ones on the convex boundary.

Usage

enclosing_hull_3d(pts, tol = 1e-09)

Arguments

Details

convex_hull_3d returns the smallest convex body containing the cloud, so any point strictly inside it is not a vertex of the result. When the point set is meant to be read as the corners of one figure, that is the wrong answer: some of the corners go missing. This function starts from the convex hull and then, for each interior point in turn, replaces the triangle whose plane it sits closest under with three triangles meeting at that point. The surface is dented inwards there, so the body stops being convex, but every supplied point ends up on it.

Because the surface is no longer convex, the volume is computed as the signed sum of tetrahedra over the oriented faces, which stays correct for any closed surface that does not intersect itself.

Value

A list with the same components as convex_hull_3d plus

See Also

convex_hull_3d

Examples

set.seed(1)
p <- rbind(as.matrix(expand.grid(c(0, 1), c(0, 1), c(0, 1))), c(0.5, 0.5, 0.5))
h <- enclosing_hull_3d(p)
length(h$vertices)   # 9: the interior point is a vertex too

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

Score Candidate States the Way a Person Solves

Description

Distance is how much of the sorted run is still missing: n - run_length. Within a run length, ties break on the gap phase 1 works to close, so among states with an equal run the one closest to placing its next value scores lower.

Usage

find_best_match_human(states, target, k)

Arguments

Details

Scoring is against the identity 1:n and target is ignored. That is deliberate, not an oversight: run_length only means something when the goal is the sorted ring. Relabelling into an arbitrary target's frame was tried and performed worse – the side of a two-ended search that grows from an unstructured state ends up judged against a goal phase 1 cannot read. Use this method for searches heading for 1:n, as the tail search after phase 1 does.

Registered as distance method "human"; see distance_methods.

Scoring runs in C++ (human_distance_cpp); the whole candidate set is scored in one call.

Value

Numeric vector of scores, one per row; lower is better

See Also

distance_methods, human_phase1_rank

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 best 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,
  sort_by = c("longest", "most_unique")
)

Arguments

Value

Data frame with columns:

Examples

# 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")
)

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,
  highway_distance_method = "manhattan",
  iterative_distance_method = highway_distance_method,
  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,
  keep_states = FALSE,
  one_sided = FALSE,
  distance_method = "manhattan",
  sort_by = c("longest", "most_unique"),
  verbose = TRUE
)

Arguments

Details

Uses a compact C++ StateStore backend for O(1) incremental hash-indexed state storage, eliminating quadratic memory growth from repeated rbind.

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"),
  max_attempts = 100L
)

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")

Solve a State with the Human TopSpin Algorithm

Description

Reproduces the way a person solves TopSpin by hand. A sorted run is grown one value at a time: for each new value m the ring is manoeuvred until m sits exactly k positions after m-1, so that a single reverse-prefix drops m directly behind m-1. Auxiliary flips are restricted to windows lying wholly inside the unsorted arc, so the run is never disturbed.

Usage

human_algorithm(start_state, final_state = NULL, k = 4L, simplify = TRUE)

Arguments

Details

Once the tail is down to eight tiles the insertion move no longer fits, and the tail is finished with two local 3-cycles built from the same operations (XLXLXRX and LXRXLXLX, each with a compensating rotation). Their conjugates generate the full alternating group on the tail, so any even arrangement is reachable by table lookup rather than search.

Because 3-cycles are even permutations, odd tail arrangements are out of their reach. In that case a single flip is fired across the block boundary and the run is rebuilt: moving one tile between block and tail changes the parity of the split, after which the table applies.

Value

List with components:

Examples

set.seed(1)
s <- generate_state(20, k = 4, n_moves = 50)
res <- human_algorithm(s, k = 4)
res$found

Human Algorithm Path Between Two Arbitrary States

Description

Finds a path from start_state to target_state with the same human TopSpin method as human_algorithm, but without routing through the identity state.

Usage

human_algorithm_to(start_state, target_state = NULL, k = 4L, simplify = TRUE)

Arguments

Details

human_algorithm reaches an arbitrary target by solving both endpoints to 1:n and concatenating the first path with the inverse of the second, so the word is roughly twice as long as it needs to be. Here the problem is instead relabelled: because the three operations permute positions and treat the values as inert labels, renaming every value v to its position in target_state turns "reach target_state" into "reach 1:n". The solver then runs once on the relabelled state and the resulting word applies unchanged to the original one.

Formally, with inv the inverse permutation of the target (inv[target_state] == seq_len(n)), the relabelled state is inv[start_state]. Any word P sorting it satisfies P(inv[start_state]) == 1:n, and since P acts on positions it commutes with the elementwise relabelling, giving P(start_state) == target_state.

Value

List with components:

See Also

human_algorithm

Examples

set.seed(1)
s <- generate_state(20, k = 4, n_moves = 50)
t <- generate_state(20, k = 4, n_moves = 50)
res <- human_algorithm_to(s, t, k = 4)
res$found

Follow the Phase 1 Navigator to the Tail

Description

Repeatedly applies the move human_phase1_rank prefers, growing the sorted run until phase 1 runs out of applicable moves – that is, until only the tail is left. The tail itself is not touched; finishing it needs either the 3-cycles of human_algorithm or a search such as find_path_iterative.

Usage

human_phase1_navigate(state, k = 4L, max_steps = 2000L, trace = FALSE)

Arguments

Details

The walk is greedy: at each step the single best-ranked candidate is taken.

Value

List with components:

See Also

human_phase1_rank, human_algorithm

Examples

set.seed(42)
s <- generate_state(20, k = 4, n_moves = 200)
nav <- human_phase1_navigate(s, k = 4)
nav$run

Rank Candidate Moves by the Phase 1 Criterion

Description

Exposes phase 1 of human_algorithm as a navigator: instead of committing to a move, it reports the moves phase 1 would consider from the given state, each scored. A search can use this to choose its own direction while still being guided by the human method.

Usage

human_phase1_rank(state, k = 4L, sorted = TRUE)

Arguments

Details

The candidates are composite moves – "rotate the ring so the flipper covers a chosen window, then flip" – which is the unit phase 1 actually works in. Ranking the three raw operations instead would give no signal: a single rotation changes neither the run nor the gap. One candidate is produced per window offset, plus the placing move itself when the gap already equals k. Windows that would overlap the finished run are dropped, exactly as in phase 1.

With sorted = TRUE the rows come back in phase 1's own order of preference: run descending, then gap_cost ascending, then the shorter word.

An empty data frame is returned once the run has grown far enough that only the tail is left: the insertion move no longer fits there, and the tail needs the 3-cycles of phase 2 instead.

Value

A data.frame with one row per candidate move:

See Also

run_length, human_algorithm

Examples

set.seed(1)
s <- generate_state(20, k = 4, n_moves = 50)
human_phase1_rank(s, k = 4)

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"))

Generate Landmark States for a Permutation of Size n

Description

Builds 25 structurally distinct permutations of 1:n, each defined by a rule rather than by a random draw, so the same construction can be compared across different n. They serve as landmarks (fixed probe points) in the Cayley graph: the distance from the identity to each landmark, measured for several small n where the diameter is known, gives a ratio d / diameter that can be extrapolated to larger graphs.

Usage

landmark_states(n)

Arguments

Details

The constructions, in the order returned:

1. full_reverse — \sigma(j) = n + 1 - j, the maximum number of inversions.

2. block_swap — the first half and the last half exchange places. For odd n the middle element stays put.

3. riffle — perfect interleaving of the two halves: 1, h+1, 2, h+2, \ldots with h = \lceil n/2 \rceil.

4. envelope — taken alternately from the two ends towards the centre: n, 1, n-1, 2, \ldots.

5. adjacent_swaps — the full pairing of neighbours: swap(1,2), swap(3,4), ... A trailing odd element is left alone.

6. broken_cycle — the n-cycle 2,3,\ldots,n,1 with the last two entries exchanged.

7. zigzag — all odd values ascending, then all even values descending.

8. block_rotate3 — the sequence cut into three blocks ABC of deliberately unequal length and reassembled as CAB. Equal blocks would make this a plain rotation, i.e. one L move from the identity.

9. two_cycles — two independent cyclic shifts, one inside each half.

10. shift_reverse — a left shift by 2 followed by reversing the first 4 elements.

11. pair_shift — odd positions take the value two ahead, wrapping round the odd positions only.

12. reverse_first — the first half reversed, the second fixed.

13. reverse_second — the first half fixed, the second reversed.

14. spiral — 1, n, 2, n-1, \ldots, alternating from the two ends but starting at the bottom.

15. local_block — a single block of four rotated in place, every other tile untouched.

16. single_swap — one transposition in the middle; the permutation closest to the identity in this set.

17. faro_in — the mirror of riffle: the upper half leads the interleaving.

18. block_reverse_pairs — the pairs (1,2)(3,4)... kept intact but listed in reverse block order.

19. doubling — \sigma(j) = 2j \bmod (n+1). That is a bijection only for even n; for odd n the map runs on 1..n-1 modulo n and the last tile stays put.

20. shift_third — a shift by n/3 with the displaced block reversed.

21. double_riffle — the halves interleaved two elements at a time rather than one.

22. cycles3 — 3-cycles (1 2 3)(4 5 6)... with any tail fixed.

23. alt_pairs — every other pair reversed: swap(1,2), leave (3,4), swap(5,6), ...

24. cascade — swapped pairs offset by one as they march along, like falling dominoes.

25. derangement — the halves exchanged and then every fixed point displaced, so no tile keeps its own place. Reversing one half instead would only reproduce reverse_first rotated by n/2.

At n = 6 cycles3 degenerates into two_cycles; for every n from 7 upwards all 25 states are distinct.

Value

A data.frame with one row per landmark and columns id, name, description, state_str (underscore-joined) and state (a list column holding the integer vector).

Examples

landmark_states(10)$state_str

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)
}

Number of OpenMP Threads Available

Description

Reports how many threads OpenMP would use by default, which is the core count unless OMP_NUM_THREADS says otherwise. Returns 1 when the package was built without OpenMP.

Usage

openmp_threads()

Details

Useful for sizing the n_threads argument of cycle_shortcut, whose own default is two below this number.

Value

Integer, the thread count

Examples

openmp_threads()

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).

Usage

reverse_prefix(state, k, coords = NULL)

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.

Usage

reverse_prefix_simple(state, k)

Arguments

Value

Integer vector with first k elements reversed

Examples

reverse_prefix_simple(1:10, k = 4)

Length of the Sorted Run on the Ring

Description

Returns the length of the run 1, 2, ..., r currently sitting consecutively on the ring, starting wherever value 1 happens to be. This is the quantity phase 1 of human_algorithm maximises: each insertion move appends one value to the run.

Usage

run_length(state)

Arguments

Details

Because the ring is cyclic, the position of value 1 is irrelevant – only the consecutive run following it is counted. A fully sorted state gives n; a state where 2 does not follow 1 gives 1.

Value

Integer, length of the sorted run (0 if value 1 is absent)

See Also

human_phase1_rank, human_algorithm

Examples

run_length(1:20)                  # 20, fully sorted
run_length(c(1:5, 20:16, 6:15))   # 5

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).

Usage

shift_left(state, coords = NULL)

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.

Usage

shift_left_simple(state)

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).

Usage

shift_right(state, coords = NULL)

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.

Usage

shift_right_simple(state)

Arguments

Value

Integer vector with elements shifted right by one position

Examples

shift_right_simple(1:5)

Shorten Path via Depth-Limited BFS Hopping

Description

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.

Usage

short_path_bfs(path, start_state, k, depth = 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

Query a State Store

Description

Accessors for a StateStore created by create_state_store. The implementations come from the C++ layer; these blocks document and export them.

Usage

state_store_size(xp)
state_store_perm_length(xp)
state_store_unique_count(xp)
state_store_indices_for_cycle(xp, target_cycle)

Arguments

Details

state_store_size

Number of states currently stored.

state_store_perm_length

Length of each permutation state.

state_store_unique_count

Number of distinct states.

state_store_indices_for_cycle

Row indices belonging to a given cycle.

The functions themselves are generated into RcppExports.R; these @export tags are what put them in the NAMESPACE.

Value

Integer, or an integer vector for state_store_indices_for_cycle

Examples

store <- create_state_store(6L)
state_store_size(store)
state_store_perm_length(store)

Add States to Store from Data Frame

Description

Converts a data.frame/data.table of states (as returned by analyze_top_combinations) into the compact C++ store.

Usage

store_add_from_df(store, df, cycle_val)

Arguments

Value

Number of rows added (invisible)

Analyze Combinations Directly into Store

Description

C++ implementation that runs full cycle expansion for each combination and writes states + coordinates directly into the StateStore, bypassing data.frame creation entirely.

Usage

store_analyze_combos(store, top_combos, start_state, k, cycle_val)

Arguments

Value

Number of states added (invisible)

Analyze Combinations into Store Using GPU Batch Operations

Description

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.

Usage

store_analyze_combos_gpu(store, top_combos, start_state, k, cycle_val)

Arguments

Value

Number of states added (invisible)

Drop All States From a Store

Description

Removes every stored state and rebuilds no indices, keeping the allocated capacity so the store can be refilled without reallocating. Frees memory immediately, unlike replacing the store with a fresh one (which defers release to R's garbage collector and can hold two stores at once).

Usage

store_clear(store)

Arguments

Clear All OPD Filters

Description

Clear All OPD Filters

Usage

store_clear_opd(store)

Arguments

Collect Operations Leading to a State Within One Cycle

Description

Returns the operation sequence from the start of target_combo up to (not including) end_step. Used to capture the path segment reaching a bridge while that cycle's states are still in the store, so the segment survives store_clear.

Usage

store_collect_ops(store, target_cycle, target_combo, end_step)

Arguments

Value

Character vector of operations

Find Combo Numbers Containing a State in a Cycle

Description

Find Combo Numbers Containing a State in a Cycle

Usage

store_combos_for_state(store, state, target_cycle)

Arguments

Value

Integer vector of combo_numbers

Filter Middle States for a Cycle

Description

Returns 0-based indices of states in the given cycle, excluding the first skip_first and last skip_last steps per combo.

Usage

store_filter_middle(store, target_cycle, skip_first = 5L, skip_last = 5L)

Arguments

Value

Integer vector of 0-based indices

Find Best Match by Manhattan Distance

Description

Find Best Match by Manhattan Distance

Usage

store_find_best_match(store, target, candidate_indices = integer(0))

Arguments

Value

Integer, 0-based index of best match

Find Intersections Between Two Stores

Description

Returns state keys present in both stores. O(min(N,M)) via hash lookup.

Usage

store_find_intersections(store_a, store_b)

Arguments

Value

Character vector of common state keys

Get Metadata for a State

Description

Retrieves metadata (step, combo_number, cycle, operation, coordinates) for a single state by 0-based index.

Usage

store_get_meta(store, idx)

Arguments

Value

Named list

Get State from Store

Description

Retrieves a single permutation state by 0-based index.

Usage

store_get_state(store, idx)

Arguments

Value

Integer vector of length perm_length

Lookup State Indices by State Vector

Description

Lookup State Indices by State Vector

Usage

store_lookup(store, state)

Arguments

Value

Integer vector of 0-based indices

Reconstruct Path from Store

Description

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.

Usage

store_reconstruct_path(
  store,
  bridge_states,
  target_state,
  target_cycle,
  target_combo
)

Arguments

Value

Character vector of operations, or NULL

Set OPD Combo Filter for a Cycle

Description

Restricts indices_for_cycle and filter_middle_indices to only return states from the specified combo_numbers for the given cycle.

Usage

store_set_opd(store, target_cycle, combos)

Arguments

Convert Store to Data Frame

Description

For debugging and backward compatibility. Converts the entire store contents to a data.frame with V1..Vn + metadata columns.

Usage

store_to_dataframe(store)

Arguments

Value

data.frame

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