Superpermutation minimisation: Difference between revisions
No edit summary |
|||
Line 395: | Line 395: | ||
=={{header|Ruby}}== |
=={{header|Ruby}}== |
||
<lang ruby> |
<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 |
|||
#this task I am going to start from an empty array and generate the whole strings using just the |
|||
#rules. |
|||
# |
|||
#Nigel Galloway: December 16th., 2014 |
|||
# |
|||
l = [] |
|||
(1..6).each{|e| |
|||
a, i = [], e-2 |
|||
(0..l.length-e+1).each{|g| |
|||
if not (n = l[g..g+e-2]).uniq! |
|||
a.concat(n[(a[0]? i : 0)..-1]).push(e).concat(n) |
|||
i = e-2 |
|||
else |
|||
i -= 1 |
|||
end |
|||
} |
|||
a.each{|n| print n}; puts "\n\n" |
|||
l = a |
|||
} |
|||
</lang> |
</lang> |
||
{{out}} |
|||
<pre> |
|||
1 |
|||
121 |
|||
123121321 |
|||
123412314231243121342132413214321 |
|||
123451234152341253412354123145231425314235142315423124531243512431524312543121345213425134215342135421324513241532413524132541321453214352143251432154321 |
|||
123456123451623451263451236451234651234156234152634152364152346152341652341256341253641253461253416253412653412356412354612354162354126354123654123145623145263145236145231645231465231425631425361425316425314625314265314235614235164235146235142635142365142315642315462315426315423615423165423124563124536124531624531264531246531243561243516243512643512463512436512431562431526431524631524361524316524312564312546312543612543162543126543121345621345261345216345213645213465213425613425163425136425134625134265134215634215364215346215342615342165342135642135462135426135421635421365421324561324516324513624513264513246513241563241536241532641532461532416532413562413526413524613524163524136524132564132546132541632541362541326541321456321453621453261453216453214653214356214352614352164352146352143652143256143251643251463251436251432651432156432154632154362154326154321654321 |
|||
</pre> |
Revision as of 15:16, 17 December 2014
A superpermutation of N different characters is a string consisting of an arrangement of multiple copies of those N different characters in which every permutation of those characters can be found as a substring.
For example, representing the characters as A..Z, using N=2 we choose to use the first three characters 'AB'. The permutations of 'AB' are the two (i.e. N!), strings: 'AB' and 'BA'.
A too obvious method of generating a superpermutation is to just join all the permutations together forming 'ABBA'.
A little thought will produce the shorter (in fact the shortest) superpermutation of 'ABA' - it contains 'AB' at the beginning and contains 'BA' from the middle to the end.
The "too obvious" method of creation generates a string of length N!*N. Using this as a yardstick, the task is to investigate other methods of generating superpermutations of N from 1-to-7 characters, that never generate larger superpermutations.
Show descriptions and comparisons of algorithms used here, and select the "Best" algorithm as being the one generating shorter superpermutations.
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
- The Minimal Superpermutation Problem. by Nathaniel Johnston.
- oeis A180632 gives 0-5 as 0, 1, 3, 9, 33, 153. 6 is thought to be 872.
C
Finding a string whose length follows OEIS A007489. Complexity is the length of output string. It is know to be not optimal. <lang c>#include <stdio.h>
- include <stdlib.h>
- include <string.h>
- define MAX 12
char *super = 0; int pos, cnt[MAX];
// 1! + 2! + ... + n! int fact_sum(int n) { int s, x, f; for (s = 0, x = 0, f = 1; x < n; f *= ++x, s += f); return s; }
int r(int n) { if (!n) return 0;
char c = super[pos - n]; if (!--cnt[n]) { cnt[n] = n; if (!r(n-1)) return 0; } super[pos++] = c; return 1; }
void superperm(int n) { int i, len;
pos = n; len = fact_sum(n); super = realloc(super, len + 1); super[len] = '\0';
for (i = 0; i <= n; i++) cnt[i] = i; for (i = 1; i <= n; i++) super[i - 1] = i + '0';
while (r(n)); }
int main(void) { int n; for (n = 0; n < MAX; n++) { printf("superperm(%2d) ", n); superperm(n); printf("len = %d", (int)strlen(super)); // uncomment next line to see the string itself // printf(": %s", super); putchar('\n'); }
return 0; }</lang>
- Output:
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
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. <lang d>import std.stdio, std.ascii, std.algorithm, core.memory, permutations2;
/** Uses greedy algorithm of adding another char (or two, or three, ...) until an unseen perm is formed in the last n chars. */ string superpermutation(in uint n) nothrow in {
assert(n > 0 && n < uppercase.length);
} out(result) {
// It's a superpermutation. assert(uppercase[0 .. n].dup.permutations.all!(p => result.canFind(p)));
} body {
string result = uppercase[0 .. n];
bool[const char[]] toFind; GC.disable; foreach (const perm; result.dup.permutations) toFind[perm] = true; GC.enable; toFind.remove(result);
auto trialPerm = new char[n]; auto auxAdd = new char[n];
while (toFind.length) { MIDDLE: foreach (immutable skip; 1 .. n) { auxAdd[0 .. skip] = result[$ - n .. $ - n + skip]; foreach (const trialAdd; auxAdd[0 .. skip].permutations!false) { trialPerm[0 .. n - skip] = result[$ + skip - n .. $]; trialPerm[n - skip .. $] = trialAdd[]; if (trialPerm in toFind) { result ~= trialAdd; toFind.remove(trialPerm); break MIDDLE; } } } }
return result;
}
void main() {
foreach (immutable n; 1 .. 8) n.superpermutation.length.writeln;
}</lang>
- Output:
1 3 9 35 164 932 6247
Using the ldc2 compiler with n=10, it finds the result string of length 4_235_533 in less than 9 seconds.
Python
<lang python>"Generate a short Superpermutation of n characters A... as a string using various algorithms."
from __future__ import print_function, division
from itertools import permutations from math import factorial import string import datetime import gc
MAXN = 7
def s_perm0(n):
""" Uses greedy algorithm of adding another char (or two, or three, ...) until an unseen perm is formed in the last n chars """ allchars = string.ascii_uppercase[:n] allperms = [.join(p) for p in permutations(allchars)] sp, tofind = allperms[0], set(allperms[1:]) while tofind: for skip in range(1, n): for trial_add in (.join(p) for p in permutations(sp[-n:][:skip])): #print(sp, skip, trial_add) trial_perm = (sp + trial_add)[-n:] if trial_perm in tofind: #print(sp, skip, trial_add) sp += trial_add tofind.discard(trial_perm) trial_add = None # Sentinel break if trial_add is None: break assert all(perm in sp for perm in allperms) # Check it is a superpermutation return sp
def s_perm1(n):
""" Uses algorithm of concatenating all perms in order if not already part of concatenation. """ allchars = string.ascii_uppercase[:n] allperms = [.join(p) for p in sorted(permutations(allchars))] perms, sp = allperms[::], while perms: nxt = perms.pop() if nxt not in sp: sp += nxt assert all(perm in sp for perm in allperms) return sp
def s_perm2(n):
""" Uses algorithm of concatenating all perms in order first-last-nextfirst- nextlast... if not already part of concatenation. """ allchars = string.ascii_uppercase[:n] allperms = [.join(p) for p in sorted(permutations(allchars))] perms, sp = allperms[::], while perms: nxt = perms.pop(0) if nxt not in sp: sp += nxt if perms: nxt = perms.pop(-1) if nxt not in sp: sp += nxt assert all(perm in sp for perm in allperms) return sp
def _s_perm3(n, cmp):
""" Uses algorithm of concatenating all perms in order first, next_with_LEASTorMOST_chars_in_same_position_as_last_n_chars, ... """ allchars = string.ascii_uppercase[:n] allperms = [.join(p) for p in sorted(permutations(allchars))] perms, sp = allperms[::], while perms: lastn = sp[-n:] nxt = cmp(perms, key=lambda pm: sum((ch1 == ch2) for ch1, ch2 in zip(pm, lastn))) perms.remove(nxt) if nxt not in sp: sp += nxt assert all(perm in sp for perm in allperms) return sp
def s_perm3_max(n):
""" Uses algorithm of concatenating all perms in order first, next_with_MOST_chars_in_same_position_as_last_n_chars, ... """ return _s_perm3(n, max)
def s_perm3_min(n):
""" Uses algorithm of concatenating all perms in order first, next_with_LEAST_chars_in_same_position_as_last_n_chars, ... """ return _s_perm3(n, min)
longest = [factorial(n) * n for n in range(MAXN + 1)]
weight, runtime = {}, {}
print(__doc__)
for algo in [s_perm0, s_perm1, s_perm2, s_perm3_max, s_perm3_min]:
print('\n###\n### %s\n###' % algo.__name__) print(algo.__doc__) weight[algo.__name__], runtime[algo.__name__] = 1, datetime.timedelta(0) for n in range(1, MAXN + 1): gc.collect() gc.disable() t = datetime.datetime.now() sp = algo(n) t = datetime.datetime.now() - t gc.enable() runtime[algo.__name__] += t lensp = len(sp) wt = (lensp / longest[n]) ** 2 print(' For N=%i: SP length %5i Max: %5i Weight: %5.2f' % (n, lensp, longest[n], wt)) weight[algo.__name__] *= wt weight[algo.__name__] **= 1 / n # Geometric mean weight[algo.__name__] = 1 / weight[algo.__name__] print('%*s Overall Weight: %5.2f in %.1f seconds.' % (29, , weight[algo.__name__], runtime[algo.__name__].total_seconds()))
print('\n###\n### Algorithms ordered by shortest superpermutations first\n###') print('\n'.join('%12s (%.3f)' % kv for kv in
sorted(weight.items(), key=lambda keyvalue: -keyvalue[1])))
print('\n###\n### Algorithms ordered by shortest runtime first\n###') print('\n'.join('%12s (%.3f)' % (k, v.total_seconds()) for k, v in
sorted(runtime.items(), key=lambda keyvalue: keyvalue[1])))
</lang>
- Output:
Generate a short Superpermutation of n characters A... as a string using various algorithms. ### ### s_perm0 ### Uses greedy algorithm of adding another char (or two, or three, ...) until an unseen perm is formed in the last n chars For N=1: SP length 1 Max: 1 Weight: 1.00 For N=2: SP length 3 Max: 4 Weight: 0.56 For N=3: SP length 9 Max: 18 Weight: 0.25 For N=4: SP length 35 Max: 96 Weight: 0.13 For N=5: SP length 164 Max: 600 Weight: 0.07 For N=6: SP length 932 Max: 4320 Weight: 0.05 For N=7: SP length 6247 Max: 35280 Weight: 0.03 Overall Weight: 6.50 in 0.1 seconds. ### ### s_perm1 ### Uses algorithm of concatenating all perms in order if not already part of concatenation. For N=1: SP length 1 Max: 1 Weight: 1.00 For N=2: SP length 4 Max: 4 Weight: 1.00 For N=3: SP length 15 Max: 18 Weight: 0.69 For N=4: SP length 64 Max: 96 Weight: 0.44 For N=5: SP length 325 Max: 600 Weight: 0.29 For N=6: SP length 1956 Max: 4320 Weight: 0.21 For N=7: SP length 13699 Max: 35280 Weight: 0.15 Overall Weight: 2.32 in 0.1 seconds. ### ### s_perm2 ### Uses algorithm of concatenating all perms in order first-last-nextfirst- nextlast... if not already part of concatenation. For N=1: SP length 1 Max: 1 Weight: 1.00 For N=2: SP length 4 Max: 4 Weight: 1.00 For N=3: SP length 15 Max: 18 Weight: 0.69 For N=4: SP length 76 Max: 96 Weight: 0.63 For N=5: SP length 420 Max: 600 Weight: 0.49 For N=6: SP length 3258 Max: 4320 Weight: 0.57 For N=7: SP length 24836 Max: 35280 Weight: 0.50 Overall Weight: 1.49 in 0.3 seconds. ### ### s_perm3_max ### Uses algorithm of concatenating all perms in order first, next_with_MOST_chars_in_same_position_as_last_n_chars, ... For N=1: SP length 1 Max: 1 Weight: 1.00 For N=2: SP length 4 Max: 4 Weight: 1.00 For N=3: SP length 15 Max: 18 Weight: 0.69 For N=4: SP length 56 Max: 96 Weight: 0.34 For N=5: SP length 250 Max: 600 Weight: 0.17 For N=6: SP length 1482 Max: 4320 Weight: 0.12 For N=7: SP length 10164 Max: 35280 Weight: 0.08 Overall Weight: 3.06 in 50.2 seconds. ### ### s_perm3_min ### Uses algorithm of concatenating all perms in order first, next_with_LEAST_chars_in_same_position_as_last_n_chars, ... For N=1: SP length 1 Max: 1 Weight: 1.00 For N=2: SP length 4 Max: 4 Weight: 1.00 For N=3: SP length 15 Max: 18 Weight: 0.69 For N=4: SP length 88 Max: 96 Weight: 0.84 For N=5: SP length 540 Max: 600 Weight: 0.81 For N=6: SP length 3930 Max: 4320 Weight: 0.83 For N=7: SP length 33117 Max: 35280 Weight: 0.88 Overall Weight: 1.16 in 49.8 seconds. ### ### Algorithms ordered by shortest superpermutations first ### s_perm0 (6.501) s_perm3_max (3.057) s_perm1 (2.316) s_perm2 (1.494) s_perm3_min (1.164) ### ### Algorithms ordered by shortest runtime first ### s_perm0 (0.099) s_perm1 (0.102) s_perm2 (0.347) s_perm3_min (49.764) s_perm3_max (50.192)
Ruby
<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
- this task I am going to start from an empty array and generate the whole strings using just the
- rules.
- Nigel Galloway: December 16th., 2014
l = [] (1..6).each{|e|
a, i = [], e-2 (0..l.length-e+1).each{|g| if not (n = l[g..g+e-2]).uniq! a.concat(n[(a[0]? i : 0)..-1]).push(e).concat(n) i = e-2 else i -= 1 end } a.each{|n| print n}; puts "\n\n" l = a
} </lang>
- Output:
1 121 123121321 123412314231243121342132413214321 123451234152341253412354123145231425314235142315423124531243512431524312543121345213425134215342135421324513241532413524132541321453214352143251432154321 123456123451623451263451236451234651234156234152634152364152346152341652341256341253641253461253416253412653412356412354612354162354126354123654123145623145263145236145231645231465231425631425361425316425314625314265314235614235164235146235142635142365142315642315462315426315423615423165423124563124536124531624531264531246531243561243516243512643512463512436512431562431526431524631524361524316524312564312546312543612543162543126543121345621345261345216345213645213465213425613425163425136425134625134265134215634215364215346215342615342165342135642135462135426135421635421365421324561324516324513624513264513246513241563241536241532641532461532416532413562413526413524613524163524136524132564132546132541632541362541326541321456321453621453261453216453214653214356214352614352164352146352143652143256143251643251463251436251432651432156432154632154362154326154321654321