Universal Cycle of K-Permutations

A universal cycle (or u-cycle) for a set of symbols S of size ∣S∣ and length n is a cyclic sequence in which every possible subsequence (or permutation) of length k appears as a contiguous block.

For example, with three symbols α,β,γ, for k = 2 we must include every possible pair: (α,β),(β,α),(α,γ),(γ,α),(β,γ),(γ,β). One possible universal cycle for these pairs is [α,β,α,γ,β,γ]. Note how the last element of each pair forms the first element of a different pair, creating a minimal solution with the required pairings.

The concept has significant applications in combinatorics, graph theory, and distributed systems.

Algorithm

This implementation builds a De Bruijn graph to represent the overlaps between (k-1)-sequences, and constructs the universal cycle by finding an Eulerian path.

Install

go get github.com/kagwave/universal-cycle

Usage

// Define the set of symbols
symbols := []types.Symbol{{Value: "α"}, {Value: "β"}, {Value: "γ"}}

// Set the length k for the k-permutations
k := 2

// Define options for generating the universal cycle
options := types.UCycleOptions{
    K:        k,
    Parallel: false, // Set to true if you want to run in parallel
}

// Generate an order of the k-permutations for the universal cycle [(α,β),(β,α),(α,γ),(γ,β),(β,γ),(γ,α)]
fullCycle, err := ucycle.Create(symbols, options)

// Compress the overlap in the ordered permutations into the u-word [α,β,α,γ,β,γ]
uword, err := ucycle.Compress(fullCycle)