Superpermutation minimisation: Difference between revisions

* [https://www.youtube.com/watch?v=_tpNuulTeSQ New Superpermutations Discovered!] Standupmaths & Numberphile.

<br><br>

 

=={{header|AWK}}==

# syntax: GAWK -f SUPERPERMUTATION_MINIMISATION.AWK

# converted from C

return(1)

}

{{out}}

<pre>

=={{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.

#include <stdlib.h>

#include <string.h>

 

return 0;

{{out}}

<pre>

=={{header|C++}}==

{{trans|Kotlin}}

#include <iostream>

#include <vector>

 

return 0;

{{out}}

<pre>superPerm(0) len = 0

=={{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, ...)

foreach (immutable n; 1 .. 8)

n.superpermutation.length.writeln;

{{out}}

<pre>1

{{trans|C}}

From the C version with some improvements.

 

enum uint nMax = 12;

writeln;

}

{{out}}

<pre>superPerm( 0) len = 0

{{libheader| System.SysUtils}}

{{Trans|C}}

program Superpermutation_minimisation;

 

end;

{$IFNDEF UNIX} readln; {$ENDIF}

 

=={{header|Elixir}}==

{{trans|Ruby}}

def minimisation(1), do: [1]

def minimisation(n) do

IO.puts if n<5, do: Enum.join(result),

else: to_s.(Enum.take(result,20)) <> "...." <> to_s.(Enum.slice(result,-20..-1))

 

{{out}}

 

=={{header|FreeBASIC}}==

' compile with: fbc -s console

 

Print : Print "hit any key to end program"

Sleep

{{out}}

<pre> 1 1 1 1

=={{header|Go}}==

{{trans|C}}

 

import "fmt"

fmt.Printf("len = %d\n", len(super))

}

 

{{out}}

=={{header|Groovy}}==

{{trans|Java}}

 

class Superpermutation {

}

}

{{out}}

<pre>superPerm( 0) len = 0

If there's an 872 long superpermutation for a six letter alphabet, this is not optimal.

 

seqs=. y{~(A.&i.~ !)#y

r=.{.seqs

end.

r

 

Some sequence lengths:

 

1 1

2 3

6 873

7 5913

 

=={{header|Java}}==

Translation of [[Superpermutation_minimisation#C|C]] via [[Superpermutation_minimisation#D|D]]

{{works with|Java|8}}

 

public class Test {

}

}

 

<pre>superPerm( 0) len = 0

{{trans|D}}

Runs in about 1/4 second.

 

function r!(n, s, pos, count)

 

testsuper(nmax)

<pre>

Superperm(0) has length 0

=={{header|Kotlin}}==

{{trans|C}}

 

const val MAX = 12

println("superPerm(${"%2d".format(n)}) len = ${sp.size}")

}

 

{{out}}

=={{header|Mathematica}} / {{header|Wolfram Language}}==

Greedy algorithm:

OverlapDistance[{s1_List, s2_List}] := OverlapDistance[s1, s2]

OverlapDistance[s1_List, s2_List] := Module[{overlaprange, overlap, l},

,

{i, 1, 7}

{{out}}

<pre>{1,1}

=={{header|Nim}}==

{{trans|Go}}

 

const MAX = 12

write(stdout, fmt"superperm({n:2})")

superperm(n)

{{out}}

<pre>

=={{header|Objeck}}==

{{trans|C}}

@super : static : Char[];

@pos : static : Int;

}

}

 

{{output}}

 

{{libheader|ntheory}}

for my $len (1..8) {

my($pre, $post, $t) = ("","");

} $len;

printf "%2d: %8d %8d\n", $len, length($pre), length($post);

{{out}}

<pre> 1: 1 1

=={{header|Phix}}==

{{trans|C}}

{{out}}

<pre>

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).

{{out}}

<pre>

=={{header|PureBasic}}==

{{trans|C}}

#MAX=10

Declare.i fact_sum(n.i) : Declare.i r(n.i) : Declare superperm(n.i)

For i=1 To n : super(i-1)=Chr('0'+i) : Next

While r(n) : Wend

{{out}}

<pre>superperm( 0) len = 0

 

=={{header|Python}}==

 

 

print('\n'.join('%12s (%.3f)' % (k, v.total_seconds()) for k, v in

sorted(runtime.items(), key=lambda keyvalue: keyvalue[1])))

 

