permute

README

golang package 'permute' provides a tools to deal with permutations, combinations .

It is very frequent to have to loop over all permutations or combinations of a set of items, this package provides ways to make it simple.

Caveat: the number of permutations grows as fast as n! with the number of items to permute, and past 20 items the number of permutations is much greater than MaxUint64. Looping over all of them is impractical.

For the remaining practical cases, speed can still be critical though, and there are different ways to generate permutations or combinations. This package offers multiple algorithms each one being best at something:

• generation speed
• memory efficiency
• generation order
  • minimal changes
  • lexicographical

See Examples or directly the godoc for more details.

Definitions

permutations

A n-permutation is:

• a []int of length n
• where each values are unique and in the interval [0, n[

Permutation example:

// For a given set 'x'.
	x := []string{"a", "b", "c"}
	// The permutation 'p'
	p := []int{2, 1, 0}
	// transform 'x' into: `{x[2], x[1], x[0]}`
	Permute(p, x)
	fmt.Printf("%#v", x)
	//Output: []string{"c", "b", "a"}

Combinations

A (n,k)-combination or (n,k)-subset is:

• a []int of length k
• where each values are unique and in the interval [0, n[
• values are sorted in ascending order.

Combination example:

	// For a given set 'x'.
	x := []string{"a", "b", "c"}
	// The combination 'c'
	c := []int{0,2}
	// transform 'x' into: `{x[2], x[0]}`
	x=Subset(c, x)
	fmt.Printf("%#v", x)
	//Output: []string{"a", "c"}

Permutation Generation

Permutations example:

	// For a given set 'x'.
	x := []string{"a", "b", "c"}

	// One can simply loop over all permutations.
	for _, p := range Permutations(x) {
		fmt.Println(p)
	}
	//Output:
	// [a b c]
	// [b a c]
	// [c a b]
	// [a c b]
	// [b c a]
	// [c b a]

This package offers several other methods to generate all permutations:

• Lexicographical Order: Generates all permutation in lexicographical order. This is not the fastest way to generate permutations, and two successives permutation can differ by mmultiple transpositions.
• Steinhaus-Johnson-Trotter: Generates all permutation with minimal changes and minimal memory consumption, using the the Steinhaus-Johnson-Trotter.
• Even Speedup: like Steinhaus-Johnson-Trotter but with a little speed up at the expense of a O(n) extra memory (but 'n' is always very small here).
• Heap: generates all permutation with minimal changes and minimal memory consumption using the Heap's Algorithm. This is the default implementation, and the fastest. The only limit is that the last element of the loop cannot be transformed into the first one with one single transposition (like with Steinhaus-Johnson-Trotter algorithm).

Benchmarks

Benchmark are available to compare permutations generation algorithms

Combination Generation

Combinations example:

	// For a given set 'x'.
	x := []string{"a", "b", "c"}

	// One can simply loop over all 2-combinations.
	for v := range Combinations(2, x) {
		fmt.Println(v)
	}
	//Output:
	// [a b]
	// [b c]
	// [a c]

This package also offers several other methods to generate all combinations:

• Lexicographical Order: Generates all combinations in lexicographical order. This is not the fastest one, and two successives combinations can differ by mmultiple transpositions.
• Revolving Door: Generates all combinations in minimal change order using the Revolving Door Algorithm. This is the default algorithm.

Benchmarks

Benchmark are available to compare combinations generation algorithms

Still on the workbench

• generating permutation by derangements (Lynn Yarbrough)
• generating combination with strong minimal change
• generating combination with adjacent Interchange
• generate integer partitions

Documentation

Overview

Package provides algorithm to generates all permutations and combinations.

Index

• func Combinations[Slice ~[]E, E any](n int, l Slice) iter.Seq[Slice]
• func HeapPermutations[Slice ~[]E, E any](l Slice) iter.Seq2[T, Slice]
• func LexCombinations[Slice ~[]E, E any](n int, list Slice) iter.Seq[Slice]
• func LexNext(p []int) bool
• func LexPermutations[Slice ~[]E, E any](l Slice) iter.Seq[Slice]
• func Permutations[Slice ~[]E, E any](list Slice) iter.Seq2[T, Slice]
• func Permute[Slice ~[]E, E any](p P, val Slice)
• func RevCombinations[Slice ~[]E, E any](n int, list Slice) iter.Seq[Slice]
• func SJTEPermutations[Slice ~[]E, E any](l Slice) iter.Seq2[T, Slice]
• func SJTPermutations[Slice ~[]E, E any](l Slice) iter.Seq2[T, Slice]
• func Subset[Slice ~[]E, E any](p S, val Slice) Slice
• func Transpose[Slice ~[]E, E any](t T, p Slice)
• type P
• type S
• type T
  • func Decompose(p P) (transpositions []T)

Examples

• Combinations
• HeapPermutations
• Permutations
• Permute
• Subset

Functions

func Combinations

func Combinations[Slice ~[]E, E any](n int, l Slice) iter.Seq[Slice]

Combinations returns an iterator over all n-combinations of 'list'.

Example

// For a given set 'x'.
x := []string{"a", "b", "c"}

// One can simply loop over all 2-combinations.
for v := range Combinations(2, x) {
	fmt.Println(v)
}

Output:

[a b]
[b c]
[a c]

func HeapPermutations

func HeapPermutations[Slice ~[]E, E any](l Slice) iter.Seq2[T, Slice]

HeapPermutations returns an interator over all permutations of 'list' using the Heap algorithm

Each permutation is computed from the previous one + one Transposition. The iterator returns both values.

Example

A := []string{"A", "B", "C", "D"}

for t, v := range HeapPermutations(A) {
	fmt.Println(t, v)
}

Output:

[0 0] [A B C D]
[0 1] [B A C D]
[0 2] [C A B D]
[0 1] [A C B D]
[0 2] [B C A D]
[0 1] [C B A D]
[0 3] [D B A C]
[0 1] [B D A C]
[0 2] [A D B C]
[0 1] [D A B C]
[0 2] [B A D C]
[0 1] [A B D C]
[1 3] [A C D B]
[0 1] [C A D B]
[0 2] [D A C B]
[0 1] [A D C B]
[0 2] [C D A B]
[0 1] [D C A B]
[2 3] [D C B A]
[0 1] [C D B A]
[0 2] [B D C A]
[0 1] [D B C A]
[0 2] [C B D A]
[0 1] [B C D A]

func LexCombinations

func LexCombinations[Slice ~[]E, E any](n int, list Slice) iter.Seq[Slice]

LexCombinations returns an iterator over all n-combinations of 'list'.

func LexNext

func LexNext(p []int) bool

LexNext finds the next permutation in lexicographical order.

return false if it has gone back to the identity permutation.

inspired from Narayana Pandita in https://en.wikipedia.org/wiki/Permutation

func LexPermutations

func LexPermutations[Slice ~[]E, E any](l Slice) iter.Seq[Slice]

LexPermutations returns an interator over all permutations of 'list' in lexicographical order.

func Permutations

func Permutations[Slice ~[]E, E any](list Slice) iter.Seq2[T, Slice]

Permutations returns an interator over all permutations of 'list'.

Each permutation is computed from the previous one + one Transposition. The iterator returns both values.

Example

// For a given set 'x'.
x := []string{"a", "b", "c"}

// One can simply loop over all permutations.
for _, p := range Permutations(x) {
	fmt.Println(p)
}

Output:

[a b c]
[b a c]
[c a b]
[a c b]
[b c a]
[c b a]

func Permute

func Permute[Slice ~[]E, E any](p P, val Slice)

Permute permutation p to 'val'.

Example

// For a given set 'x'.
x := []string{"a", "b", "c"}
// The permutation 'p'
p := []int{2, 1, 0}
// transform 'x' into: `{x[2], x[1], x[0]}`
Permute(p, x)
fmt.Printf("%#v", x)

Output:

[]string{"c", "b", "a"}

func RevCombinations

func RevCombinations[Slice ~[]E, E any](n int, list Slice) iter.Seq[Slice]

RevCombinations returns an iterator over all n-combinations of 'list' according to the Revolving Door algorithm.

ref Knuth, Donald Ervin. The Art of Computer Programming, volume 4, fascicle 3; generating all combinations and partitions, sec. 7.2.1.3, algorithm R, Revolving-door combinations, p. 9.

func SJTEPermutations

func SJTEPermutations[Slice ~[]E, E any](l Slice) iter.Seq2[T, Slice]

SJTEPermutations returns an interator over all permutations of 'list' using the Steinhaus-Johnson-Trotter algorithm with the Even speed up.

func SJTPermutations

func SJTPermutations[Slice ~[]E, E any](l Slice) iter.Seq2[T, Slice]

SJTPermutations returns an interator over all permutations of 'list' using the Steinhaus-Johnson-Trotter algorithm.

func Subset

func Subset[Slice ~[]E, E any](p S, val Slice) Slice

Subset applies subset 'p' to 'val' and returns it.

Example

// For a given set 'x'.
x := []string{"a", "b", "c"}
// The combination 'c'
c := []int{0, 2}
// transform 'x' into: `{x[2], x[0]}`
x = Subset(c, x)
fmt.Printf("%#v", x)

Output:

[]string{"a", "c"}

func Transpose

func Transpose[Slice ~[]E, E any](t T, p Slice)

Transpose applies the transposition 't' to 'p'.

Types

type P

type P []int

T represent a single transposition

type S

type S []int

T represent a single transposition

type T

type T [2]int

T represent a single transposition

func Decompose

func Decompose(p P) (transpositions []T)

Decompose 'p' into an equivalent sequences of Transpositions.