superpermutations

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

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

more information about superpermutations

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