Superpermutation minimisation: Difference between revisions
Content added Content deleted
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
(Added XPL0 example.) |
||
Line 2,106: | Line 2,106: | ||
superPerm(10) len = 4037913 |
superPerm(10) len = 4037913 |
||
superPerm(11) len = 43954713 |
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> |
</pre> |
||