Rosetta Code

Superpermutation minimisation: Difference between revisions

Page Discussion

Superpermutation minimisation (view source)

Revision as of 11:14, 11 February 2024

2,368 bytes added ,  4 months ago
m
→‎{{header|Wren}}: Minor tidy
m (→‎{{header|Phix}}: syntax coloured, made p2js compatible - mainly via a much smaller limit.)
m (→‎{{header|Wren}}: Minor tidy)
 
(2 intermediate revisions by 2 users not shown)
Line 30:
{{trans|Kotlin}}
 
<langsyntaxhighlight lang="11l">-V MAX = 12
 
[Char] sp
Line 69:
L(n) 0 .< MAX
superPerm(n)
print(‘superPerm(#2) len = #.’.format(n, sp.len))</langsyntaxhighlight>
 
{{out}}
Line 88:
 
=={{header|AWK}}==
<syntaxhighlight lang="awk">
<lang AWK>
# syntax: GAWK -f SUPERPERMUTATION_MINIMISATION.AWK
# converted from C
Line 137:
return(1)
}
</syntaxhighlight>
</lang>▼
{{out}}
<pre>
Line 156:
=={{header|C}}==
Finding a string whose length follows [https://oeis.org/A007489 OEIS A007489]. &nbsp; Complexity is the length of output string. &nbsp; It is known to be ''not'' optimal.
<langsyntaxhighlight lang="c">#include <stdio.h>
#include <stdlib.h>
#include <string.h>
Line 213:
 
return 0;
}</langsyntaxhighlight>
{{out}}
<pre>
Line 232:
=={{header|C++}}==
{{trans|Kotlin}}
<langsyntaxhighlight lang="cpp">#include <array>
#include <iostream>
#include <vector>
Line 290:
 
return 0;
}</langsyntaxhighlight>
{{out}}
<pre>superPerm(0) len = 0
Line 307:
=={{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.
<langsyntaxhighlight lang="d">import std.stdio, std.ascii, std.algorithm, core.memory, permutations2;
 
/** Uses greedy algorithm of adding another char (or two, or three, ...)
Line 351:
foreach (immutable n; 1 .. 8)
n.superpermutation.length.writeln;
}</langsyntaxhighlight>
{{out}}
<pre>1
Line 365:
{{trans|C}}
From the C version with some improvements.
<langsyntaxhighlight lang="d">import std.stdio, std.range, std.algorithm, std.ascii;
 
enum uint nMax = 12;
Line 414:
writeln;
}
}</langsyntaxhighlight>
{{out}}
<pre>superPerm( 0) len = 0
Line 433:
{{libheader| System.SysUtils}}
{{Trans|C}}
<syntaxhighlight lang="delphi">
<lang Delphi>
program Superpermutation_minimisation;
 
Line 511:
end;
{$IFNDEF UNIX} readln; {$ENDIF}
end.</langsyntaxhighlight>
 
=={{header|Elixir}}==
{{trans|Ruby}}
<langsyntaxhighlight lang="elixir">defmodule Superpermutation do
def minimisation(1), do: [1]
def minimisation(n) do
Line 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)</langsyntaxhighlight>
 
{{out}}
Line 552:
 
=={{header|FreeBASIC}}==
<langsyntaxhighlight lang="freebasic">' version 28-06-2018
' compile with: fbc -s console
 
Line 630:
Print : Print "hit any key to end program"
Sleep
End</langsyntaxhighlight>
{{out}}
<pre> 1 1 1 1
Line 645:
=={{header|Go}}==
{{trans|C}}
<langsyntaxhighlight lang="go">package main
 
import "fmt"
Line 706:
fmt.Printf("len = %d\n", len(super))
}
}</langsyntaxhighlight>
 
{{out}}
Line 726:
=={{header|Groovy}}==
{{trans|Java}}
<langsyntaxhighlight lang="groovy">import static java.util.stream.IntStream.rangeClosed
 
class Superpermutation {
Line 780:
}
}
}</langsyntaxhighlight>
{{out}}
<pre>superPerm( 0) len = 0
Line 799:
If there's an 872 long superpermutation for a six letter alphabet, this is not optimal.
 
<langsyntaxhighlight Jlang="j">approxmin=:3 :0
seqs=. y{~(A.&i.~ !)#y
r=.{.seqs
Line 816:
end.
r
)</langsyntaxhighlight>
 
Some sequence lengths:
 
<langsyntaxhighlight Jlang="j"> (#, #@approxmin)@> (1+i.8) {.&.> <'abcdefghijk'
1 1
2 3
Line 828:
6 873
7 5913
8 46233</langsyntaxhighlight>
 
=={{header|Java}}==
Translation of [[Superpermutation_minimisation#C|C]] via [[Superpermutation_minimisation#D|D]]
{{works with|Java|8}}
<langsyntaxhighlight lang="java">import static java.util.stream.IntStream.rangeClosed;
 
public class Test {
Line 883:
}
}
}</langsyntaxhighlight>
 
<pre>superPerm( 0) len = 0
Line 901:
{{trans|D}}
Runs in about 1/4 second.
<langsyntaxhighlight lang="julia">const nmax = 12
 
function r!(n, s, pos, count)
Line 941:
 
testsuper(nmax)
</langsyntaxhighlight>{{out}}
<pre>
Superperm(0) has length 0
Line 959:
=={{header|Kotlin}}==
{{trans|C}}
<langsyntaxhighlight lang="scala">// version 1.1.2
 
const val MAX = 12
Line 1,003:
println("superPerm(${"%2d".format(n)}) len = ${sp.size}")
}
}</langsyntaxhighlight>
 
{{out}}
Line 1,023:
=={{header|Mathematica}} / {{header|Wolfram Language}}==
Greedy algorithm:
<langsyntaxhighlight Mathematicalang="mathematica">ClearAll[OverlapDistance, ConstructDistances]
OverlapDistance[{s1_List, s2_List}] := OverlapDistance[s1, s2]
OverlapDistance[s1_List, s2_List] := Module[{overlaprange, overlap, l},
Line 1,055:
,
{i, 1, 7}
]</langsyntaxhighlight>
{{out}}
<pre>{1,1}
Line 1,067:
=={{header|Nim}}==
{{trans|Go}}
<langsyntaxhighlight lang="nim">import strformat
 
const MAX = 12
Line 1,110:
write(stdout, fmt"superperm({n:2})")
superperm(n)
writeLine(stdout, fmt" len = {len(super)}")</langsyntaxhighlight>
{{out}}
<pre>
Line 1,129:
=={{header|Objeck}}==
{{trans|C}}
<langsyntaxhighlight lang="objeck">class SuperPermutation {
@super : static : Char[];
@pos : static : Int;
Line 1,194:
}
}
</syntaxhighlight>
</lang>
 
{{output}}
Line 1,216:
 
{{libheader|ntheory}}
<langsyntaxhighlight lang="perl">use ntheory qw/forperm/;
for my $len (1..8) {
my($pre, $post, $t) = ("","");
Line 1,225:
} $len;
printf "%2d: %8d %8d\n", $len, length($pre), length($post);
}</langsyntaxhighlight>
{{out}}
<pre> 1: 1 1
Line 1,239:
=={{header|Phix}}==
{{trans|C}}
<!--<langsyntaxhighlight Phixlang="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>
Line 1,298:
<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>
<!--</langsyntaxhighlight>-->
{{out}}
<pre>
Line 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).
<!--<langsyntaxhighlight Phixlang="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>
Line 1,377:
<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>
<!--</langsyntaxhighlight>-->
{{out}}
<pre>
Line 1,392:
=={{header|PureBasic}}==
{{trans|C}}
<langsyntaxhighlight PureBasiclang="purebasic">EnableExplicit
#MAX=10
Declare.i fact_sum(n.i) : Declare.i r(n.i) : Declare superperm(n.i)
Line 1,431:
For i=1 To n : super(i-1)=Chr('0'+i) : Next
While r(n) : Wend
EndProcedure</langsyntaxhighlight>
{{out}}
<pre>superperm( 0) len = 0
Line 1,446:
 
=={{header|Python}}==
<langsyntaxhighlight lang="python">"Generate a short Superpermutation of n characters A... as a string using various algorithms."
 
 
Line 1,586:
print('\n'.join('%12s (%.3f)' % (k, v.total_seconds()) for k, v in
sorted(runtime.items(), key=lambda keyvalue: keyvalue[1])))
</syntaxhighlight>
</lang>
 
{{out}}
Line 1,691:
===Alternative Version===
{{trans|D}}
<langsyntaxhighlight lang="python">from array import array
from string import ascii_uppercase, digits
from operator import mul
Line 1,749:
print
 
main()</langsyntaxhighlight>
It is four times slower than the D entry. The output is about the same as the D entry.
 
Line 1,755:
{{trans|Ruby}}
 
<langsyntaxhighlight lang="racket">#lang racket/base
(require racket/list racket/format)
 
Line 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)))</langsyntaxhighlight>
 
{{out}}
Line 1,803:
(formerly Perl 6)
{{trans|Perl}}
<syntaxhighlight lang="raku" perl6line>for 1..8 -> $len {
my $pre = my $post = my $t = '';
for ('a'..'z')[^$len].permutations -> @p {
Line 1,811:
}
printf "%1d: %8d %8d\n", $len, $pre.chars, $post.chars;
}</langsyntaxhighlight>
{{out}}
<pre>1: 1 1
Line 1,825:
===version 1===
This REXX version just does simple finds for the permutations.
<langsyntaxhighlight lang="rexx">/*REXX program attempts to find better minimizations for computing superpermutations.*/
parse arg cycles . /*obtain optional arguments from the CL*/
if cycles=='' | cycles=="," then cycles= 7 /*Not specified? Then use the default.*/
Line 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</langsyntaxhighlight>
{{out|output|text=&nbsp; when using the input: &nbsp; &nbsp; <tt> 8 </tt>}}
<pre>
Line 1,876:
 
===version 2===
<langsyntaxhighlight lang="rexx">/*REXX program attempts to find better minimizations for computing superpermutations.*/
parse arg cycles . /*obtain optional arguments from the CL*/
if cycles=='' | cycles=="," then cycles= 7 /*Not specified? Then use the default.*/
Line 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</langsyntaxhighlight>
{{out|output|text=&nbsp; when using the default input: &nbsp; &nbsp; <tt> 7 </tt>}}
<pre>
Line 1,940:
=={{header|Ruby}}==
===Non Recursive Version===
<langsyntaxhighlight lang="ruby">#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
Line 1,961:
a.each{|n| print n}; puts "\n\n"
l = a
}</langsyntaxhighlight>
{{out}}
<pre>1
Line 1,975:
123456123451623451263451236451234651234156234152634152364152346152341652341256341253641253461253416253412653412356412354612354162354126354123654123145623145263145236145231645231465231425631425361425316425314625314265314235614235164235146235142635142365142315642315462315426315423615423165423124563124536124531624531264531246531243561243516243512643512463512436512431562431526431524631524361524316524312564312546312543612543162543126543121345621345261345216345213645213465213425613425163425136425134625134265134215634215364215346215342615342165342135642135462135426135421635421365421324561324516324513624513264513246513241563241536241532641532461532416532413562413526413524613524163524136524132564132546132541632541362541326541321456321453621453261453216453214653214356214352614352164352146352143652143256143251643251463251436251432651432156432154632154362154326154321654321</pre>
===Recursive Version===
<langsyntaxhighlight lang="ruby">def superperm(n)
return [1] if n==1
superperm(n-1).each_cons(n-1).with_object([]) do |sub, ary|
Line 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</langsyntaxhighlight>
{{out}}
1: len = 1 :1
Line 2,004:
 
=={{header|Scala}}==
<langsyntaxhighlight Scalalang="scala">object SuperpermutationMinimisation extends App {
val nMax = 12
 
Line 2,015:
for (n <- 0 until nMax) println(f"superPerm($n%2d) len = ${factSum(n)}%d")
 
}</langsyntaxhighlight>
 
=={{header|Sidef}}==
{{trans|Perl}}
<langsyntaxhighlight lang="ruby">for len in (1..8) {
var (pre="", post="")
@^len -> permutations {|*p|
Line 2,027:
}
printf("%2d: %8d %8d\n", len, pre.len, post.len)
}</langsyntaxhighlight>
{{out}}
<pre>
Line 2,043:
{{trans|Kotlin}}
{{libheader|Wren-fmt}}
<langsyntaxhighlight ecmascriptlang="wren">import "./fmt" for Fmt
 
var max = 12
Line 2,090:
superPerm.call(n)
Fmt.print("superPerm($2d) len = $d", n, sp.count)
}</langsyntaxhighlight>
 
{{out}}
Line 2,106:
superPerm(10) len = 4037913
superPerm(11) len = 43954713
▲</langpre>
 
=={{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 2,111 ⟶ 2,182:
{{trans|C}}
It crawls ...
<langsyntaxhighlight lang="zkl">const MAX = 12;
var super=Data(), pos, cnt; // global state, ick
Line 2,146 ⟶ 2,217:
//print(": %s".fmt(super.text));
println();
}</langsyntaxhighlight>
{{out}}
<pre>
PureFox
9,485

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/251590...352561"