Possibly new possibly old algorithm for creating superpermutations?

Question

Edit - Confirmed to be the standard greedy algorithm.

In combinatorial mathematics, a superpermutation on n symbols is a string that contains each permutation of n symbols as a substring. We will do it for $n=3$. We list all permutations of length $3$:

$123$
$132$
$213$
$231$
$312$
$321$

We will assign each permutation an initial value of $0$. They can never go below it. At each step, we will add or subtract a value from $\frac{1}{n}$ to $\frac{n-1}{n}$. In this case, our choices are $\frac{1}{3}$ or $\frac{2}{3}$. Once the value of a permutation equals $\frac{3}{3}=1$, it is no longer under our consideration because it is in our superpermutation. We will change the value depending on if the permutation is accessible through concatenation or is equal to our current state of construction.

Step 1: current string $1$, permutation values:

$123 - \frac{1}{3}$
$132 - \frac{1}{3}$
$213 - 0$
$231 - 0$
$312 - 0$
$321 - 0$

each step we take the highest non 3/3 sequence and choose the digit to raise it . always attempt to go from 2/3 t to 3/3 or from 1/3 to 2/3. Checking in that order

Step 2: current string $12$, permutation values:

$123 - \frac{2}{3}$
$132 - 0$
$213 - \frac{1}{3}$
$231 - \frac{1}{3}$
$312 - 0$
$321 - 0$

Step 3: current string $123$, permutation values:

$123 - \frac{3}{3}=1$
$132 - 0$
$213 - 0$
$231 - \frac{2}{3}$
$312 - \frac{1}{3}$
$321 - \frac{1}{3}$

Step 4: current string $1231$, permutation values:

$123 - \frac{3}{3}$
$132 - \frac{1}{3}$
$213 - 0$
$231 - \frac{3}{3}$
$312 - \frac{2}{3}$
$321 - 0$

Step 5: current string $12312$, permutation values:

$123 - \frac{3}{3}$
$132 - 0$
$213 - \frac{1}{3}$
$231 - \frac{3}{3}$
$312 - \frac{3}{3}$
$321 - 0$

Step 6: current string $123121$, permutation values:

$123 - \frac{3}{3}$
$132 - \frac{1}{3}$
$213 - \frac{2}{3}$
$231 - \frac{3}{3}$
$312 - \frac{3}{3}$
$321 - 0$

Step 7: current string $1231213$, permutation values:

$123-\frac{3}{3}$
$132 -\frac{2}{3}$
$213 -\frac{3}{3}$
$231 - \frac{3}{3}$
$312 - \frac{3}{3}$
$321 - \frac{1}{3}$
step 8 current string $12312132$, permutation values: $123 - \frac{3}{3}$
$132 - \frac{3}{3}$
$213 - \frac{3}{3}$
$231 - \frac{3}{3}$
$312 - \frac{3}{3}$
$321 - \frac{2}{3}$
step 9 current string $123121321$, permutation values: $123 - \frac{3}{3}$
$132 - \frac{3}{3}$
$213 - \frac{3}{3}$
$231 - \frac{3}{3}$
$312 - \frac{3}{3}$
$321 - \frac{3}{3}$
Final string $123121321$

At each step we take the highest non 3/3 sequence and choose the digit to raise it .

Answer 1

It looks like your idea is to build the superpermutation one permutation at a time. And at each step, you keep track of how many letters you need to add each permutation which has not been included.

This idea is (in my view) already the standard way to view the superpermutation problem. Specifically, we treat it as a directed instance of the Traveling Salesman Problem. Here, the vertices will be our permutations, and the weights of an directed edge $e=(\pi\to \tau)$ are defined according to how many letters must be concatenated to $\pi$ to get $\tau$ as a prefix. You can find this described in the section “Superpermutations as Paths through a Graph” of Greg Egan’s webpage (it also appears in the literature, but I’m feeling too lazy to add those references). Anyways, if you’ve just added the permutation “$\pi$”, then what you’re doing is assigning the value $v(\tau) := w(\pi\to\tau)/k$ (if $\tau$ has not been added yet), and otherwise assigning $v(\tau) := 0$ (here I write $v(\cdot)$ to denote your value assignments, and $w(\cdot)$ to denote the weight of a directed edge).

Unfortunately, it doesn’t seem you are suggestinf an algorithm which efficiently finds better superpermutations (at least I don’t see this in what you’ve written). Thus there is not much more to say in the matter. I will mention that there is a Google Group for discussing the superpermutation problem (link). In you are still learning about the problem, perhaps it is better to ask there (MathOverflow tends to have a slightly different audience).