Superpermutation minimisation: Difference between revisions
m
→{{header|Wren}}: Minor tidy
m (→version 1: added/changed comments and whitespace, added commas to the output.) |
m (→{{header|Wren}}: Minor tidy) |
||
(15 intermediate revisions by 9 users not shown) | |||
Line 26:
* [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
Line 77 ⟶ 137:
return(1)
}
</syntaxhighlight>
{{out}}
<pre>
Line 96 ⟶ 156:
=={{header|C}}==
Finding a string whose length follows [https://oeis.org/A007489 OEIS A007489]. Complexity is the length of output string. It is known to be ''not'' optimal.
<
#include <stdlib.h>
#include <string.h>
Line 153 ⟶ 213:
return 0;
}</
{{out}}
<pre>
Line 169 ⟶ 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.
<
/** Uses greedy algorithm of adding another char (or two, or three, ...)
Line 216 ⟶ 351:
foreach (immutable n; 1 .. 8)
n.superpermutation.length.writeln;
}</
{{out}}
<pre>1
Line 230 ⟶ 365:
{{trans|C}}
From the C version with some improvements.
<
enum uint nMax = 12;
Line 279 ⟶ 414:
writeln;
}
}</
{{out}}
<pre>superPerm( 0) len = 0
Line 294 ⟶ 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}}
<
def minimisation(1), do: [1]
def minimisation(n) do
Line 319 ⟶ 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)</
{{out}}
Line 334 ⟶ 552:
=={{header|FreeBASIC}}==
<
' compile with: fbc -s console
Line 412 ⟶ 630:
Print : Print "hit any key to end program"
Sleep
End</
{{out}}
<pre> 1 1 1 1
Line 427 ⟶ 645:
=={{header|Go}}==
{{trans|C}}
<
import "fmt"
Line 488 ⟶ 706:
fmt.Printf("len = %d\n", len(super))
}
}</
{{out}}
Line 505 ⟶ 723:
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 510 ⟶ 799:
If there's an 872 long superpermutation for a six letter alphabet, this is not optimal.
<
seqs=. y{~(A.&i.~ !)#y
r=.{.seqs
Line 527 ⟶ 816:
end.
r
)</
Some sequence lengths:
<
1 1
2 3
Line 539 ⟶ 828:
6 873
7 5913
8 46233</
=={{header|Java}}==
Translation of [[Superpermutation_minimisation#C|C]] via [[Superpermutation_minimisation#D|D]]
{{works with|Java|8}}
<
public class Test {
Line 594 ⟶ 883:
}
}
}</
<pre>superPerm( 0) len = 0
Line 612 ⟶ 901:
{{trans|D}}
Runs in about 1/4 second.
<
function r!(n, s, pos, count)
Line 652 ⟶ 941:
testsuper(nmax)
</
<pre>
Superperm(0) has length 0
Line 670 ⟶ 959:
=={{header|Kotlin}}==
{{trans|C}}
<
const val MAX = 12
Line 714 ⟶ 1,003:
println("superPerm(${"%2d".format(n)}) len = ${sp.size}")
}
}</
{{out}}
Line 731 ⟶ 1,020:
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}}
<
const MAX = 12
Line 777 ⟶ 1,110:
write(stdout, fmt"superperm({n:2})")
superperm(n)
writeLine(stdout, fmt" len = {len(super)}")</
{{out}}
<pre>
Line 796 ⟶ 1,129:
=={{header|Objeck}}==
{{trans|C}}
<
@super : static : Char[];
@pos : static : Int;
Line 861 ⟶ 1,194:
}
}
</syntaxhighlight>
{{output}}
Line 883 ⟶ 1,216:
{{libheader|ntheory}}
<
for my $len (1..8) {
my($pre, $post, $t) = ("","");
Line 892 ⟶ 1,225:
} $len;
printf "%2d: %8d %8d\n", $len, length($pre), length($post);
}</
{{out}}
<pre> 1: 1 1
Line 906 ⟶ 1,239:
=={{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>
Line 980 ⟶ 1,320:
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;">"<"</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"="</span><span style="color: #0000FF;">,</span><span style="color: #008000;">">"</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>
Line 1,038 ⟶ 1,389:
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}}==
<
Line 1,180 ⟶ 1,586:
print('\n'.join('%12s (%.3f)' % (k, v.total_seconds()) for k, v in
sorted(runtime.items(), key=lambda keyvalue: keyvalue[1])))
</syntaxhighlight>
{{out}}
Line 1,285 ⟶ 1,691:
===Alternative Version===
{{trans|D}}
<
from string import ascii_uppercase, digits
from operator import mul
Line 1,343 ⟶ 1,749:
print
main()</
It is four times slower than the D entry. The output is about the same as the D entry.
Line 1,349 ⟶ 1,755:
{{trans|Ruby}}
<
(require racket/list racket/format)
Line 1,381 ⟶ 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)))</
{{out}}
Line 1,397 ⟶ 1,803:
(formerly Perl 6)
{{trans|Perl}}
<syntaxhighlight lang="raku"
my $pre = my $post = my $t = '';
for ('a'..'z')[^$len].permutations -> @p {
Line 1,405 ⟶ 1,811:
}
printf "%1d: %8d %8d\n", $len, $pre.chars, $post.chars;
}</
{{out}}
<pre>1: 1 1
Line 1,419 ⟶ 1,825:
===version 1===
This REXX version just does simple finds for the permutations.
<
parse arg cycles . /*obtain optional arguments from the CL*/
if cycles=='' | cycles=="," then cycles= 7 /*Not specified? Then use the default.*/
do n=0 to cycles
#= 0; $.=
do pop=1 for n; @.pop= d2x(pop); $.0= $.0 || @.pop
end /*pop*/
do while aPerm(n, 0)
if n\==0 then #= #+1; $.#=
do j=1 for n; $.#= $.# || @.j
end /*j*/
end /*while*/
z= $.0
nm= n-1
do
if
if right(z, 1)==h then do; z= z ||
end /*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*/
exit 0 /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
commas: parse arg
/*──────────────────────────────────────────────────────────────────────────────────────*/
aPerm: procedure expose @.; parse arg n,i; nm= n - 1; if n==0 then return 0
Line 1,453 ⟶ 1,861:
if i==0 then return 0
do m=i+1 while @.m<@.i; end /*m*/; parse value @.m @.i with @.i @.m
return 1</
{{out|output|text= when using the input: <tt> 8 </tt>}}
<pre>
Line 1,468 ⟶ 1,876:
===version 2===
<
parse arg cycles . /*obtain optional arguments from the CL*/
if cycles=='' | cycles=="," then cycles=
do n=0 to cycles
#= 0;
do pop=1 for n; @.pop= d2x(pop); $.0= $.0 || @.pop
end /*pop*/
do while aPerm(n,0); if n\==0 then #= #+1; $.#=
end /*
end /*while*/
z= $.0
c= 0 /*count of found permutations (so far).*/
do j=1 while c\==#
if j># then do; c= c +
z= z || $.j; $.j=
j= 1
end
if $.j=='' then iterate
if pos($.j, z)\==0 then do; c= c + 1; $.j=
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
z= left($.j, k-1) || z; $.j=
iterate j
end
if left($.j, k) ==right(z, k) then do; c= c+1 /*found
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") =" right(L, max(length(L), cycles+2) )
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 1,512 ⟶ 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</
{{out|output|text= when using the default input: <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) =
length of superpermutation(7) =
</pre>
=={{header|Ruby}}==
===Non Recursive Version===
<
#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 1,548 ⟶ 1,961:
a.each{|n| print n}; puts "\n\n"
l = a
}</
{{out}}
<pre>1
Line 1,562 ⟶ 1,975:
123456123451623451263451236451234651234156234152634152364152346152341652341256341253641253461253416253412653412356412354612354162354126354123654123145623145263145236145231645231465231425631425361425316425314625314265314235614235164235146235142635142365142315642315462315426315423615423165423124563124536124531624531264531246531243561243516243512643512463512436512431562431526431524631524361524316524312564312546312543612543162543126543121345621345261345216345213645213465213425613425163425136425134625134265134215634215364215346215342615342165342135642135462135426135421635421365421324561324516324513624513264513246513241563241536241532641532461532416532413562413526413524613524163524136524132564132546132541632541362541326541321456321453621453261453216453214653214356214352614352164352146352143652143256143251643251463251436251432651432156432154632154362154326154321654321</pre>
===Recursive Version===
<
return [1] if n==1
superperm(n-1).each_cons(n-1).with_object([]) do |sub, ary|
Line 1,577 ⟶ 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</
{{out}}
1: len = 1 :1
Line 1,591 ⟶ 2,004:
=={{header|Scala}}==
<
val nMax = 12
Line 1,602 ⟶ 2,015:
for (n <- 0 until nMax) println(f"superPerm($n%2d) len = ${factSum(n)}%d")
}</
=={{header|Sidef}}==
{{trans|Perl}}
<
var (pre="", post="")
@^len -> permutations {|*p|
Line 1,614 ⟶ 2,027:
}
printf("%2d: %8d %8d\n", len, pre.len, post.len)
}</
{{out}}
<pre>
Line 1,630 ⟶ 2,043:
{{trans|Kotlin}}
{{libheader|Wren-fmt}}
<
var max = 12
Line 1,677 ⟶ 2,090:
superPerm.call(n)
Fmt.print("superPerm($2d) len = $d", n, sp.count)
}</
{{out}}
Line 1,693 ⟶ 2,106:
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 1,698 ⟶ 2,182:
{{trans|C}}
It crawls ...
<
var super=Data(), pos, cnt; // global state, ick
Line 1,733 ⟶ 2,217:
//print(": %s".fmt(super.text));
println();
}</
{{out}}
<pre>
|