g-harel/superpermutations

calculate and check superpermutations
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Type Name Latest commit message Commit time
Failed to load latest commit information.
superpermutations
.gitignore
build.sh
check.go
find.go
go.mod
go.sum

superpermutations

A superpermutation of the string `n` is another string that contains all the permutations of the characters in `n`. For example, `1221` is a superpermutation of `12`. However, `121` is a shorter superpermutation of `12` because it overlapps characters.

This repository contains code to produce superpermutations that are close to minimal (proving a superpermutation is minimal for any `n` is still not a solved problem).

The algorithm starts with the original string `n` and progressively appends more character(s). The number of appended/shifted characters each iteration is taken from a sequence of integers which is generated from the input string's length.

Shift sequences

`len(n)` sequence
1 `-`
2 `1`
3 `112`
4 `111211121113`
5 `111121111211112111131111211112111121111311112111121111211114`
... `...`

When the shift is of 1, the first character of the most recent permutation can be appended to the end of the string. This adds a unique permutation of the string `n` to the end of the result string.

``````123     shift(1)
231    shift(1)
312   shift(1)
12312   ...
``````

When the shift (`s`) is larger than one, the first `s` characters of the most recent permutation are mirrored and appended to the end of the result string. This process repeats until the sequence is exhausted, which means half + 1 of the result has been computed. The rest of the string is produced by mirroring this first part.

``````1234         shift(1)
2341        shift(1)
3412       shift(1)
2143    shift(3) 341 -> 143
1432   shift(1)
1234121432   ...
``````

Usage

`\$ go get -u github.com/g-harel/superpermutations/superpermutations`

CLI

``````Usage:
superpermutations [flags]

Flags:
-c, --check          check correctness of result (big performance hit)
-h, --help           help for superpermutations
-l, --length int     set input string length (max 13) (default 5)
-o, --out string     write result to a file
-p, --print          print the result (may be very large)
-r, --runes string   custom list of chars (looped if < length)
-s, --silent         silence all output (except --print)
--version        version for superpermutations
``````

Package

```import "github.com/g-harel/superpermutations"

func main() {
// generate superpermutation
s := superpermutations.Find("01234")

// confirm that it contains all permutations
fmt.Println(superpermutations.Check("01234", s))
}```
You can’t perform that action at this time.