Superpermutation minimisation: Difference between revisions
Content added Content deleted
m (→{{header|C}}: corrected a misspelling.) |
m (→version 1: added/changed comments and whitespace, added commas to the output.) |
||
Line 1,421: | Line 1,421: | ||
<lang rexx>/*REXX program attempts to find better minimizations for computing superpermutations.*/ |
<lang rexx>/*REXX program attempts to find better minimizations for computing superpermutations.*/ |
||
parse arg cycles . /*obtain optional arguments from the CL*/ |
parse arg cycles . /*obtain optional arguments from the CL*/ |
||
if cycles=='' | cycles=="," then cycles= |
if cycles=='' | cycles=="," then cycles= 7 /*Not specified? Then use the default.*/ |
||
do n=0 to cycles |
do n=0 to cycles |
||
#=0; |
#= 0; $.= /*populate the first permutation. */ |
||
do pop=1 for n; @.pop=d2x(pop); |
do pop=1 for n; @.pop= d2x(pop); $.0= $.0 || @.pop |
||
end /*pop*/ |
|||
do while aPerm(n, 0) |
do while aPerm(n, 0) |
||
if n\==0 then #=#+1; $.#= |
if n\==0 then #=#+1; $.#= |
||
do j=1 for n; $.#= $.# || @.j |
|||
end /*j*/ |
|||
end /*while*/ |
|||
⚫ | |||
z= $.0 |
|||
⚫ | |||
do ?=1 for #; if $.j=='' then iterate; if pos($.?, z)\==0 then iterate |
do ?=1 for #; if $.j=='' then iterate; if pos($.?, z)\==0 then iterate |
||
parse var $.? h 2 R 1 L =(n) |
parse var $.? h 2 R 1 L =(n) |
||
if left(z, nm)==R then do; z=h || z; iterate; end |
if left(z, nm)==R then do; z= h || z; iterate; end |
||
if right(z, 1)==h then do; z=z || R; iterate; end |
if right(z, 1)==h then do; z= z || R; iterate; end |
||
z=z || $.? |
z= z || $.? |
||
end /*?*/ /* [↑] more IFs could be added for opt*/ |
end /*?*/ /* [↑] more IFs could be added for opt*/ |
||
L= commas( length(z) ) |
|||
say 'length of superpermutation('n") =" length( |
say 'length of superpermutation('n") =" right(L, max(length(L), cycles+2) ) |
||
end /*cycle*/ |
end /*cycle*/ |
||
exit |
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 @.; |
aPerm: procedure expose @.; parse arg n,i; nm= n - 1; if n==0 then return 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 |
if i==0 then return 0 |
||
do m=i+1 while @.m<@.i; end /*m*/; parse value @.m @.i with @.i @.m |
|||
return 1</lang> |
return 1</lang> |
||
{{out|output|text= when using the input: <tt> 8 </tt>}} |
{{out|output|text= when using the input: <tt> 8 </tt>}} |
||
<pre> |
<pre> |
||
length of superpermutation(0) = 0 |
length of superpermutation(0) = 0 |
||
length of superpermutation(1) = 1 |
length of superpermutation(1) = 1 |
||
length of superpermutation(2) = 2 |
length of superpermutation(2) = 2 |
||
length of superpermutation(3) = 9 |
length of superpermutation(3) = 9 |
||
length of superpermutation(4) = 50 |
length of superpermutation(4) = 50 |
||
length of superpermutation(5) = 302 |
length of superpermutation(5) = 302 |
||
length of superpermutation(6) = |
length of superpermutation(6) = 1,922 |
||
length of superpermutation(7) = |
length of superpermutation(7) = 13,652 |
||
length of superpermutation(8) = |
length of superpermutation(8) = 109,538 |
||
</pre> |
</pre> |
||