{{out}}

===Alternative Version===

{{trans|D}}

from string import ascii_uppercase, digits

from operator import mul

print

 

It is four times slower than the D entry. The output is about the same as the D entry.

 

{{trans|Ruby}}

 

(require racket/list racket/format)

 

 

(for* ((n (in-range 1 (add1 8))) (ary (in-value (superperm n))))

 

{{out}}

(formerly Perl 6)

{{trans|Perl}}

my $pre = my $post = my $t = '';

for ('a'..'z')[^$len].permutations -> @p {

}

printf "%1d: %8d %8d\n", $len, $pre.chars, $post.chars;

{{out}}

<pre>1: 1 1

===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

end /*pop*/

 

do while aPerm(n, 0)

end /*j*/

end /*while*/

z= $.0

nm= n-1

z= z || $.p

end /*p*/ /* [↑] more IFs could be added for opt*/

 

L= commas( length(z) )

end /*cycle*/

exit 0 /*stick a fork in it, we're all done. */

if i==0 then return 0

do m=i+1 while @.m<@.i; end /*m*/; parse value @.m @.i with @.i @.m

{{out|output|text=&nbsp; when using the input: &nbsp; &nbsp; <tt> 8 </tt>}}

<pre>

 

===version 2===

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; $.= /*populate the first permutation. */

end /*pop*/

 

do j=1 for n; $.#= $.# || @.j

end /*j*/

end /*while*/

z= $.0

do j=1 while c\==#

if j># then do; c= c + 1 /*exhausted finds and shortcuts; concat*/

end

if $.j=='' then iterate /*Already found? Then ignore this perm.*/

iterate

end

 

do k=n-1 to 1 by -1 /*handle the shortcuts in perm finding.*/

z= left($.j, k-1) || z; $.j=

iterate j

end

z= z || substr($.j, k+1); $.j=

iterate j

end /*k*/ /* [↑] more IFs could be added for opt*/

end /*j*/

L= commas( length(z) )

say 'length of superpermutation('n") =" right(L, max(length(L), cycles+2) )

if i==0 then return 0

do m=i+1 while @.m<@.i; end /*m*/; parse value @.m @.i with @.i @.m

{{out|output|text=&nbsp; when using the default input: &nbsp; &nbsp; <tt> 7 </tt>}}

<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

a.each{|n| print n}; puts "\n\n"

l = a

{{out}}

<pre>1

123456123451623451263451236451234651234156234152634152364152346152341652341256341253641253461253416253412653412356412354612354162354126354123654123145623145263145236145231645231465231425631425361425316425314625314265314235614235164235146235142635142365142315642315462315426315423615423165423124563124536124531624531264531246531243561243516243512643512463512436512431562431526431524631524361524316524312564312546312543612543162543126543121345621345261345216345213645213465213425613425163425136425134625134265134215634215364215346215342615342165342135642135462135426135421635421365421324561324516324513624513264513246513241563241536241532641532461532416532413562413526413524613524163524136524132564132546132541632541362541326541321456321453621453261453216453214653214356214352614352164352146352143652143256143251643251463251436251432651432156432154632154362154326154321654321</pre>

===Recursive Version===

return [1] if n==1

superperm(n-1).each_cons(n-1).with_object([]) do |sub, ary|

print "%3d: len =%8d :" % [n, ary.size]

puts n<5 ? ary.join : to_16(ary.first(20)) + "...." + to_16(ary.last(20))

{{out}}

1: len = 1 :1

 

=={{header|Scala}}==

val nMax = 12

 

for (n <- 0 until nMax) println(f"superPerm($n%2d) len = ${factSum(n)}%d")

 

 

=={{header|Sidef}}==

{{trans|Perl}}

var (pre="", post="")

@^len -> permutations {|*p|

}

printf("%2d: %8d %8d\n", len, pre.len, post.len)

{{out}}

<pre>

{{trans|Kotlin}}

{{libheader|Wren-fmt}}

 

var max = 12

superPerm.call(n)

Fmt.print("superPerm($2d) len = $d", n, sp.count)

 

{{out}}

superPerm(10) len = 4037913

superPerm(11) len = 43954713

</pre>

 

{{trans|C}}

It crawls ...

var super=Data(), pos, cnt; // global state, ick

//print(": %s".fmt(super.text));

println();

{{out}}

<pre>