Superpermutation minimisation: Difference between revisions
→{{header|Phix}}
(Fixed description and promeoted to full task.) |
|||
Line 645:
7: 10080 13699
8: 80640 109600</pre>
=={{header|Phix}}==
{{trans|C}}
<lang Phix>constant nMax = 12
atom t0 = time()
string superperm
sequence count
integer pos
function factSum(int n)
integer s = 0, f = 1
for i=1 to n do
f *= i
s += f
end for
return s
end function
function r(int n)
if (n == 0) then return false end if
integer c = superperm[pos-n+1]
count[n] -= 1
if count[n]=0 then
count[n] = n
if not r(n-1) then return false end if
end if
pos += 1
superperm[pos] = c
return true
end function
procedure superPerm(int n)
string chars = "123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"[1..n]
pos = n
superperm = chars&repeat(' ',factSum(n)-n)
count = tagset(n)
while r(n) do end while
if n=0 then
if superperm!="" then ?9/0 end if
elsif n<=9 then
-- (I estimate it would take at least 5 days to validate
-- superPerm(12), feel free to try it on your own time)
for i=1 to factorial(n) do
if not match(permute(i,chars),superperm) then ?9/0 end if
end for
end if
end procedure
for n=0 to nMax do
superPerm(n)
integer l = length(superperm)
if l>40 then superperm[20..-20] = "..." end if
string e = elapsed(time()-t0)
printf(1,"superPerm(%2d) len = %d %s (%s)\n", {n, l, superperm, e})
end for</lang>
{{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).
<lang Phix>procedure superPerm(int n)
atom t0 = time()
string chars = "123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"[1..n]
integer f = factorial(n)
sequence perms = repeat("",f)
for i=1 to f do
perms[i] = permute(i,chars)
end for
string res = perms[$]
perms = perms[1..$-1]
while length(perms) do
integer best = 0, bi = length(perms)
for i=1 to length(perms) do
string pi = perms[i]
integer m = length(res),
k = find(res[m],pi)
for l=k to 1 by -1 do
if res[m]!=pi[l] then
k = 0
exit
end if
m -= 1
end for
if k>best then
best = k
bi = i
end if
end for
if match(perms[bi],res) then
?9/0 -- (sanity check)
else
res &= perms[bi][best+1..$]
end if
perms[bi] = perms[$]
perms = perms[1..$-1]
end while
integer lr = length(res)
integer fsn = factSum(n)
string op = {"<","=",">"}[compare(lr,fsn)+2]
t0 = time()-t0
string e = iff(t0>1?", "&elapsed(t0):"")
printf(1,"superPerm(%d) len = %d (%s%d%s)\n",{n,lr,op,fsn,e})
end procedure
for n=1 to 7 do -- (note: 8 takes 65x longer than 7)
superPerm(n)
end for</lang>
{{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|Python}}==
| |||