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 two characters 'AB'.
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'.
A little thought will produce the shorter (in fact the shortest) superpermutation of 'ABA' - it contains 'AB' at the beginning and contains 'BA' from the middle to the end.
The "too obvious" method of creation generates a string of length N!*N. Using this as a yardstick, the task is to investigate other methods of generating superpermutations of N from 1-to-7 characters, that never generate larger superpermutations.
Show descriptions and comparisons of algorithms used here, and select the "Best" algorithm as being the one generating shorter superpermutations.
The problem of generating the shortest superpermutation for each Nmight be NP complete, although the minimal strings for small values of N have been found by brute -force searches.
-V MAX = 12[Char] spV count = [0] * MAXV pos = 0F factSum(n) V s = 0 V x = 0 V f = 1 L x < n f *= ++x s += f R sF 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 1BF 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))superPerm( 0) len = 0superPerm( 1) len = 1superPerm( 2) len = 3superPerm( 3) len = 9superPerm( 4) len = 33superPerm( 5) len = 153superPerm( 6) len = 873superPerm( 7) len = 5913superPerm( 8) len = 46233superPerm( 9) len = 409113superPerm(10) len = 4037913superPerm(11) len = 43954713
# syntax: GAWK -f SUPERPERMUTATION_MINIMISATION.AWK# converted from CBEGIN{arr[0]# prevents fatal: attempt to use scalar 'arr' as an arraylimit=11for(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 stringprintf("\n")}exit(0)}functionfact_sum(n,f,s,x){f=1s=x=0for(;x<n;){f*=++xs+=f}return(s)}functionsuper_perm(n,i,leng){deletearrpos=nleng=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)}functionr(n,c){if(!n){return(0)}c=arr[pos-n]if(!--cnt[n]){cnt[n]=nif(!r(n-1)){return(0)}}arr[pos++]=creturn(1)}
0 0 1 1 2 3 3 9 4 33 5 153 6 873 7 5913 8 46233 9 40911310 403791311 43954713
Finding a string whose length followsOEIS A007489. Complexity is the length of output string. It is known to benot optimal.
#include<stdio.h>#include<stdlib.h>#include<string.h>#define MAX 12char*super=0;intpos,cnt[MAX];// 1! + 2! + ... + n!intfact_sum(intn){ints,x,f;for(s=0,x=0,f=1;x<n;f*=++x,s+=f);returns;}intr(intn){if(!n)return0;charc=super[pos-n];if(!--cnt[n]){cnt[n]=n;if(!r(n-1))return0;}super[pos++]=c;return1;}voidsuperperm(intn){inti,len;pos=n;len=fact_sum(n);super=realloc(super,len+1);super[len]='\0';for(i=0;i<=n;i++)cnt[i]=i;for(i=1;i<=n;i++)super[i-1]=i+'0';while(r(n));}intmain(void){intn;for(n=0;n<MAX;n++){printf("superperm(%2d) ",n);superperm(n);printf("len = %d",(int)strlen(super));// uncomment next line to see the string itself// printf(": %s", super);putchar('\n');}return0;}
superperm( 0) len = 0superperm( 1) len = 1superperm( 2) len = 3superperm( 3) len = 9superperm( 4) len = 33superperm( 5) len = 153superperm( 6) len = 873superperm( 7) len = 5913superperm( 8) len = 46233superperm( 9) len = 409113superperm(10) len = 4037913superperm(11) len = 43954713
#include<array>#include<iostream>#include<vector>constexprintMAX=12;staticstd::vector<char>sp;staticstd::array<int,MAX>count;staticintpos=0;intfactSum(intn){ints=0;intx=0;intf=1;while(x<n){f*=++x;s+=f;}returns;}boolr(intn){if(n==0){returnfalse;}charc=sp[pos-n];if(--count[n]==0){count[n]=n;if(!r(n-1)){returnfalse;}}sp[pos++]=c;returntrue;}voidsuperPerm(intn){pos=n;intlen=factSum(n);if(len>0){sp.resize(len);}for(size_ti=0;i<=n;i++){count[i]=i;}for(size_ti=1;i<=n;i++){sp[i-1]='0'+i;}while(r(n)){}}intmain(){for(size_tn=0;n<MAX;n++){superPerm(n);std::cout<<"superPerm("<<n<<") len = "<<sp.size()<<'\n';}return0;}
superPerm(0) len = 0superPerm(1) len = 1superPerm(2) len = 3superPerm(3) len = 9superPerm(4) len = 33superPerm(5) len = 153superPerm(6) len = 873superPerm(7) len = 5913superPerm(8) len = 46233superPerm(9) len = 409113superPerm(10) len = 4037913superPerm(11) len = 43954713
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.
importstd.stdio,std.ascii,std.algorithm,core.memory,permutations2;/** Uses greedy algorithm of adding another char (or two, or three, ...)until an unseen perm is formed in the last n chars. */stringsuperpermutation(inuintn)nothrowin{assert(n>0&&n<uppercase.length);}out(result){// It's a superpermutation.assert(uppercase[0..n].dup.permutations.all!(p=>result.canFind(p)));}body{stringresult=uppercase[0..n];bool[constchar[]]toFind;GC.disable;foreach(constperm;result.dup.permutations)toFind[perm]=true;GC.enable;toFind.remove(result);autotrialPerm=newchar[n];autoauxAdd=newchar[n];while(toFind.length){MIDDLE:foreach(immutableskip;1..n){auxAdd[0..skip]=result[$-n..$-n+skip];foreach(consttrialAdd;auxAdd[0..skip].permutations!false){trialPerm[0..n-skip]=result[$+skip-n..$];trialPerm[n-skip..$]=trialAdd[];if(trialPermintoFind){result~=trialAdd;toFind.remove(trialPerm);breakMIDDLE;}}}}returnresult;}voidmain(){foreach(immutablen;1..8)n.superpermutation.length.writeln;}
139351649326247
Using the ldc2 compiler with n=10, it finds the result string of length 4_235_533 in less than 9 seconds.
From the C version with some improvements.
importstd.stdio,std.range,std.algorithm,std.ascii;enumuintnMax=12;__gsharedchar[]superperm;__gshareduintpos;__gshareduint[nMax]count;/// factSum(n) = 1! + 2! + ... + n!uintfactSum(inuintn)purenothrow@nogc@safe{returniota(1,n+1).map!(m=>reduce!q{a*b}(1u,iota(1,m+1))).sum;}boolr(inuintn)nothrow@nogc{if(!n)returnfalse;immutablec=superperm[pos-n];if(!--count[n]){count[n]=n;if(!r(n-1))returnfalse;}superperm[pos++]=c;returntrue;}voidsuperPerm(inuintn)nothrow{staticimmutablechars=digits~uppercase;staticassert(chars.length>=nMax);pos=n;superperm.length=factSum(n);foreach(immutablei;0..n+1)count[i]=i;foreach(immutablei;1..n+1)superperm[i-1]=chars[i];while(r(n)){}}voidmain(){foreach(immutablen;0..nMax){superPerm(n);writef("superPerm(%2d) len = %d",n,superperm.length);// Use -version=doPrint to see the string itself.version(doPrint)write(": ",superperm);writeln;}}
superPerm( 0) len = 0superPerm( 1) len = 1superPerm( 2) len = 3superPerm( 3) len = 9superPerm( 4) len = 33superPerm( 5) len = 153superPerm( 6) len = 873superPerm( 7) len = 5913superPerm( 8) len = 46233superPerm( 9) len = 409113superPerm(10) len = 4037913superPerm(11) len = 43954713
Run-time: about 0.40 seconds.
programSuperpermutation_minimisation;{$APPTYPE CONSOLE}usesSystem.SysUtils;constMax=12;varsuper:ansistring;pos:Integer;cnt:TArray<Integer>;functionfactSum(n:Integer):Uint64;beginvars:Uint64:=0;varf:=1;varx:=0;whilex<ndobegininc(x);f:=f*x;inc(s,f);end;Result:=s;end;functionr(n:Integer):Boolean;beginifn=0thenexit(false);varc:=super[pos-n];dec(cnt[n]);ifcnt[n]=0thenbegincnt[n]:=n;ifnotr(n-1)thenexit(false);end;super[pos]:=c;inc(pos);result:=true;end;procedureSuperPerm(n:Integer);beginvarpos:=n;varle:Uint64:=factSum(n);SetLength(super,le);forvari:=0tondocnt[i]:=i;forvari:=1tondosuper[i]:=ansichar(i+ord('0'));whiler(n)do;end;beginSetLength(cnt,max);forvarn:=0tomax-1dobeginwrite('superperm(',n:2,') ');SuperPerm(n);writeln('len = ',length(super));end;{$IFNDEF UNIX}readln;{$ENDIF}end.
defmoduleSuperpermutationdodefminimisation(1),do:[1]defminimisation(n)doEnum.chunk(minimisation(n-1),n-1,1)|>Enum.reduce({[],nil},fnsub,{acc,last}->ifEnum.uniq(sub)==subdoi=ifacc==[],do:0,else:Enum.find_index(sub,&(&1==last))+1{acc++(Enum.drop(sub,i)++[n]++sub),List.last(sub)}else{acc,last}endend)|>elem(0)endendto_s=fnlist->Enum.map_join(list,&Integer.to_string(&1,16))endEnum.each(1..8,fnn->result=Superpermutation.minimisation(n):io.format"~3w: len =~8w : ",[n,length(result)]IO.putsifn<5,do:Enum.join(result),else:to_s.(Enum.take(result,20))<>"...."<>to_s.(Enum.slice(result,-20..-1))end)
1: len = 1 : 1 2: len = 3 : 121 3: len = 9 : 123121321 4: len = 33 : 123412314231243121342132413214321 5: len = 153 : 12345123415234125341....14352143251432154321 6: len = 873 : 12345612345162345126....62154326154321654321 7: len = 5913 : 12345671234561723456....65432716543217654321 8: len = 46233 : 12345678123456718234....43281765432187654321
' version 28-06-2018' compile with: fbc -s consoleFunctionsuperpermsize(nAsUInteger)AsUIntegerDimAsUIntegerx,y,sum,facForx=1Tonfac=1Fory=1Toxfac*=yNextsum+=facNextFunction=sumEndFunctionFunctionsuperperm(nAsUInteger)AsStringIfn=1ThenReturn"1"DimAsStringsup_perm="1",insertDimAsStringp,q()DimAsUIntegera,b,i,l,xForx=2Toninsert=IIf(x<10,Str(x),Chr(x+55))l=Len(sup_perm)Ifl>1Thenl=Len(sup_perm)-x+2ReDimq(l)Fori=1Tolp=Mid(sup_perm,i,x-1)Ifx>2ThenFora=0ToLen(p)-2Forb=a+1ToLen(p)-1Ifp[a]=p[b]ThenContinueFor,For,ForNextNextEndIfq(i)=p+insert+pNextsup_perm=q(1)Fori=2ToUBound(q)a=x-1DoIfRight(sup_perm,a)=Left(q(i),a)Thensup_perm+=Mid(q(i),a+1)ExitDoEndIfa-=1LoopNextNextFunction=sup_permEndFunction' ------=< MAIN >=------DimAsStringsuperpermutationDimAsUIntegernForn=1To10superpermutation=superperm(n)PrintUsing"### ######## ######## ";n;superpermsize(n);Len(superpermutation);Ifn<5ThenPrintsuperpermutationElsePrintEndIfNext' empty keyboard bufferWhileInKey<>"":WendPrint:Print"hit any key to end program"SleepEnd
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
packagemainimport"fmt"constmax=12var(super[]byteposintcnt[max]int)// 1! + 2! + ... + n!funcfactSum(nint)int{s:=0forx,f:=0,1;x<n;{x++f*=xs+=f}returns}funcr(nint)bool{ifn==0{returnfalse}c:=super[pos-n]cnt[n]--ifcnt[n]==0{cnt[n]=nif!r(n-1){returnfalse}}super[pos]=cpos++returntrue}funcsuperperm(nint){pos=nle:=factSum(n)super=make([]byte,le)fori:=0;i<=n;i++{cnt[i]=i}fori:=1;i<=n;i++{super[i-1]=byte(i)+'0'}forr(n){}}funcmain(){forn:=0;n<max;n++{fmt.Printf("superperm(%2d) ",n)superperm(n)fmt.Printf("len = %d\n",len(super))}}
superperm( 0) len = 0superperm( 1) len = 1superperm( 2) len = 3superperm( 3) len = 9superperm( 4) len = 33superperm( 5) len = 153superperm( 6) len = 873superperm( 7) len = 5913superperm( 8) len = 46233superperm( 9) len = 409113superperm(10) len = 4037913superperm(11) len = 43954713
importstaticjava.util.stream.IntStream.rangeClosedclassSuperpermutation{finalstaticintnMax=12staticchar[]superpermstaticintposstaticint[]count=newint[nMax]staticintfactSum(intn){returnrangeClosed(1,n).map({m->rangeClosed(1,m).reduce(1,{a,b->a*b})}).sum()}staticbooleanr(intn){if(n==0){returnfalse}charc=superperm[pos-n]if(--count[n]==0){count[n]=nif(!r(n-1)){returnfalse}}superperm[pos++]=creturntrue}staticvoidsuperPerm(intn){Stringchars="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"pos=nsuperperm=newchar[factSum(n)]for(inti=0;i<n+1;i++){count[i]=i}for(inti=1;i<n+1;i++){superperm[i-1]=chars.charAt(i)}while(r(n)){}}staticvoidmain(String[]args){for(intn=0;n<nMax;n++){superPerm(n)printf("superPerm(%2d) len = %d",n,superperm.length)println()}}}
superPerm( 0) len = 0superPerm( 1) len = 1superPerm( 2) len = 3superPerm( 3) len = 9superPerm( 4) len = 33superPerm( 5) len = 153superPerm( 6) len = 873superPerm( 7) len = 5913superPerm( 8) len = 46233superPerm( 9) len = 409113superPerm(10) len = 4037913superPerm(11) len = 43954713
If there's an 872 long superpermutation for a six letter alphabet, this is not optimal.
approxmin=:3 :0seqs=.y{~(A.&i.~!)#yr=.{.seqsseqs=.}.seqswhile.#seqsdo.for_n.i.-#ydo.tail=.(-n){.rb=.tail-:"1n{."1seqsif.1e.bdo.j=.bi.1r=.r,n}.j{seqsseqs=.(<<<j){seqsbreak.end.end.end.r)
Some sequence lengths:
(#,#@approxmin)@>(1+i.8){.&.><'abcdefghijk'1123394335153687375913846233
import staticjava.util.stream.IntStream.rangeClosed;publicclassTest{finalstaticintnMax=12;staticchar[]superperm;staticintpos;staticint[]count=newint[nMax];staticintfactSum(intn){returnrangeClosed(1,n).map(m->rangeClosed(1,m).reduce(1,(a,b)->a*b)).sum();}staticbooleanr(intn){if(n==0)returnfalse;charc=superperm[pos-n];if(--count[n]==0){count[n]=n;if(!r(n-1))returnfalse;}superperm[pos++]=c;returntrue;}staticvoidsuperPerm(intn){Stringchars="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";pos=n;superperm=newchar[factSum(n)];for(inti=0;i<n+1;i++)count[i]=i;for(inti=1;i<n+1;i++)superperm[i-1]=chars.charAt(i);while(r(n)){}}publicstaticvoidmain(String[]args){for(intn=0;n<nMax;n++){superPerm(n);System.out.printf("superPerm(%2d) len = %d",n,superperm.length);System.out.println();}}}
superPerm( 0) len = 0superPerm( 1) len = 1superPerm( 2) len = 3superPerm( 3) len = 9superPerm( 4) len = 33superPerm( 5) len = 153superPerm( 6) len = 873superPerm( 7) len = 5913superPerm( 8) len = 46233superPerm( 9) len = 409113superPerm(10) len = 4037913superPerm(11) len = 43954713
constnMax=12;letsuperperm;letpos;letcount=newArray(nMax);functionfactSum(n){letsum=0;for(letm=1;m<=n;m++){letfactorial=1;for(leti=1;i<=m;i++){factorial*=i;}sum+=factorial;}returnsum;}functionr(n){if(n===0){returnfalse;}constc=superperm[pos-n];if(--count[n]===0){count[n]=n;if(!r(n-1)){returnfalse;}}superperm[pos++]=c;returntrue;}functionsuperPerm(n){constchars="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";pos=n;superperm=newArray(factSum(n));for(leti=0;i<n+1;i++){count[i]=i;}for(leti=1;i<n+1;i++){superperm[i-1]=chars.charAt(i);}while(r(n)){// Continue until r(n) returns false}}functionmain(){for(letn=0;n<nMax;n++){superPerm(n);console.log(`superPerm(${n.toString().padStart(2,' ')}) len =${superperm.length}`);}}// Run the main functionmain();
superPerm( 0) len = 0superPerm( 1) len = 1superPerm( 2) len = 3superPerm( 3) len = 9superPerm( 4) len = 33superPerm( 5) len = 153superPerm( 6) len = 873superPerm( 7) len = 5913superPerm( 8) len = 46233superPerm( 9) len = 409113superPerm(10) len = 4037913superPerm(11) len = 43954713
Runs in about 1/4 second.
constnmax=12functionr!(n,s,pos,count)ifn==0returnfalseendc=s[pos+1-n]count[n+1]-=1ifcount[n+1]==0count[n+1]=nifr!(n-1,s,pos,count)==0returnfalseendends[pos+1]=cpos+=1trueendfunctionsuperpermutation(n)count=zeros(nmax)pos=nsuperperm=zeros(UInt8,n<2?n:mapreduce(factorial,+,1:n))foriin0:n-1count[i+1]=isuperperm[i+1]=Char(i+'0')endcount[n+1]=nwhiler!(n,superperm,pos,count);endsuperpermendfunctiontestsuper(N,verbose=false)foriin0:N-1s=superpermutation(i)println("Superperm($i) has length$(length(s)) ",(verbose?String(s):""))endendtestsuper(nmax)
Superperm(0) has length 0Superperm(1) has length 1Superperm(2) has length 3Superperm(3) has length 9Superperm(4) has length 33Superperm(5) has length 153Superperm(6) has length 873Superperm(7) has length 5913Superperm(8) has length 46233Superperm(9) has length 409113Superperm(10) has length 4037913Superperm(11) has length 43954713
// version 1.1.2constvalMAX=12varsp=CharArray(0)valcount=IntArray(MAX)varpos=0funfactSum(n:Int):Int{vars=0varx=0varf=1while(x<n){f*=++xs+=f}returns}funr(n:Int):Boolean{if(n==0)returnfalsevalc=sp[pos-n]if(--count[n]==0){count[n]=nif(!r(n-1))returnfalse}sp[pos++]=creturntrue}funsuperPerm(n:Int){pos=nvallen=factSum(n)if(len>0)sp=CharArray(len)for(iin0..n)count[i]=ifor(iin1..n)sp[i-1]='0'+iwhile(r(n)){}}funmain(args:Array<String>){for(nin0untilMAX){superPerm(n)println("superPerm(${"%2d".format(n)}) len = ${sp.size}")}}
superPerm( 0) len = 0superPerm( 1) len = 1superPerm( 2) len = 3superPerm( 3) len = 9superPerm( 4) len = 33superPerm( 5) len = 153superPerm( 6) len = 873superPerm( 7) len = 5913superPerm( 8) len = 46233superPerm( 9) len = 409113superPerm(10) len = 4037913superPerm(11) len = 43954713
Greedy algorithm:
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}]
{1,1}{2,3}{3,9}{4,33}{5,153}{6,873}{7,5913}importstrformatconstMAX=12varsuper:seq[char]=@[]varpos:intvarcnt:array[MAX,int]procfactSum(n:int):int=vars,x=0varf=1whilex<n:incxf*=xincs,fsprocr(n:int):bool=ifn==0:returnfalsevarc=super[pos-n]deccnt[n]ifcnt[n]==0:cnt[n]=nifnotr(n-1):returnfalsesuper[pos]=cincpostrueprocsuperperm(n:int)=pos=nvarle=factSum(n)super.setLen(le)foriin0..n:cnt[i]=iforiin1..n:super[i-1]=char(i+ord('0'))whiler(n):discardfornin0..<MAX:write(stdout,fmt"superperm({n:2})")superperm(n)writeLine(stdout,fmt" len = {len(super)}")
superperm( 0) len = 0superperm( 1) len = 1superperm( 2) len = 3superperm( 3) len = 9superperm( 4) len = 33superperm( 5) len = 153superperm( 6) len = 873superperm( 7) len = 5913superperm( 8) len = 46233superperm( 9) len = 409113superperm(10) len = 4037913superperm(11) len = 43954713
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); }}superperm(0) len = 0superperm(1) len = 1superperm(2) len = 3superperm(3) len = 9superperm(4) len = 33superperm(5) len = 153superperm(6) len = 873superperm(7) len = 5913superperm(8) len = 46233superperm(9) len = 409113superperm(10) len = 4037913superperm(11) len = 43954713
This uses a naive method of just concatenating the new permutation to the end (or prepending to the front) if it is not already in the string. Adding to the end is similar to Python'ss_perm1() function.
usentheoryqw/forperm/;formy$len(1..8){my($pre,$post,$t)=("","");forperm{$t=join"",@_;$post.=$tunlessindex($post,$t)>=0;$pre=$t.$preunlessindex($pre,$t)>=0;}$len;printf"%2d: %8d %8d\n",$len,length($pre),length($post);}
1: 1 1 2: 4 4 3: 12 15 4: 48 64 5: 240 325 6: 1440 1956 7: 10080 13699 8: 80640 109600
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.
withjavascript_semanticsconstantnMax=iff(platform()=JS?8:12)-- 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.atomt0=time()stringsuperpermsequencecountintegerposfunctionfactSum(intn)integers=0,f=1fori=1tondof*=is+=fendforreturnsendfunctionfunctionr(intn)if(n==0)thenreturnfalseendifintegerc=superperm[pos-n+1]count[n]-=1ifcount[n]=0thencount[n]=nifnotr(n-1)thenreturnfalseendifendifpos+=1superperm[pos]=creturntrueendfunctionproceduresuperPerm(intn)stringchars="123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"[1..n]pos=nsuperperm=chars&repeat(' ',factSum(n)-n)count=tagset(n)whiler(n)doendwhileifn=0thenifsuperperm!=""then?9/0endifelsifn<=7then-- (I estimate it would take at least 5 days to validate -- superPerm(12), feel free to try it on your own time)fori=1tofactorial(n)doifnotmatch(permute(i,chars),superperm)then?9/0endifendforendifendprocedureforn=0tonMaxdosuperPerm(n)integerl=length(superperm)ifl>40thensuperperm[20..-20]="..."endifstringe=elapsed(time()-t0)printf(1,"superPerm(%2d) len = %d %s (%s)\n",{n,l,superperm,e})endfor
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)
Finds the longest overlap, similar to Python's greedy s_perm0 but theoretically more efficient.
I also tried prefixing res with any longer overlap at the start, but it just made things worse.
Uses factSum() from above, and compares that with these results (which are always worse for >3).
withjavascript_semanticsfunctionfactSum(intn)integers=0,f=1fori=1tondof*=is+=fendforreturnsendfunctionproceduresuperPerm(intn)atomt0=time()stringchars="123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"[1..n]integerf=factorial(n)sequenceperms=repeat("",f)fori=1tofdoperms[i]=permute(i,chars)endforstringres=perms[$]perms=perms[1..$-1]whilelength(perms)dointegerbest=0,bi=length(perms)fori=1tolength(perms)dostringpi=perms[i]integerm=length(res),k=find(res[m],pi)forl=kto1by-1doifres[m]!=pi[l]thenk=0exitendifm-=1endforifk>bestthenbest=kbi=iendifendforifmatch(perms[bi],res)then?9/0-- (sanity check)elseres&=perms[bi][best+1..$]endifperms[bi]=perms[$]perms=perms[1..$-1]endwhileintegerlr=length(res),fsn=factSum(n)stringop={"<","=",">"}[compare(lr,fsn)+2]t0=time()-t0stringe=iff(t0>1?", "&elapsed(t0):"")printf(1,"superPerm(%d) len = %d (%s%d%s)\n",{n,lr,op,fsn,e})endprocedureforn=1to7do-- (note: 8 takes 65x longer than 7)superPerm(n)endfor
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)
EnableExplicit#MAX=10Declare.ifact_sum(n.i):Declare.ir(n.i):Declaresuperperm(n.i)Globalpos.i,Dimcnt.i(#MAX),Dimsuper.s{1}(fact_sum(#MAX))IfOpenConsole();-MAIN:Superpermutation_minimisationDefine.inForn=0To#MAXsuperperm(n):Print("superperm("+RSet(Str(n),2)+") len = "+LSet(Str(pos),10))Ifn<=4:Print(~"\t"+PeekS(@super(),pos)):EndIfPrintN("")NextInput()EndIfEnd;-END:Superpermutation_minimisationProcedure.ifact_sum(n.i)Define.is=0,f=1,x=0Whilex<n:x+1:f*x:s+f:WendProcedureReturnsEndProcedureProcedure.ir(n.i)IfNotn:ProcedureReturn0:EndIfDefinec.s{1}=super(pos-n)cnt(n)-1IfNotcnt(n)cnt(n)=nIfNotr(n-1):ProcedureReturn0:EndIfEndIfsuper(pos)=c:pos+1:ProcedureReturn1EndProcedureProceduresuperperm(n.i)pos=nDefine.ilen=fact_sum(n),iFori=0Ton:cnt(i)=i:NextFori=1Ton:super(i-1)=Chr('0'+i) : NextWhiler(n):WendEndProcedure
superperm( 0) len = 0 superperm( 1) len = 1 1superperm( 2) len = 3 121superperm( 3) len = 9 123121321superperm( 4) len = 33 123412314231243121342132413214321superperm( 5) len = 153 superperm( 6) len = 873 superperm( 7) len = 5913 superperm( 8) len = 46233 superperm( 9) len = 409113 superperm(10) len = 4037913
"Generate a short Superpermutation of n characters A... as a string using various algorithms."from__future__importprint_function,divisionfromitertoolsimportpermutationsfrommathimportfactorialimportstringimportdatetimeimportgcMAXN=7defs_perm0(n):""" Uses greedy algorithm of adding another char (or two, or three, ...) until an unseen perm is formed in the last n chars """allchars=string.ascii_uppercase[:n]allperms=[''.join(p)forpinpermutations(allchars)]sp,tofind=allperms[0],set(allperms[1:])whiletofind:forskipinrange(1,n):fortrial_addin(''.join(p)forpinpermutations(sp[-n:][:skip])):#print(sp, skip, trial_add)trial_perm=(sp+trial_add)[-n:]iftrial_permintofind:#print(sp, skip, trial_add)sp+=trial_addtofind.discard(trial_perm)trial_add=None# Sentinelbreakiftrial_addisNone:breakassertall(perminspforperminallperms)# Check it is a superpermutationreturnspdefs_perm1(n):""" Uses algorithm of concatenating all perms in order if not already part of concatenation. """allchars=string.ascii_uppercase[:n]allperms=[''.join(p)forpinsorted(permutations(allchars))]perms,sp=allperms[::],''whileperms:nxt=perms.pop()ifnxtnotinsp:sp+=nxtassertall(perminspforperminallperms)returnspdefs_perm2(n):""" Uses algorithm of concatenating all perms in order first-last-nextfirst- nextlast... if not already part of concatenation. """allchars=string.ascii_uppercase[:n]allperms=[''.join(p)forpinsorted(permutations(allchars))]perms,sp=allperms[::],''whileperms:nxt=perms.pop(0)ifnxtnotinsp:sp+=nxtifperms:nxt=perms.pop(-1)ifnxtnotinsp:sp+=nxtassertall(perminspforperminallperms)returnspdef_s_perm3(n,cmp):""" Uses algorithm of concatenating all perms in order first, next_with_LEASTorMOST_chars_in_same_position_as_last_n_chars, ... """allchars=string.ascii_uppercase[:n]allperms=[''.join(p)forpinsorted(permutations(allchars))]perms,sp=allperms[::],''whileperms:lastn=sp[-n:]nxt=cmp(perms,key=lambdapm:sum((ch1==ch2)forch1,ch2inzip(pm,lastn)))perms.remove(nxt)ifnxtnotinsp:sp+=nxtassertall(perminspforperminallperms)returnspdefs_perm3_max(n):""" Uses algorithm of concatenating all perms in order first, next_with_MOST_chars_in_same_position_as_last_n_chars, ... """return_s_perm3(n,max)defs_perm3_min(n):""" Uses algorithm of concatenating all perms in order first, next_with_LEAST_chars_in_same_position_as_last_n_chars, ... """return_s_perm3(n,min)longest=[factorial(n)*nforninrange(MAXN+1)]weight,runtime={},{}print(__doc__)foralgoin[s_perm0,s_perm1,s_perm2,s_perm3_max,s_perm3_min]:print('\n###\n###%s\n###'%algo.__name__)print(algo.__doc__)weight[algo.__name__],runtime[algo.__name__]=1,datetime.timedelta(0)forninrange(1,MAXN+1):gc.collect()gc.disable()t=datetime.datetime.now()sp=algo(n)t=datetime.datetime.now()-tgc.enable()runtime[algo.__name__]+=tlensp=len(sp)wt=(lensp/longest[n])**2print(' For N=%i: SP length%5i Max:%5i Weight:%5.2f'%(n,lensp,longest[n],wt))weight[algo.__name__]*=wtweight[algo.__name__]**=1/n# Geometric meanweight[algo.__name__]=1/weight[algo.__name__]print('%*s Overall Weight:%5.2f in%.1f seconds.'%(29,'',weight[algo.__name__],runtime[algo.__name__].total_seconds()))print('\n###\n### Algorithms ordered by shortest superpermutations first\n###')print('\n'.join('%12s (%.3f)'%kvforkvinsorted(weight.items(),key=lambdakeyvalue:-keyvalue[1])))print('\n###\n### Algorithms ordered by shortest runtime first\n###')print('\n'.join('%12s (%.3f)'%(k,v.total_seconds())fork,vinsorted(runtime.items(),key=lambdakeyvalue:keyvalue[1])))
Generate a short Superpermutation of n characters A... as a string using various algorithms.###### s_perm0### Uses greedy algorithm of adding another char (or two, or three, ...) until an unseen perm is formed in the last n chars For N=1: SP length 1 Max: 1 Weight: 1.00 For N=2: SP length 3 Max: 4 Weight: 0.56 For N=3: SP length 9 Max: 18 Weight: 0.25 For N=4: SP length 35 Max: 96 Weight: 0.13 For N=5: SP length 164 Max: 600 Weight: 0.07 For N=6: SP length 932 Max: 4320 Weight: 0.05 For N=7: SP length 6247 Max: 35280 Weight: 0.03 Overall Weight: 6.50 in 0.1 seconds.###### s_perm1### Uses algorithm of concatenating all perms in order if not already part of concatenation. For N=1: SP length 1 Max: 1 Weight: 1.00 For N=2: SP length 4 Max: 4 Weight: 1.00 For N=3: SP length 15 Max: 18 Weight: 0.69 For N=4: SP length 64 Max: 96 Weight: 0.44 For N=5: SP length 325 Max: 600 Weight: 0.29 For N=6: SP length 1956 Max: 4320 Weight: 0.21 For N=7: SP length 13699 Max: 35280 Weight: 0.15 Overall Weight: 2.32 in 0.1 seconds.###### s_perm2### Uses algorithm of concatenating all perms in order first-last-nextfirst- nextlast... if not already part of concatenation. For N=1: SP length 1 Max: 1 Weight: 1.00 For N=2: SP length 4 Max: 4 Weight: 1.00 For N=3: SP length 15 Max: 18 Weight: 0.69 For N=4: SP length 76 Max: 96 Weight: 0.63 For N=5: SP length 420 Max: 600 Weight: 0.49 For N=6: SP length 3258 Max: 4320 Weight: 0.57 For N=7: SP length 24836 Max: 35280 Weight: 0.50 Overall Weight: 1.49 in 0.3 seconds.###### s_perm3_max### Uses algorithm of concatenating all perms in order first, next_with_MOST_chars_in_same_position_as_last_n_chars, ... For N=1: SP length 1 Max: 1 Weight: 1.00 For N=2: SP length 4 Max: 4 Weight: 1.00 For N=3: SP length 15 Max: 18 Weight: 0.69 For N=4: SP length 56 Max: 96 Weight: 0.34 For N=5: SP length 250 Max: 600 Weight: 0.17 For N=6: SP length 1482 Max: 4320 Weight: 0.12 For N=7: SP length 10164 Max: 35280 Weight: 0.08 Overall Weight: 3.06 in 50.2 seconds.###### s_perm3_min### Uses algorithm of concatenating all perms in order first, next_with_LEAST_chars_in_same_position_as_last_n_chars, ... For N=1: SP length 1 Max: 1 Weight: 1.00 For N=2: SP length 4 Max: 4 Weight: 1.00 For N=3: SP length 15 Max: 18 Weight: 0.69 For N=4: SP length 88 Max: 96 Weight: 0.84 For N=5: SP length 540 Max: 600 Weight: 0.81 For N=6: SP length 3930 Max: 4320 Weight: 0.83 For N=7: SP length 33117 Max: 35280 Weight: 0.88 Overall Weight: 1.16 in 49.8 seconds.###### Algorithms ordered by shortest superpermutations first### s_perm0 (6.501) s_perm3_max (3.057) s_perm1 (2.316) s_perm2 (1.494) s_perm3_min (1.164)###### Algorithms ordered by shortest runtime first### s_perm0 (0.099) s_perm1 (0.102) s_perm2 (0.347) s_perm3_min (49.764) s_perm3_max (50.192)
fromarrayimportarrayfromstringimportascii_uppercase,digitsfromoperatorimportmultry:importpsycopsyco.full()except:passN_MAX=12# fact_sum(n) = 1! + 2! + ... + n!deffact_sum(n):returnsum(reduce(mul,xrange(1,m+1),1)forminxrange(1,n+1))defr(n,superperm,pos,count):ifnotn:returnFalsec=superperm[pos-n]count[n]-=1ifnotcount[n]:count[n]=nifnotr(n-1,superperm,pos,count):returnFalsesuperperm[pos]=cpos+=1returnTruedefsuper_perm(n,superperm,pos,count,chars=digits+ascii_uppercase):assertlen(chars)>=N_MAXpos=nsuperperm+=array("c"," ")*(fact_sum(n)-len(superperm))foriinxrange(n+1):count[i]=iforiinxrange(1,n+1):superperm[i-1]=chars[i]whiler(n,superperm,pos,count):passdefmain():superperm=array("c","")pos=0count=array("l",[0])*N_MAXforninxrange(N_MAX):super_perm(n,superperm,pos,count)print"Super perm(%2d) len =%d"%(n,len(superperm)),#print superperm.tostring(),printmain()
It is four times slower than the D entry. The output is about the same as the D entry.
#langracket/base(requireracket/listracket/format)(define(index-of1xl)(for/first((i(in-naturals1))(m(in-listl))#:when(equal?mx))i))(define(sprprmn)(definen-1(-n1))(definesp:n-1(superpermn-1))(letloop((subs(letloop((spsp:n-1)(i(-(lengthsp:n-1)n-1-1))(rvnull))(cond[(zero?i)(reverserv)][else(definesub(takespn-1))(loop(cdrsp)(-i1)(if(check-duplicatessub)rv(conssubrv)))])))(arynull))(if(null?subs)ary(let((sub(carsubs)))(definei(if(null?ary)0(index-of1(lastary)sub)))(loop(cdrsubs)(appendary(dropsubi)(listn)sub))))))(definesuperperm(let((hsh(make-hash(list(cons1(list1))))))(lambda(n)(hash-ref!hshn(lambda()(sprprmn))))))(define(20..20ary)(if(<(lengthary)41)ary(append(takeary20)(cons'..(take-rightary20)))))(for*((n(in-range1(add18)))(ary(in-value(superpermn))))(printf"~a: len = ~a : ~a~%"(~an#:width3)(~a(lengthary)#:width8)(20..20ary)))
1 : len = 1 : (1)2 : len = 3 : (1 2 1)3 : len = 9 : (1 2 3 1 2 1 3 2 1)4 : len = 33 : (1 2 3 4 1 2 3 1 4 2 3 1 2 4 3 1 2 1 3 4 2 1 3 2 4 1 3 2 1 4 3 2 1)5 : len = 153 : (1 2 3 4 5 1 2 3 4 1 5 2 3 4 1 2 5 3 4 1 .. 1 4 3 5 2 1 4 3 2 5 1 4 3 2 1 5 4 3 2 1)6 : len = 873 : (1 2 3 4 5 6 1 2 3 4 5 1 6 2 3 4 5 1 2 6 .. 6 2 1 5 4 3 2 6 1 5 4 3 2 1 6 5 4 3 2 1)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)
(formerly Perl 6)
for1..8 ->$len {my$pre =my$post =my$t ='';for ('a'..'z')[^$len].permutations ->@p {$t =@p.join('');$post ~=$tunlessindex($post,$t);$pre =$t ~$preunlessindex($pre,$t); }printf"%1d: %8d %8d\n",$len,$pre.chars,$post.chars;}
1: 1 12: 4 43: 12 154: 48 645: 240 3256: 1440 19567: 10080 136998: 80640 109600
This REXX version just does simple finds for the permutations.
/*REXX program attempts to find better minimizations for computing superpermutations.*/parseargcycles./*obtain optional arguments from the CL*/ifcycles==''|cycles==","thencycles=7/*Not specified? Then use the default.*/don=0tocycles#=0;$.=/*populate the first permutation. */dopop=1forn;@.pop=d2x(pop);$.0=$.0||@.popend/*pop*/dowhileaPerm(n,0)ifn\==0then#=#+1;$.#=doj=1forn;$.#=$.#||@.jend/*j*/end/*while*/z=$.0nm=n-1dop=1for#;if$.j==''theniterateifpos($.p,z)\==0theniterateparsevar$.ph2R1L=(n)ifleft(z,nm)==Rthendo;z=h||z;iterate;endifright(z,1)==hthendo;z=z||R;iterate;endz=z||$.pend/*p*//* [↑] more IFs could be added for opt*/L=commas(length(z))say'length of superpermutation('n") ="right(L,max(length(L),cycles+2))end/*cycle*/exit0/*stick a fork in it, we're all done. *//*──────────────────────────────────────────────────────────────────────────────────────*/commas:parsearg?;dojc=length(?)-3to1by-3;?=insert(',',?,jc);end;return?/*──────────────────────────────────────────────────────────────────────────────────────*/aPerm:procedureexpose@.;parseargn,i;nm=n-1;ifn==0thenreturn0dok=nmby-1fornm;kp=k+1;if@.k<@.kpthendo;i=k;leave;end;end/*k*/doj=i+1whilej<n;parsevalue@.j@.nwith@.n@.j;n=n-1;end/*j*/ifi==0thenreturn0dom=i+1while@.m<@.i;end/*m*/;parsevalue@.m@.iwith@.i@.mreturn1
length of superpermutation(0) = 0length of superpermutation(1) = 1length of superpermutation(2) = 2length of superpermutation(3) = 9length of superpermutation(4) = 50length of superpermutation(5) = 302length of superpermutation(6) = 1,922length of superpermutation(7) = 13,652length of superpermutation(8) = 109,538
/*REXX program attempts to find better minimizations for computing superpermutations.*/parseargcycles./*obtain optional arguments from the CL*/ifcycles==''|cycles==","thencycles=7/*Not specified? Then use the default.*/don=0tocycles#=0;$.=/*populate the first permutation. */dopop=1forn;@.pop=d2x(pop);$.0=$.0||@.popend/*pop*/dowhileaPerm(n,0);ifn\==0then#=#+1;$.#=doj=1forn;$.#=$.#||@.jend/*j*/end/*while*/z=$.0c=0/*count of found permutations (so far).*/doj=1whilec\==#ifj>#thendo;c=c+1/*exhausted finds and shortcuts; concat*/z=z||$.j;$.j=j=1endif$.j==''theniterate/*Already found? Then ignore this perm.*/ifpos($.j,z)\==0thendo;c=c+1;$.j=iterateenddok=n-1to1by-1/*handle the shortcuts in perm finding.*/ifsubstr($.j,k)==left(z,k)thendo;c=c+1/*found rightish shortcut*/z=left($.j,k-1)||z;$.j=iteratejendifleft($.j,k)==right(z,k)thendo;c=c+1/*found leftish shortcut*/z=z||substr($.j,k+1);$.j=iteratejendend/*k*//* [↑] more IFs could be added for opt*/end/*j*/L=commas(length(z))say'length of superpermutation('n") ="right(L,max(length(L),cycles+2))end/*n*/exit0/*stick a fork in it, we're all done. *//*──────────────────────────────────────────────────────────────────────────────────────*/commas:parsearg?;dojc=length(?)-3to1by-3;?=insert(',',?,jc);end;return?/*──────────────────────────────────────────────────────────────────────────────────────*/aPerm:procedureexpose@.;parseargn,i;nm=n-1;ifn==0thenreturn0dok=nmby-1fornm;kp=k+1;if@.k<@.kpthendo;i=k;leave;end;end/*k*/doj=i+1whilej<n;parsevalue@.j@.nwith@.n@.j;n=n-1;end/*j*/ifi==0thenreturn0dom=i+1while@.m<@.i;end/*m*/;parsevalue@.m@.iwith@.i@.mreturn1
length of superpermutation(0) = 0length of superpermutation(1) = 1length of superpermutation(2) = 3length of superpermutation(3) = 9length of superpermutation(4) = 35length of superpermutation(5) = 183length of superpermutation(6) = 1,411length of superpermutation(7) = 12,137
#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#this task I am going to start from an empty array and generate the whole strings using just the#rules.##Nigel Galloway: December 16th., 2014#l=[](1..6).each{|e|a,i=[],e-2(0..l.length-e+1).each{|g|ifnot(n=l[g..g+e-2]).uniq!a.concat(n[(a[0]?i:0)..-1]).push(e).concat(n)i=e-2elsei-=1end}a.each{|n|printn};puts"\n\n"l=a}
1121123121321123412314231243121342132413214321123451234152341253412354123145231425314235142315423124531243512431524312543121345213425134215342135421324513241532413524132541321453214352143251432154321123456123451623451263451236451234651234156234152634152364152346152341652341256341253641253461253416253412653412356412354612354162354126354123654123145623145263145236145231645231465231425631425361425316425314625314265314235614235164235146235142635142365142315642315462315426315423615423165423124563124536124531624531264531246531243561243516243512643512463512436512431562431526431524631524361524316524312564312546312543612543162543126543121345621345261345216345213645213465213425613425163425136425134625134265134215634215364215346215342615342165342135642135462135426135421635421365421324561324516324513624513264513246513241563241536241532641532461532416532413562413526413524613524163524136524132564132546132541632541362541326541321456321453621453261453216453214653214356214352614352164352146352143652143256143251643251463251436251432651432156432154632154362154326154321654321
defsuperperm(n)return[1]ifn==1superperm(n-1).each_cons(n-1).with_object([])do|sub,ary|nextifsub.uniq!i=ary.empty??0:sub.index(ary.last)+1ary.concat(sub[i..-1]+[n]+sub)endenddefto_16(a)a.map{|x|x.to_s(16)}.joinendfornin1..10ary=superperm(n)print"%3d: len =%8d :"%[n,ary.size]putsn<5?ary.join:to_16(ary.first(20))+"...."+to_16(ary.last(20))end
1: len = 1 :1 2: len = 3 :121 3: len = 9 :123121321 4: len = 33 :123412314231243121342132413214321 5: len = 153 :12345123415234125341....14352143251432154321 6: len = 873 :12345612345162345126....62154326154321654321 7: len = 5913 :12345671234561723456....65432716543217654321 8: len = 46233 :12345678123456718234....43281765432187654321 9: len = 409113 :12345678912345678192....2918765432198765432110: len = 4037913 :123456789a1234567891....1987654321a987654321
constMAX:usize=12;// 1! + 2! + ... + n!fnfact_sum(n:usize)->usize{letmutsum=0_usize;letmutfact=1_usize;letmutx=0_usize;whilex<n{x+=1;fact*=x;sum+=fact;}returnsum;}fnr(n:usize,sup:&mutVec<u8>,pos:&mutusize,cnt:&mutVec<usize>)->bool{ifn==0{returnfalse;}letc=sup[*pos-n];cnt[n]-=1;ifcnt[n]==0{cnt[n]=n;if!r(n-1,sup,pos,cnt){returnfalse;}}sup[*pos]=c;*pos+=1;returntrue;}fnsuperperm(n:usize,sup:&mutVec<u8>,pos:&mutusize,cnt:&mutVec<usize>)->usize{*pos=n;letnew_len=fact_sum(n);sup.resize(new_len,0);foriin0..=n{cnt[i]=i;}foriin1..=n{sup[i-1]=(iasu8)+('0'asu8);}whiler(n,sup,pos,cnt){}returnsup.len();}fnmain(){letsup:&mutVec<u8>=&mut[0_u8;0].to_vec();letpos:&mutusize=&mut0_usize;letcnt:&mutVec<usize>=&mut[0_usize;MAX].to_vec();fornin0..MAX{println!("superperm of {:<2} has a length of {}",n,superperm(n,sup,pos,cnt));}}
superperm of 0 has a length of 0superperm of 1 has a length of 1superperm of 2 has a length of 3superperm of 3 has a length of 9superperm of 4 has a length of 33superperm of 5 has a length of 153superperm of 6 has a length of 873superperm of 7 has a length of 5913superperm of 8 has a length of 46233superperm of 9 has a length of 409113superperm of 10 has a length of 4037913superperm of 11 has a length of 43954713
objectSuperpermutationMinimisationextendsApp{valnMax=12@annotation.tailrecdeffactorial(number:Int,acc:Long=1):Long=if(number==0)accelsefactorial(number-1,acc*number)deffactSum(n:Int):Long=(1ton).map(factorial(_)).sumfor(n<-0untilnMax)println(f"superPerm($n%2d) len =${factSum(n)}%d")}
forlenin(1..8){var(pre="",post="")@^len->permutations{|*p|vart=p.joinpost.append!(t)if !post.contains(t)pre.prepend!(t)if !pre.contains(t)}printf("%2d: %8d %8d\n",len,pre.len,post.len)}
1: 1 1 2: 4 4 3: 12 15 4: 48 64 5: 240 325 6: 1440 1956 7: 10080 13699 8: 80640 109600
import"./fmt"forFmtvarmax=12varsp=[]varcount=List.filled(max,0)varpos=0varfactSum=Fn.new{|n|vars=0varx=0varf=1while(x<n){x=x+1f=f*xs=s+f}returns}varr// recursiver=Fn.new{|n|if(n==0)returnfalsevarc=sp[pos-n]count[n]=count[n]-1if(count[n]==0){count[n]=nif(!r.call(n-1))returnfalse}sp[pos]=cpos=pos+1returntrue}varsuperPerm=Fn.new{|n|pos=nvarlen=factSum.call(n)if(len>0)sp=List.filled(len,"\0")for(iin0..n)count[i]=iif(n>0){for(iin1..n)sp[i-1]=String.fromByte(48+i)}while(r.call(n)){}}for(nin0...max){superPerm.call(n)Fmt.print("superPerm($2d) len = $d",n,sp.count)}
superPerm( 0) len = 0superPerm( 1) len = 1superPerm( 2) len = 3superPerm( 3) len = 9superPerm( 4) len = 33superPerm( 5) len = 153superPerm( 6) len = 873superPerm( 7) len = 5913superPerm( 8) len = 46233superPerm( 9) len = 409113superPerm(10) len = 4037913superPerm(11) len = 43954713
Works on Raspberry Pi. ReallocMem is not supported in DOS versions.
include xpllib; \for Print and StrLendefine 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); ];]Superperm(0) len = 0Superperm(1) len = 1Superperm(2) len = 3Superperm(3) len = 9Superperm(4) len = 33Superperm(5) len = 153Superperm(6) len = 873Superperm(7) len = 5913Superperm(8) len = 46233Superperm(9) len = 409113Superperm(10) len = 4037913Superperm(11) len = 43954713
It crawls ...
const MAX = 12;var super=Data(), pos, cnt; // global state, ick fcn fact_sum(n){ // -->1! + 2! + ... + n! [1..n].reduce(fcn(s,n){ s + [2..n].reduce('*,1) },0)} fcn r(n){ if (not n) return(0); c := super[pos - n]; if (not (cnt[n]-=1)){ cnt[n] = n; if (not r(n-1)) return(0); } super[pos] = c; pos+=1; 1} fcn superperm(n){ pos = n; len := fact_sum(n); super.fill(0,len); // this is pretty close to recalloc() cnt = (n+1).pump(List()); //-->(0,1,2,3,..n) foreach i in (n){ super[i] = i + 0x31; } //-->"1" ... "123456789:;" while (r(n)){}} foreach n in (MAX){ superperm(n); print("superperm(%2d) len = %d".fmt(n,super.len())); // uncomment next line to see the string itself //print(": %s".fmt(super.text)); println();}superperm( 0) len = 0: superperm( 1) len = 1: 1superperm( 2) len = 3: 121superperm( 3) len = 9: 123121321superperm( 4) len = 33: 123412314231243121342132413214321superperm( 5) len = 153: 123451234152341253412354123145231425314235142315423124531243512431524312543121345213425134215342135421324513241532413524132541321453214352143251432154321superperm( 6) len = 873superperm( 7) len = 5913superperm( 8) len = 46233superperm( 9) len = 409113superperm(10) len = 4037913superperm(11) len = 43954713