Superpermutation minimisation: Difference between revisions

 

The problem of generating the shortest superpermutation for each N ''might'' be NP complete, although the minimal strings for small values of N have been found by brute -force searches.

 

;Reference:

* [http://oeis.org/A180632 oeis A180632] gives 0-5 as 0, 1, 3, 9, 33, 153. 6 is thought to be 872.

* [https://www.youtube.com/watch?v=wJGE4aEWc28 Superpermutations - Numberphile]. A video

<br><br>

=={{header|C}}==

#include <stdlib.h>

#include <string.h>

 

return 0;

{{out}}

<pre>

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

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

superPerm(11) len = 43954713</pre>

Run-time: about 0.40 seconds.

 

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

8: len = 46233 : 12345678123456718234....43281765432187654321

</pre>

 

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

superperm(11) len = 43954713

</pre>

 

=={{header|J}}==

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

superPerm(10) len = 4037913

superPerm(11) len = 43954713</pre>

 

=={{header|Kotlin}}==

{{trans|C}}

 

const val MAX = 12

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

}

 

{{out}}

superPerm(10) len = 4037913

superPerm(11) len = 43954713

</pre>

 

=={{header|Objeck}}==

{{trans|C}}

@super : static : Char[];

@pos : static : Int;

};

@super[@pos++] := c;

return true;

}

 

@pos := n;

len := FactSum(n);

 

tmp := Char->New[len + 1];

@super := tmp;

 

}

}

 

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

8: 80640 109600</pre>

The permutations are generated in lexicographic order, and it seems prepending them leads to smaller strings than adding to the end. These are still quite a bit larger than the heuristic methods.

 

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

superPerm(8) len = 48703 (>46233, 2 minutes and 43s)

</pre>

 

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

7 : len = 5913 : (1 2 3 4 5 6 7 1 2 3 4 5 6 1 7 2 3 4 5 6 .. 6 5 4 3 2 7 1 6 5 4 3 2 1 7 6 5 4 3 2 1)

8 : len = 46233 : (1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 1 8 2 3 4 .. 4 3 2 8 1 7 6 5 4 3 2 1 8 7 6 5 4 3 2 1)</pre>

 

=={{header|REXX}}==

===version 1===

This REXX version just does simple finds for the permutations.

parse arg cycles . /*obtain optional arguments from the CL*/

 

do n=0 to cycles

 

do while aPerm(n, 0)

 

end /*cycle*/

/*──────────────────────────────────────────────────────────────────────────────────────*/

if i==0 then return 0

<pre>

</pre>

 

===version 2===

parse arg cycles . /*obtain optional arguments from the CL*/

 

do n=0 to cycles

 

do j=1 while c\==#

end

 

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

iterate j

end

iterate j

end

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

end /*j*/

/*──────────────────────────────────────────────────────────────────────────────────────*/

aPerm: procedure expose @.; parse arg n,i; nm=n-1; if n==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

<pre>

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

9: len = 409113 :12345678912345678192....29187654321987654321

10: len = 4037913 :123456789a1234567891....1987654321a987654321

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

7: 10080 13699

8: 80640 109600

</pre>

 

{{trans|C}}

It crawls ...

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

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

println();

{{out}}

<pre>