Rosetta Code

Superpermutation minimisation: Difference between revisions

Page Discussion

Superpermutation minimisation (view source)

Revision as of 11:14, 11 February 2024

51,767 bytes added ,  3 months ago
m
→‎{{header|Wren}}: Minor tidy
m (→‎{{header|Sidef}}: updated code)
m (→‎{{header|Wren}}: Minor tidy)
 
(43 intermediate revisions by 18 users not shown)
Line 1:
{{draft task}}
A superpermutation of N different characters is a string consisting of an arrangement of multiple copies of those N different characters in which every permutation of those characters can be found as a substring.
 
For example, representing the characters as A..Z, using N=2 we choose to use the first threetwo characters 'AB'. The permutations of 'AB' are the two (i.e. N!), strings: 'AB' and 'BA'.<br>
The permutations of 'AB' are the two, (i.e. two-factorial), strings: 'AB' and 'BA'.
 
A too obvious method of generating a superpermutation is to just join all the permutations together forming 'ABBA'.
Line 13 ⟶ 14:
 
The problem of generating the shortest superpermutation for each N ''might'' be NP complete, although the minimal strings for small values of N have been found by brute -force searches.
 
 
{{Template:Strings}}
 
 
;Reference:
* [http://www.njohnston.ca/2013/04/the-minimal-superpermutation-problem/ The Minimal Superpermutation Problem]. by Nathaniel Johnston.
* [http://oeis.org/A180632 oeis A180632] gives 0-5 as 0, 1, 3, 9, 33, 153. 6 is thought to be 872.
* [https://www.youtube.com/watch?v=wJGE4aEWc28 Superpermutations - Numberphile]. A video
* [https://www.youtube.com/watch?v=OZzIvl1tbPo Superpermutations: the maths problem solved by 4chan - Standupmaths]. A video of recent (2018) mathematical progress.
* [https://www.youtube.com/watch?v=_tpNuulTeSQ New Superpermutations Discovered!] Standupmaths & Numberphile.
<br><br>
 
=={{header|11l}}==
{{trans|Kotlin}}
 
<syntaxhighlight lang="11l">-V MAX = 12
 
[Char] sp
V count = [0] * MAX
V pos = 0
 
F factSum(n)
V s = 0
V x = 0
V f = 1
L x < n
f *= ++x
s += f
R s
 
F r(n)
I n == 0
R 0B
V c = :sp[:pos - n]
I --:count[n] == 0
:count[n] = n
I !r(n - 1)
R 0B
:sp[:pos++] = c
R 1B
 
F superPerm(n)
:pos = n
V len = factSum(n)
I len > 0
:sp = [Char("\0")] * len
L(i) 0 .. n
:count[i] = i
L(i) 1 .. n
:sp[i - 1] = Char(code' ‘0’.code + i)
L r(n) {}
 
L(n) 0 .< MAX
superPerm(n)
print(‘superPerm(#2) len = #.’.format(n, sp.len))</syntaxhighlight>
 
{{out}}
<pre>
superPerm( 0) len = 0
superPerm( 1) len = 1
superPerm( 2) len = 3
superPerm( 3) len = 9
superPerm( 4) len = 33
superPerm( 5) len = 153
superPerm( 6) len = 873
superPerm( 7) len = 5913
superPerm( 8) len = 46233
superPerm( 9) len = 409113
superPerm(10) len = 4037913
superPerm(11) len = 43954713
</pre>
 
=={{header|AWK}}==
<syntaxhighlight lang="awk">
# syntax: GAWK -f SUPERPERMUTATION_MINIMISATION.AWK
# converted from C
BEGIN {
arr[0] # prevents fatal: attempt to use scalar 'arr' as an array
limit = 11
for (n=0; n<=limit; n++) {
leng = super_perm(n)
printf("%2d %d ",n,leng)
# for (i=0; i<length(arr); i++) { printf(arr[i]) } # un-comment to see the string
printf("\n")
}
exit(0)
}
function fact_sum(n, f,s,x) {
f = 1
s = x = 0
for (;x<n;) {
f *= ++x
s += f
}
return(s)
}
function super_perm(n, i,leng) {
delete arr
pos = n
leng = fact_sum(n)
for (i=0; i<leng; i++) {
arr[i] = ""
}
for (i=0; i<=n; i++) {
cnt[i] = i
}
for (i=1; i<=n; i++) {
arr[i-1] = i + "0"
}
while (r(n)) { }
return(leng)
}
function r(n, c) {
if (!n) { return(0) }
c = arr[pos-n]
if (!--cnt[n]) {
cnt[n] = n
if (!r(n-1)) { return(0) }
}
arr[pos++] = c
return(1)
}
</syntaxhighlight>
{{out}}
<pre>
0 0
1 1
2 3
3 9
4 33
5 153
6 873
7 5913
8 46233
9 409113
10 4037913
11 43954713
</pre>
 
=={{header|C}}==
Finding a string whose length follows [https://oeis.org/A007489 OEIS A007489]. &nbsp; Complexity is the length of output string. &nbsp; It is knowknown to be ''not'' optimal.
<langsyntaxhighlight lang="c">#include <stdio.h>
#include <stdlib.h>
#include <string.h>
Line 77 ⟶ 213:
 
return 0;
}</langsyntaxhighlight>
{{out}}
<pre>
Line 93 ⟶ 229:
superperm(11) len = 43954713
</pre>
 
=={{header|C++}}==
{{trans|Kotlin}}
<syntaxhighlight lang="cpp">#include <array>
#include <iostream>
#include <vector>
 
constexpr int MAX = 12;
 
static std::vector<char> sp;
static std::array<int, MAX> count;
static int pos = 0;
 
int factSum(int n) {
int s = 0;
int x = 0;
int f = 1;
while (x < n) {
f *= ++x;
s += f;
}
return s;
}
 
bool r(int n) {
if (n == 0) {
return false;
}
char c = sp[pos - n];
if (--count[n] == 0) {
count[n] = n;
if (!r(n - 1)) {
return false;
}
}
sp[pos++] = c;
return true;
}
 
void superPerm(int n) {
pos = n;
int len = factSum(n);
if (len > 0) {
sp.resize(len);
}
for (size_t i = 0; i <= n; i++) {
count[i] = i;
}
for (size_t i = 1; i <= n; i++) {
sp[i - 1] = '0' + i;
}
while (r(n)) {}
}
 
int main() {
for (size_t n = 0; n < MAX; n++) {
superPerm(n);
std::cout << "superPerm(" << n << ") len = " << sp.size() << '\n';
}
 
return 0;
}</syntaxhighlight>
{{out}}
<pre>superPerm(0) len = 0
superPerm(1) len = 1
superPerm(2) len = 3
superPerm(3) len = 9
superPerm(4) len = 33
superPerm(5) len = 153
superPerm(6) len = 873
superPerm(7) len = 5913
superPerm(8) len = 46233
superPerm(9) len = 409113
superPerm(10) len = 4037913
superPerm(11) len = 43954713</pre>
 
=={{header|D}}==
The greedy algorithm from the Python entry. This is a little more complex than the Python code because it uses some helper arrays to avoid some allocations inside the loops, to increase performance.
<langsyntaxhighlight lang="d">import std.stdio, std.ascii, std.algorithm, core.memory, permutations2;
 
/** Uses greedy algorithm of adding another char (or two, or three, ...)
Line 140 ⟶ 351:
foreach (immutable n; 1 .. 8)
n.superpermutation.length.writeln;
}</langsyntaxhighlight>
{{out}}
<pre>1
Line 154 ⟶ 365:
{{trans|C}}
From the C version with some improvements.
<langsyntaxhighlight lang="d">import std.stdio, std.range, std.algorithm, std.ascii;
 
enum uint nMax = 12;
Line 203 ⟶ 414:
writeln;
}
}</langsyntaxhighlight>
{{out}}
<pre>superPerm( 0) len = 0
Line 218 ⟶ 429:
superPerm(11) len = 43954713</pre>
Run-time: about 0.40 seconds.
 
=={{header|Delphi}}==
{{libheader| System.SysUtils}}
{{Trans|C}}
<syntaxhighlight lang="delphi">
program Superpermutation_minimisation;
 
{$APPTYPE CONSOLE}
 
uses
System.SysUtils;
 
const
Max = 12;
 
var
super: ansistring;
pos: Integer;
cnt: TArray<Integer>;
 
function factSum(n: Integer): Uint64;
begin
var s: Uint64 := 0;
var f := 1;
var x := 0;
 
while x < n do
begin
inc(x);
f := f * x;
inc(s, f);
end;
 
Result := s;
end;
 
function r(n: Integer): Boolean;
begin
if n = 0 then
exit(false);
 
var c := super[pos - n];
 
dec(cnt[n]);
 
if cnt[n] = 0 then
begin
cnt[n] := n;
if not r(n - 1) then
exit(false);
end;
super[pos] := c;
inc(pos);
result := true;
end;
 
procedure SuperPerm(n: Integer);
begin
var pos := n;
var le: Uint64 := factSum(n);
SetLength(super, le);
 
for var i := 0 to n do
cnt[i] := i;
 
for var i := 1 to n do
super[i] := ansichar(i + ord('0'));
 
while r(n) do
;
end;
 
begin
SetLength(cnt, max);
 
for var n := 0 to max - 1 do
begin
write('superperm(', n: 2, ') ');
SuperPerm(n);
writeln('len = ', length(super));
end;
{$IFNDEF UNIX} readln; {$ENDIF}
end.</syntaxhighlight>
 
=={{header|Elixir}}==
{{trans|Ruby}}
<langsyntaxhighlight lang="elixir">defmodule Superpermutation do
def minimisation(1), do: [1]
def minimisation(n) do
Line 243 ⟶ 537:
IO.puts if n<5, do: Enum.join(result),
else: to_s.(Enum.take(result,20)) <> "...." <> to_s.(Enum.slice(result,-20..-1))
end)</langsyntaxhighlight>
 
{{out}}
Line 256 ⟶ 550:
8: len = 46233 : 12345678123456718234....43281765432187654321
</pre>
 
=={{header|FreeBASIC}}==
<syntaxhighlight lang="freebasic">' version 28-06-2018
' compile with: fbc -s console
 
Function superpermsize(n As UInteger) As UInteger
 
Dim As UInteger x, y, sum, fac
For x = 1 To n
fac = 1
For y = 1 To x
fac *= y
Next
sum += fac
Next
 
Function = sum
 
End Function
 
Function superperm(n As UInteger) As String
 
If n = 1 Then Return "1"
 
Dim As String sup_perm = "1", insert
Dim As String p, q()
Dim As UInteger a, b, i, l, x
 
For x = 2 To n
insert = IIf(x < 10, Str(x), Chr(x + 55))
l = Len(sup_perm)
If l > 1 Then l = Len(sup_perm) - x +2
ReDim q(l)
For i = 1 To l
p = Mid(sup_perm, i, x -1)
If x > 2 Then
For a = 0 To Len(p) -2
For b = a+1 To Len(p) -1
If p[a] = p[b] Then Continue For, For, For
Next
Next
End If
q(i) = p + insert + p
Next
sup_perm = q(1)
For i = 2 To UBound(q)
a = x -1
Do
If Right(sup_perm, a) = Left(q(i), a) Then
sup_perm += Mid(q(i), a +1)
Exit Do
End If
a -= 1
Loop
Next
Next
 
Function = sup_perm
 
End Function
 
' ------=< MAIN >=------
 
Dim As String superpermutation
Dim As UInteger n
 
For n = 1 To 10
superpermutation = superperm(n)
Print Using "### ######## ######## "; n; superpermsize(n); Len(superpermutation);
If n < 5 Then
Print superpermutation
Else
Print
End If
Next
 
' empty keyboard buffer
While InKey <> "" : Wend
Print : Print "hit any key to end program"
Sleep
End</syntaxhighlight>
{{out}}
<pre> 1 1 1 1
2 3 3 121
3 9 9 123121321
4 33 33 123412314231243121342132413214321
5 153 153
6 873 873
7 5913 5913
8 46233 46233
9 409113 409113
10 4037913 4037913</pre>
 
=={{header|Go}}==
{{trans|C}}
<syntaxhighlight lang="go">package main
 
import "fmt"
 
const max = 12
 
var (
super []byte
pos int
cnt [max]int
)
 
// 1! + 2! + ... + n!
func factSum(n int) int {
s := 0
for x, f := 0, 1; x < n; {
x++
f *= x
s += f
}
return s
}
 
func r(n int) bool {
if n == 0 {
return false
}
c := super[pos-n]
cnt[n]--
if cnt[n] == 0 {
cnt[n] = n
if !r(n - 1) {
return false
}
}
super[pos] = c
pos++
return true
}
 
func superperm(n int) {
pos = n
le := factSum(n)
super = make([]byte, le)
for i := 0; i <= n; i++ {
cnt[i] = i
}
for i := 1; i <= n; i++ {
super[i-1] = byte(i) + '0'
}
 
for r(n) {
}
}
 
func main() {
for n := 0; n < max; n++ {
fmt.Printf("superperm(%2d) ", n)
superperm(n)
fmt.Printf("len = %d\n", len(super))
}
}</syntaxhighlight>
 
{{out}}
<pre>
superperm( 0) len = 0
superperm( 1) len = 1
superperm( 2) len = 3
superperm( 3) len = 9
superperm( 4) len = 33
superperm( 5) len = 153
superperm( 6) len = 873
superperm( 7) len = 5913
superperm( 8) len = 46233
superperm( 9) len = 409113
superperm(10) len = 4037913
superperm(11) len = 43954713
</pre>
 
=={{header|Groovy}}==
{{trans|Java}}
<syntaxhighlight lang="groovy">import static java.util.stream.IntStream.rangeClosed
 
class Superpermutation {
final static int nMax = 12
 
static char[] superperm
static int pos
static int[] count = new int[nMax]
 
static int factSum(int n) {
return rangeClosed(1, n)
.map({ m -> rangeClosed(1, m).reduce(1, { a, b -> a * b }) }).sum()
}
 
static boolean r(int n) {
if (n == 0) {
return false
}
 
char c = superperm[pos - n]
if (--count[n] == 0) {
count[n] = n
if (!r(n - 1)) {
return false
}
}
superperm[pos++] = c
return true
}
 
static void superPerm(int n) {
String chars = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
 
pos = n
superperm = new char[factSum(n)]
 
for (int i = 0; i < n + 1; i++) {
count[i] = i
}
for (int i = 1; i < n + 1; i++) {
superperm[i - 1] = chars.charAt(i)
}
 
while (r(n)) {
}
}
 
static void main(String[] args) {
for (int n = 0; n < nMax; n++) {
superPerm(n)
printf("superPerm(%2d) len = %d", n, superperm.length)
println()
}
}
}</syntaxhighlight>
{{out}}
<pre>superPerm( 0) len = 0
superPerm( 1) len = 1
superPerm( 2) len = 3
superPerm( 3) len = 9
superPerm( 4) len = 33
superPerm( 5) len = 153
superPerm( 6) len = 873
superPerm( 7) len = 5913
superPerm( 8) len = 46233
superPerm( 9) len = 409113
superPerm(10) len = 4037913
superPerm(11) len = 43954713</pre>
 
=={{header|J}}==
Line 261 ⟶ 799:
If there's an 872 long superpermutation for a six letter alphabet, this is not optimal.
 
<langsyntaxhighlight Jlang="j">approxmin=:3 :0
seqs=. y{~(A.&i.~ !)#y
r=.{.seqs
Line 278 ⟶ 816:
end.
r
)</langsyntaxhighlight>
 
Some sequence lengths:
 
<langsyntaxhighlight Jlang="j"> (#, #@approxmin)@> (1+i.8) {.&.> <'abcdefghijk'
1 1
2 3
Line 290 ⟶ 828:
6 873
7 5913
8 46233</langsyntaxhighlight>
 
=={{header|Java}}==
Translation of [[Superpermutation_minimisation#C|C]] via [[Superpermutation_minimisation#D|D]]
{{works with|Java|8}}
<langsyntaxhighlight lang="java">import static java.util.stream.IntStream.rangeClosed;
 
public class Test {
Line 345 ⟶ 883:
}
}
}</langsyntaxhighlight>
 
<pre>superPerm( 0) len = 0
Line 359 ⟶ 897:
superPerm(10) len = 4037913
superPerm(11) len = 43954713</pre>
 
=={{header|Julia}}==
{{trans|D}}
Runs in about 1/4 second.
<syntaxhighlight lang="julia">const nmax = 12
 
function r!(n, s, pos, count)
if n == 0
return false
end
c = s[pos + 1 - n]
count[n + 1] -= 1
if count[n + 1] == 0
count[n + 1] = n
if r!(n - 1, s, pos, count) == 0
return false
end
end
s[pos + 1] = c
pos += 1
true
end
 
function superpermutation(n)
count = zeros(nmax)
pos = n
superperm = zeros(UInt8, n < 2 ? n : mapreduce(factorial, +, 1:n))
for i in 0:n-1
count[i + 1] = i
superperm[i + 1] = Char(i + '0')
end
count[n + 1] = n
while r!(n, superperm, pos, count) ; end
superperm
end
 
function testsuper(N, verbose=false)
for i in 0:N-1
s = superpermutation(i)
println("Superperm($i) has length $(length(s)) ", (verbose ? String(s) : ""))
end
end
 
testsuper(nmax)
</syntaxhighlight>{{out}}
<pre>
Superperm(0) has length 0
Superperm(1) has length 1
Superperm(2) has length 3
Superperm(3) has length 9
Superperm(4) has length 33
Superperm(5) has length 153
Superperm(6) has length 873
Superperm(7) has length 5913
Superperm(8) has length 46233
Superperm(9) has length 409113
Superperm(10) has length 4037913
Superperm(11) has length 43954713
</pre>
 
=={{header|Kotlin}}==
{{trans|C}}
<syntaxhighlight lang="scala">// version 1.1.2
 
const val MAX = 12
 
var sp = CharArray(0)
val count = IntArray(MAX)
var pos = 0
 
fun factSum(n: Int): Int {
var s = 0
var x = 0
var f = 1
while (x < n) {
f *= ++x
s += f
}
return s
}
 
fun r(n: Int): Boolean {
if (n == 0) return false
val c = sp[pos - n]
if (--count[n] == 0) {
count[n] = n
if (!r(n - 1)) return false
}
sp[pos++] = c
return true
}
 
fun superPerm(n: Int) {
pos = n
val len = factSum(n)
if (len > 0) sp = CharArray(len)
for (i in 0..n) count[i] = i
for (i in 1..n) sp[i - 1] = '0' + i
while (r(n)) {}
}
 
fun main(args: Array<String>) {
for (n in 0 until MAX) {
superPerm(n)
println("superPerm(${"%2d".format(n)}) len = ${sp.size}")
}
}</syntaxhighlight>
 
{{out}}
<pre>
superPerm( 0) len = 0
superPerm( 1) len = 1
superPerm( 2) len = 3
superPerm( 3) len = 9
superPerm( 4) len = 33
superPerm( 5) len = 153
superPerm( 6) len = 873
superPerm( 7) len = 5913
superPerm( 8) len = 46233
superPerm( 9) len = 409113
superPerm(10) len = 4037913
superPerm(11) len = 43954713
</pre>
 
=={{header|Mathematica}} / {{header|Wolfram Language}}==
Greedy algorithm:
<syntaxhighlight lang="mathematica">ClearAll[OverlapDistance, ConstructDistances]
OverlapDistance[{s1_List, s2_List}] := OverlapDistance[s1, s2]
OverlapDistance[s1_List, s2_List] := Module[{overlaprange, overlap, l},
overlaprange = {Min[Length[s1], Length[s2]], 0};
l = LengthWhile[Range[Sequence @@ overlaprange, -1], Take[s1, -#] =!= Take[s2, #] &];
overlap = overlaprange[[1]] - l;
<|"Overlap" -> overlap, "Distance" -> Length[s2] - overlap|>
]
ConstructDistances[perms_List] := Module[{sel, OD, fullseq},
OD = BlockMap[OverlapDistance, perms, 2, 1];
fullseq =
Fold[Join[#1, Drop[#2[[2]], #2[[1]]["Overlap"]]] &,
First[perms], {OD, Rest[perms]} // Transpose];
fullseq
]
Dynamic[Length[perms]]
Do[
n = i;
perms = Permutations[Range[n]];
{start, perms} = TakeDrop[perms, 1];
While[Length[perms] > 0,
last = Last[start];
dists =
Table[<|"Index" -> i, OverlapDistance[last, perms[[i]]]|>, {i,
Length[perms]}];
sel = First[TakeSmallestBy[dists, #["Distance"] &, 1]];
AppendTo[start, perms[[sel["Index"]]]];
perms = Delete[perms, sel["Index"]];
];
Print[{n, Length@ConstructDistances[start]}]
,
{i, 1, 7}
]</syntaxhighlight>
{{out}}
<pre>{1,1}
{2,3}
{3,9}
{4,33}
{5,153}
{6,873}
{7,5913}</pre>
 
=={{header|Nim}}==
{{trans|Go}}
<syntaxhighlight lang="nim">import strformat
 
const MAX = 12
 
var super: seq[char] = @[]
var pos: int
var cnt: array[MAX, int]
 
proc factSum(n: int): int =
var s, x = 0
var f = 1
while x < n:
inc x
f *= x
inc s, f
s
 
proc r(n: int): bool =
if n == 0:
return false
var c = super[pos - n]
dec cnt[n]
if cnt[n] == 0:
cnt[n] = n
if not r(n - 1):
return false
super[pos] = c
inc pos
true
 
proc superperm(n: int) =
pos = n
var le = factSum(n)
super.setLen(le)
for i in 0..n:
cnt[i] = i
for i in 1..n:
super[i-1] = char(i + ord('0'))
while r(n):
discard
for n in 0..<MAX:
write(stdout, fmt"superperm({n:2})")
superperm(n)
writeLine(stdout, fmt" len = {len(super)}")</syntaxhighlight>
{{out}}
<pre>
superperm( 0) len = 0
superperm( 1) len = 1
superperm( 2) len = 3
superperm( 3) len = 9
superperm( 4) len = 33
superperm( 5) len = 153
superperm( 6) len = 873
superperm( 7) len = 5913
superperm( 8) len = 46233
superperm( 9) len = 409113
superperm(10) len = 4037913
superperm(11) len = 43954713
</pre>
 
=={{header|Objeck}}==
{{trans|C}}
<syntaxhighlight lang="objeck">class SuperPermutation {
@super : static : Char[];
@pos : static : Int;
@cnt : static : Int[];
 
function : Main(args : String[]) ~ Nil {
max := 12;
@cnt := Int->New[max];
@super := Char->New[0];
 
for(n := 0; n < max; n += 1;) {
"superperm({$n}) "->Print();
SuperPerm(n);
len := @super->Size() - 1;
"len = {$len}"->PrintLine();
};
}
 
function : native : FactSum(n : Int) ~ Int {
s := 0; x := 0; f := 1;
while(x < n) {
f *= ++x; s += f;
};
return s;
}
 
function : native : R(n : Int) ~ Bool {
if(n = 0) {
return false;
};
 
c := @super[@pos - n];
if(--@cnt[n] = 0) {
@cnt[n] := n;
if(<>R(n - 1)) {
return false;
};
};
@super[@pos++] := c;
 
return true;
}
 
function : SuperPerm(n : Int) ~ Nil {
@pos := n;
len := FactSum(n);
 
tmp := Char->New[len + 1];
Runtime->Copy(tmp, 0, @super, 0, @super->Size());
@super := tmp;
 
for(i := 0; i <= n; i += 1;) {
@cnt[i] := i;
};
 
for(i := 1; i <= n; i += 1;) {
@super[i - 1] := i + '0';
};
do {
r := R(n);
}
while(r);
}
}
</syntaxhighlight>
 
{{output}}
<pre>
superperm(0) len = 0
superperm(1) len = 1
superperm(2) len = 3
superperm(3) len = 9
superperm(4) len = 33
superperm(5) len = 153
superperm(6) len = 873
superperm(7) len = 5913
superperm(8) len = 46233
superperm(9) len = 409113
superperm(10) len = 4037913
superperm(11) len = 43954713
</pre>
 
=={{header|Perl}}==
Line 364 ⟶ 1,216:
 
{{libheader|ntheory}}
<langsyntaxhighlight lang="perl">use ntheory qw/forperm/;
for my $len (1..8) {
my($pre, $post, $t) = ("","");
Line 373 ⟶ 1,225:
} $len;
printf "%2d: %8d %8d\n", $len, length($pre), length($post);
}</langsyntaxhighlight>
{{out}}
<pre> 1: 1 1
Line 384 ⟶ 1,236:
8: 80640 109600</pre>
The permutations are generated in lexicographic order, and it seems prepending them leads to smaller strings than adding to the end. These are still quite a bit larger than the heuristic methods.
 
=={{header|Phix}}==
{{trans|C}}
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">constant</span> <span style="color: #000000;">nMax</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()=</span><span style="color: #004600;">JS</span><span style="color: #0000FF;">?</span><span style="color: #000000;">8</span><span style="color: #0000FF;">:</span><span style="color: #000000;">12</span><span style="color: #0000FF;">)</span>
<span style="color: #000080;font-style:italic;">-- Aside: on desktop/Phix, strings can be modified in situ, whereas
-- JavaScript strings are immutable, and the equivalent code
-- in p2js.js ends up doing excessive splitting and splicing
-- hence nMax has to be significantly smaller in a browser.</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">superperm</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">count</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">pos</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">factSum</span><span style="color: #0000FF;">(</span><span style="color: #004080;">int</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">f</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">f</span> <span style="color: #0000FF;">*=</span> <span style="color: #000000;">i</span>
<span style="color: #000000;">s</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">f</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">s</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">(</span><span style="color: #004080;">int</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #0000FF;">(</span><span style="color: #000000;">n</span> <span style="color: #0000FF;">==</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">false</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">c</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">superperm</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pos</span><span style="color: #0000FF;">-</span><span style="color: #000000;">n</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">count</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">count</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">count</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span>
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #008080;">return</span> <span style="color: #004600;">false</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">pos</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #000000;">superperm</span><span style="color: #0000FF;">[</span><span style="color: #000000;">pos</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">c</span>
<span style="color: #008080;">return</span> <span style="color: #004600;">true</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">superPerm</span><span style="color: #0000FF;">(</span><span style="color: #004080;">int</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">chars</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">pos</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n</span>
<span style="color: #000000;">superperm</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">chars</span><span style="color: #0000FF;">&</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">' '</span><span style="color: #0000FF;">,</span><span style="color: #000000;">factSum</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">count</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">tagset</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">r</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span> <span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">superperm</span><span style="color: #0000FF;">!=</span><span style="color: #008000;">""</span> <span style="color: #008080;">then</span> <span style="color: #0000FF;">?</span><span style="color: #000000;">9</span><span style="color: #0000FF;">/</span><span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">elsif</span> <span style="color: #000000;">n</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">7</span> <span style="color: #008080;">then</span>
<span style="color: #000080;font-style:italic;">-- (I estimate it would take at least 5 days to validate
-- superPerm(12), feel free to try it on your own time)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">factorial</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #7060A8;">match</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">permute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">chars</span><span style="color: #0000FF;">),</span><span style="color: #000000;">superperm</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> <span style="color: #0000FF;">?</span><span style="color: #000000;">9</span><span style="color: #0000FF;">/</span><span style="color: #000000;">0</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">nMax</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">superPerm</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">superperm</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">l</span><span style="color: #0000FF;">></span><span style="color: #000000;">40</span> <span style="color: #008080;">then</span> <span style="color: #000000;">superperm</span><span style="color: #0000FF;">[</span><span style="color: #000000;">20</span><span style="color: #0000FF;">..-</span><span style="color: #000000;">20</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"..."</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">e</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"superPerm(%2d) len = %d %s (%s)\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">l</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">superperm</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">e</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
superPerm( 0) len = 0 (0s)
superPerm( 1) len = 1 1 (0s)
superPerm( 2) len = 3 121 (0s)
superPerm( 3) len = 9 123121321 (0s)
superPerm( 4) len = 33 123412314231243121342132413214321 (0s)
superPerm( 5) len = 153 1234512341523412534...4352143251432154321 (0s)
superPerm( 6) len = 873 1234561234516234512...2154326154321654321 (0.0s)
superPerm( 7) len = 5913 1234567123456172345...5432716543217654321 (0.7s)
superPerm( 8) len = 46233 1234567812345671823...3281765432187654321 (0.7s)
superPerm( 9) len = 409113 1234567891234567819...9187654321987654321 (0.8s)
superPerm(10) len = 4037913 123456789A123456789...987654321A987654321 (1.2s)
superPerm(11) len = 43954713 123456789AB12345678...87654321BA987654321 (6.5s)
superPerm(12) len = 522956313 123456789ABC1234567...7654321CBA987654321 (1 minute and 09s)
</pre>
 
===Alternative===
Finds the longest overlap, similar to Python's greedy s_perm0 but theoretically more efficient.<br>
I also tried prefixing res with any longer overlap at the start, but it just made things worse.<br>
Uses factSum() from above, and compares that with these results (which are always worse for >3).
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">factSum</span><span style="color: #0000FF;">(</span><span style="color: #004080;">int</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">f</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">n</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">f</span> <span style="color: #0000FF;">*=</span> <span style="color: #000000;">i</span>
<span style="color: #000000;">s</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">f</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">s</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">superPerm</span><span style="color: #0000FF;">(</span><span style="color: #004080;">int</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">atom</span> <span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">chars</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">n</span><span style="color: #0000FF;">]</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">f</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">factorial</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">perms</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">""</span><span style="color: #0000FF;">,</span><span style="color: #000000;">f</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">f</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">perms</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">permute</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">chars</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">perms</span><span style="color: #0000FF;">[$]</span>
<span style="color: #000000;">perms</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">perms</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..$-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">while</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">perms</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">best</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">bi</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">perms</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">perms</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">pi</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">perms</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">m</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">),</span>
<span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">find</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">m</span><span style="color: #0000FF;">],</span><span style="color: #000000;">pi</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">l</span><span style="color: #0000FF;">=</span><span style="color: #000000;">k</span> <span style="color: #008080;">to</span> <span style="color: #000000;">1</span> <span style="color: #008080;">by</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">1</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">m</span><span style="color: #0000FF;">]!=</span><span style="color: #000000;">pi</span><span style="color: #0000FF;">[</span><span style="color: #000000;">l</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">k</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">exit</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">m</span> <span style="color: #0000FF;">-=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">k</span><span style="color: #0000FF;">></span><span style="color: #000000;">best</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">best</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">k</span>
<span style="color: #000000;">bi</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">i</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">match</span><span style="color: #0000FF;">(</span><span style="color: #000000;">perms</span><span style="color: #0000FF;">[</span><span style="color: #000000;">bi</span><span style="color: #0000FF;">],</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #0000FF;">?</span><span style="color: #000000;">9</span><span style="color: #0000FF;">/</span><span style="color: #000000;">0</span> <span style="color: #000080;font-style:italic;">-- (sanity check)</span>
<span style="color: #008080;">else</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">&=</span> <span style="color: #000000;">perms</span><span style="color: #0000FF;">[</span><span style="color: #000000;">bi</span><span style="color: #0000FF;">][</span><span style="color: #000000;">best</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..$]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">perms</span><span style="color: #0000FF;">[</span><span style="color: #000000;">bi</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">perms</span><span style="color: #0000FF;">[$]</span>
<span style="color: #000000;">perms</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">perms</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..$-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">lr</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">),</span> <span style="color: #000000;">fsn</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">factSum</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">op</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #008000;">"&lt;"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"="</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"&gt;"</span><span style="color: #0000FF;">}[</span><span style="color: #7060A8;">compare</span><span style="color: #0000FF;">(</span><span style="color: #000000;">lr</span><span style="color: #0000FF;">,</span><span style="color: #000000;">fsn</span><span style="color: #0000FF;">)+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">t0</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t0</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">e</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">></span><span style="color: #000000;">1</span><span style="color: #0000FF;">?</span><span style="color: #008000;">", "</span><span style="color: #0000FF;">&</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t0</span><span style="color: #0000FF;">):</span><span style="color: #008000;">""</span><span style="color: #0000FF;">)</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"superPerm(%d) len = %d (%s%d%s)\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">n</span><span style="color: #0000FF;">,</span><span style="color: #000000;">lr</span><span style="color: #0000FF;">,</span><span style="color: #000000;">op</span><span style="color: #0000FF;">,</span><span style="color: #000000;">fsn</span><span style="color: #0000FF;">,</span><span style="color: #000000;">e</span><span style="color: #0000FF;">})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">7</span> <span style="color: #008080;">do</span> <span style="color: #000080;font-style:italic;">-- (note: 8 takes 65x longer than 7)</span>
<span style="color: #000000;">superPerm</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
superPerm(1) len = 1 (=1)
superPerm(2) len = 3 (=3)
superPerm(3) len = 9 (=9)
superPerm(4) len = 35 (>33)
superPerm(5) len = 162 (>153)
superPerm(6) len = 924 (>873)
superPerm(7) len = 6250 (>5913, 2.5s)
superPerm(8) len = 48703 (>46233, 2 minutes and 43s)
</pre>
 
=={{header|PureBasic}}==
{{trans|C}}
<syntaxhighlight lang="purebasic">EnableExplicit
#MAX=10
Declare.i fact_sum(n.i) : Declare.i r(n.i) : Declare superperm(n.i)
Global pos.i, Dim cnt.i(#MAX), Dim super.s{1}(fact_sum(#MAX))
 
If OpenConsole() ;- MAIN: Superpermutation_minimisation
Define.i n
For n=0 To #MAX
superperm(n) : Print("superperm("+RSet(Str(n),2)+") len = "+LSet(Str(pos),10))
If n<=4 : Print(~"\t"+PeekS(@super(),pos)) : EndIf
PrintN("")
Next
Input()
EndIf
End ;- END: Superpermutation_minimisation
 
Procedure.i fact_sum(n.i)
Define.i s=0,f=1,x=0
While x<n : x+1 : f*x : s+f : Wend
ProcedureReturn s
EndProcedure
 
Procedure.i r(n.i)
If Not n : ProcedureReturn 0 : EndIf
Define c.s{1}=super(pos-n)
cnt(n)-1
If Not cnt(n)
cnt(n)=n
If Not r(n-1) : ProcedureReturn 0 : EndIf
EndIf
super(pos)=c : pos+1 : ProcedureReturn 1
EndProcedure
 
Procedure superperm(n.i)
pos=n
Define.i len=fact_sum(n),i
For i=0 To n : cnt(i)=i : Next
For i=1 To n : super(i-1)=Chr('0'+i) : Next
While r(n) : Wend
EndProcedure</syntaxhighlight>
{{out}}
<pre>superperm( 0) len = 0
superperm( 1) len = 1 1
superperm( 2) len = 3 121
superperm( 3) len = 9 123121321
superperm( 4) len = 33 123412314231243121342132413214321
superperm( 5) len = 153
superperm( 6) len = 873
superperm( 7) len = 5913
superperm( 8) len = 46233
superperm( 9) len = 409113
superperm(10) len = 4037913</pre>
 
=={{header|Python}}==
<langsyntaxhighlight lang="python">"Generate a short Superpermutation of n characters A... as a string using various algorithms."
 
 
Line 526 ⟶ 1,586:
print('\n'.join('%12s (%.3f)' % (k, v.total_seconds()) for k, v in
sorted(runtime.items(), key=lambda keyvalue: keyvalue[1])))
</syntaxhighlight>
</lang>
 
{{out}}
Line 631 ⟶ 1,691:
===Alternative Version===
{{trans|D}}
<langsyntaxhighlight lang="python">from array import array
from string import ascii_uppercase, digits
from operator import mul
Line 689 ⟶ 1,749:
print
 
main()</langsyntaxhighlight>
It is four times slower than the D entry. The output is about the same as the D entry.
 
Line 695 ⟶ 1,755:
{{trans|Ruby}}
 
<langsyntaxhighlight lang="racket">#lang racket/base
(require racket/list racket/format)
 
Line 727 ⟶ 1,787:
 
(for* ((n (in-range 1 (add1 8))) (ary (in-value (superperm n))))
(printf "~a: len = ~a : ~a~%" (~a n #:width 3) (~a (length ary) #:width 8) (20..20 ary)))</langsyntaxhighlight>
 
{{out}}
Line 739 ⟶ 1,799:
7 : len = 5913 : (1 2 3 4 5 6 7 1 2 3 4 5 6 1 7 2 3 4 5 6 .. 6 5 4 3 2 7 1 6 5 4 3 2 1 7 6 5 4 3 2 1)
8 : len = 46233 : (1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 1 8 2 3 4 .. 4 3 2 8 1 7 6 5 4 3 2 1 8 7 6 5 4 3 2 1)</pre>
 
=={{header|Raku}}==
(formerly Perl 6)
{{trans|Perl}}
<syntaxhighlight lang="raku" line>for 1..8 -> $len {
my $pre = my $post = my $t = '';
for ('a'..'z')[^$len].permutations -> @p {
$t = @p.join('');
$post ~= $t unless index($post, $t);
$pre = $t ~ $pre unless index($pre, $t);
}
printf "%1d: %8d %8d\n", $len, $pre.chars, $post.chars;
}</syntaxhighlight>
{{out}}
<pre>1: 1 1
2: 4 4
3: 12 15
4: 48 64
5: 240 325
6: 1440 1956
7: 10080 13699
8: 80640 109600</pre>
 
=={{header|REXX}}==
===version 1===
This REXX version just does simple finds for the permutations.
<langsyntaxhighlight lang="rexx">/*REXX program attempts to find better minimizations for computing superpermutations.*/
parse arg cycles . /*obtain optional arguments from the CL*/
if cycles=='' | cycles=="," then cycles=7 7 /*Not specified? Then use the default.*/
 
do n=0 to cycles
#= 0; $.= /*populate the first permutation. */
do pop=1 for n; @.pop= d2x(pop); $.0= $.0 || @.pop; end /*pop*/
end /*pop*/
 
do while aPerm(n, 0)
if n\==0 then #= #+1; $.#=; do j=1 for n; $.#=$.# || @.j; end /*j*/
end /*while*/do j=1 for n; $.#= $.# || @.j
z=$.0 end /*j*/
end /*while*/
nm=n-1
z= $.0
do ?=1 for #; if $.j=='' then iterate; if pos($.?, z)\==0 then iterate
nm= n-1
parse var $.? h 2 R 1 L =(n)
if left(z,do nm)p==R1 thenfor do#; z if $.j==h'' || z; iterate; end then iterate
if right(z, 1)==h then do; z=z || R; iterate; end if pos($.p, z)\==0 then iterate
z=zparse var || $.?p h 2 R 1 L =(n)
endif left(z, /*?*/nm)==R then do; z= h || z; iterate; /* [↑] more IFs could be added for opt*/end
if right(z, 1)==h then do; z= z || R; iterate; end
z= z || $.p
end /*p*/ /* [↑] more IFs could be added for opt*/
 
sayL= 'length of superpermutationcommas('n") =" length(z) )
say 'length of superpermutation('n") =" right(L, max(length(L), cycles+2) )
end /*cycle*/
exit 0 /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
aPermcommas: procedureparse exposearg @.?; do jc=length(?)-3 parseto arg1 n,i; by nm=n-13; ?=insert(',', if?, n==0jc); end; then return 0?
/*──────────────────────────────────────────────────────────────────────────────────────*/
do k=nm by -1 for nm; kp=k+1; if @.k<@.kp then do; i=k;leave; end; end /*k*/
aPerm: procedure expose @.; parse arg n,i; do j=i+1 while nm= j<n; - parse1; value @.j @.n withif @.n==0 @.j; then return n=n-1; end /*j*/0
do k=nm by -1 for nm; kp=k+1; if @.k<@.kp then do; i=k; leave; end; end /*k*/
do j=i+1 while j<n; parse value @.j @.n with @.n @.j; n= n-1; end /*j*/
if i==0 then return 0
do m=i+1 while @.m<@.i; end /*m*/; parse value @.m @.i with @.i @.m
return 1</langsyntaxhighlight>
'''{{out|output''' |text=&nbsp; when using the input used is: &nbsp; &nbsp; <tt> 8 </tt>}}
<pre>
length of superpermutation(0) = 0
length of superpermutation(1) = 1
length of superpermutation(2) = 2
length of superpermutation(3) = 9
length of superpermutation(4) = 50
length of superpermutation(5) = 302
length of superpermutation(6) = 1922 1,922
length of superpermutation(7) = 13652 13,652
length of superpermutation(8) = 109538 109,538
</pre>
 
===version 2===
<langsyntaxhighlight lang="rexx">/*REXX program attempts to find better minimizations for computing superpermutations.*/
parse arg cycles . /*obtain optional arguments from the CL*/
if cycles=='' | cycles=="," then cycles=7 7 /*Not specified? Then use the default.*/
 
do n=0 to cycles
#= 0; $.= /*populate the first permutation. */
do pop=1 for n; @.pop= d2x(pop); $.0= $.0 || @.pop; end /*pop*/
end /*pop*/
 
do while aPerm(n,0); if n\==0 then #= #+1; $.#=
if n\==0 thendo #j=#+1; $.#=for n; do j=1 for n; $.#= $.# || @.j; end /*j*/
end /*whilej*/
end /*while*/
z=$.0
z= $.0
c=0 /*count of found permutations (so far).*/
c= 0 /*count of found permutations (so far).*/
do j=1 while c\==#
if j># then do; c= c +1 1 /*exhausted finds and shortcuts; concat*/
z= z || $.j; $.j=
j= 1
end
if $.j=='' then iterate /*Already found? Then ignore this perm.*/
if pos($.j, z)\==0 then do; c= c + 1; $.j=
$.j= iterate
iterateend
end
 
do k=n-1 to 1 by -1 /*handle the shortcuts in perm finding.*/
if substr($.j, k)==left(z, k) then do; c= c+1 /*found a rightish shortcut*/
z= left($.j, k-1) || z; $.j=
iterate j
end
if left($.j, k) ==right(z, k) then do; c= c+1 /*found a leftish shortcut*/
z= z || substr($.j, k+1); $.j=
iterate j
end
end /*k*/ /* [↑] more IFs could be added for opt*/
end /*j*/
 
say 'length of superpermutation('n") =" length(z)
endL= commas( length(z) /*cycle*/)
say 'length of superpermutation('n") =" right(L, max(length(L), cycles+2) )
exit /*stick a fork in it, we're all done. */
end /*n*/
exit 0 /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
commas: parse arg ?; do jc=length(?)-3 to 1 by -3; ?=insert(',', ?, jc); end; return ?
/*──────────────────────────────────────────────────────────────────────────────────────*/
aPerm: procedure expose @.; parse arg n,i; nm=n-1; if n==0 then return 0
Line 831 ⟶ 1,925:
if i==0 then return 0
do m=i+1 while @.m<@.i; end /*m*/; parse value @.m @.i with @.i @.m
return 1</langsyntaxhighlight>
'''{{out|output''' |text=&nbsp; when using the default input: &nbsp; &nbsp; <tt> 7 </tt>}}
<pre>
length of superpermutation(0) = 0
length of superpermutation(1) = 1
length of superpermutation(2) = 3
length of superpermutation(3) = 9
length of superpermutation(4) = 35
length of superpermutation(5) = 183
length of superpermutation(6) = 1411 1,411
length of superpermutation(7) = 12137 12,137
</pre>
 
=={{header|Ruby}}==
===Non Recursive Version===
<langsyntaxhighlight lang="ruby">#A straight forward implementation of N. Johnston's algorithm. I prefer to look at this as 2n+1 where
#the second n is first n reversed, and the 1 is always the second symbol. This algorithm will generate
#just the left half of the result by setting l to [1,2] and looping from 3 to 6. For the purpose of
Line 867 ⟶ 1,961:
a.each{|n| print n}; puts "\n\n"
l = a
}</langsyntaxhighlight>
{{out}}
<pre>1
1
 
121
Line 880 ⟶ 1,973:
123451234152341253412354123145231425314235142315423124531243512431524312543121345213425134215342135421324513241532413524132541321453214352143251432154321
 
123456123451623451263451236451234651234156234152634152364152346152341652341256341253641253461253416253412653412356412354612354162354126354123654123145623145263145236145231645231465231425631425361425316425314625314265314235614235164235146235142635142365142315642315462315426315423615423165423124563124536124531624531264531246531243561243516243512643512463512436512431562431526431524631524361524316524312564312546312543612543162543126543121345621345261345216345213645213465213425613425163425136425134625134265134215634215364215346215342615342165342135642135462135426135421635421365421324561324516324513624513264513246513241563241536241532641532461532416532413562413526413524613524163524136524132564132546132541632541362541326541321456321453621453261453216453214653214356214352614352164352146352143652143256143251643251463251436251432651432156432154632154362154326154321654321</pre>
</pre>
 
===Recursive Version===
<langsyntaxhighlight lang="ruby">def superperm(n)
return [1] if n==1
superperm(n-1).each_cons(n-1).with_object([]) do |sub, ary|
Line 899 ⟶ 1,990:
print "%3d: len =%8d :" % [n, ary.size]
puts n<5 ? ary.join : to_16(ary.first(20)) + "...." + to_16(ary.last(20))
end</langsyntaxhighlight>
 
{{out}}
<pre>
1: len = 1 :1
2: len = 3 :121
Line 913 ⟶ 2,002:
9: len = 409113 :12345678912345678192....29187654321987654321
10: len = 4037913 :123456789a1234567891....1987654321a987654321
 
</pre>
=={{header|Scala}}==
<syntaxhighlight lang="scala">object SuperpermutationMinimisation extends App {
val nMax = 12
 
@annotation.tailrec
def factorial(number: Int, acc: Long = 1): Long =
if (number == 0) acc else factorial(number - 1, acc * number)
 
def factSum(n: Int): Long = (1 to n).map(factorial(_)).sum
 
for (n <- 0 until nMax) println(f"superPerm($n%2d) len = ${factSum(n)}%d")
 
}</syntaxhighlight>
 
=={{header|Sidef}}==
{{trans|Perl}}
<langsyntaxhighlight lang="ruby">for len in (1..8) {
var (pre="", post="")
@^len -> permutations {|*p|
Line 925 ⟶ 2,027:
}
printf("%2d: %8d %8d\n", len, pre.len, post.len)
}</langsyntaxhighlight>
{{out}}
<pre>
Line 936 ⟶ 2,038:
7: 10080 13699
8: 80640 109600
</pre>
 
=={{header|Wren}}==
{{trans|Kotlin}}
{{libheader|Wren-fmt}}
<syntaxhighlight lang="wren">import "./fmt" for Fmt
 
var max = 12
var sp = []
var count = List.filled(max, 0)
var pos = 0
 
var factSum = Fn.new { |n|
var s = 0
var x = 0
var f = 1
while (x < n) {
x = x + 1
f = f * x
s = s + f
}
return s
}
 
var r // recursive
r = Fn.new { |n|
if (n == 0) return false
var c = sp[pos - n]
count[n] = count[n] - 1
if (count[n] == 0) {
count[n] = n
if (!r.call(n - 1)) return false
}
sp[pos] = c
pos = pos + 1
return true
}
 
var superPerm = Fn.new { |n|
pos = n
var len = factSum.call(n)
if (len > 0) sp = List.filled(len, "\0")
for (i in 0..n) count[i] = i
if (n > 0) {
for (i in 1..n) sp[i - 1] = String.fromByte(48 + i)
}
while (r.call(n)) {}
}
 
for (n in 0...max) {
superPerm.call(n)
Fmt.print("superPerm($2d) len = $d", n, sp.count)
}</syntaxhighlight>
 
{{out}}
<pre>
superPerm( 0) len = 0
superPerm( 1) len = 1
superPerm( 2) len = 3
superPerm( 3) len = 9
superPerm( 4) len = 33
superPerm( 5) len = 153
superPerm( 6) len = 873
superPerm( 7) len = 5913
superPerm( 8) len = 46233
superPerm( 9) len = 409113
superPerm(10) len = 4037913
superPerm(11) len = 43954713
</pre>
 
=={{header|XPL0}}==
{{trans|C}}
Works on Raspberry Pi. ReallocMem is not supported in DOS versions.
<syntaxhighlight lang "XPL0">include xpllib; \for Print and StrLen
 
define Maxx = 12;
char Super;
int Pos, Cnt(Maxx);
 
func FactSum(N); \1! + 2! + ... + n!
int N, S, X, F;
[S:= 0; X:= 0; F:= 1;
while X < N do
[X:= X+1;
F:= F*X;
S:= S+F;
];
return S;
];
 
func R(N);
int N, C;
[if N = 0 then return false;
C:= Super(Pos - N);
Cnt(N):= Cnt(N)-1;
if Cnt(N) = 0 then
[Cnt(N):= N;
if R(N-1) = 0 then return false;
];
Super(Pos):= C; Pos:= Pos+1;
return true;
];
 
proc Superperm(N);
int N, I, Len;
[Pos:= N;
Len:= FactSum(N);
Super:= ReallocMem(Super, Len+1);
Super(Len):= 0;
for I:= 0 to N do Cnt(I):= I;
for I:= 1 to N do Super(I-1):= I+^0;
while R(N) do [];
];
 
int N;
[Super:= 0;
for N:= 0 to Maxx-1 do
[Print("Superperm(%d) ", N);
Superperm(N);
Print("len = %d", StrLen(Super));
\Uncomment next line to see the string itself
\Print(": %s", Super);
CrLf(0);
];
]</syntaxhighlight>
{{out}}
<pre>
Superperm(0) len = 0
Superperm(1) len = 1
Superperm(2) len = 3
Superperm(3) len = 9
Superperm(4) len = 33
Superperm(5) len = 153
Superperm(6) len = 873
Superperm(7) len = 5913
Superperm(8) len = 46233
Superperm(9) len = 409113
Superperm(10) len = 4037913
Superperm(11) len = 43954713
</pre>
 
Line 941 ⟶ 2,182:
{{trans|C}}
It crawls ...
<langsyntaxhighlight lang="zkl">const MAX = 12;
var super=Data(), pos, cnt; // global state, ick
Line 976 ⟶ 2,217:
//print(": %s".fmt(super.text));
println();
}</langsyntaxhighlight>
{{out}}
<pre>
PureFox
9,482

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/251549...352561"