```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 ``` ```# find shortest string containing all permutations, http://stackoverflow.com/questions/2253232/generate-sequence-with-all-permutations # The length of the shortest string is between: # upper bound: sum(factorial(k) for k in 1...n) http://www.research.att.com/~njas/sequences/A007489 # 1, 3, 9, 33, 153, 873, ... # lower bound: n! - n + 1 http://www.research.att.com/~njas/sequences/A030495 # 1, 3, 8, 27, 124, 725, ... # # known: 1, 3, 9, 33, 153 # # It looks as though the upper bound might be tight. # === Answer #0 - Tree search with pruning based on a pretty tight upper bound from itertools import permutations def fac(n): p = 1 for i in range(2, n + 1): p *= i return p def meld(it): def meld2(a, b): return a + b[-costToAdd(a, b):] return reduce(meld2, it) # This eventually comes back when len(s) == 5, but not when len(s) == 6. def BRUTE_shortestStringContainingAllPermutationsOf(s): n = len(s) perms = [''.join(tpl) for tpl in permutations(s)] N = len(perms) rN = range(N) indices = list(rN) locs = indices[:] costs = [0] * N #best = fac(n - 1) * (2 * n - 1) + 1 # sloppy upper bound + 1 best = sum(fac(k) for k in range(1, n + 1)) + 1 # tighter upper bound + 1 print "starting upper bound:", best bestseq = None def swap(x, y): lx = locs[x] ly = locs[y] indices[lx], indices[ly] = indices[ly], indices[lx] locs[x], locs[y] = ly, lx i = 1 costs[0] = N + n - 1 # lower bound on cost, given what we have so far while 1: # going forward total = costs[i - 1] while 1: total += costToAdd(perms[indices[i-1]], perms[indices[i]]) - 1 if total >= best: break # over budget, start backtracking costs[i] = total i += 1 if i == N: print "new best:", total, meld(perms[idx] for idx in indices) bestseq = indices[:] best = total i -= 1 break # now backtrack, try something else # find the first avaiable thing to try in the next slot for next in rN: if locs[next] >= i: break else: assert 0 # should never happen swap(indices[i], next) # backtracking at i while i: # find an available thing to try next cur = indices[i] next = cur + 1 while next < N: if locs[next] > i: break # it's available next += 1 else: # nothing is available i -= 1 continue # found available index, swap them assert locs[cur] == i swap(cur, next) break else: # backtracked all the way to 0, we're done break return meld(perms[idx] for idx in bestseq) # === Answer #1 - greedy def costToAdd(a, b): for i in range(1, len(b)): if a.endswith(b[:-i]): return i return len(b) def GREEDY_stringContainingAllPermutationsOf(s): perms = set(''.join(tpl) for tpl in itertools.permutations(s)) perms.remove(s) a = s while perms: cost, next = min((costToAdd(a, x), x) for x in perms) perms.remove(next) a += next[-cost:] return a # === Answer #2 - walking the Tree of All Permutations def build(node, s): """String together all ancestors of the given node at depth len(s).""" d = len(node) # depth of this node. depth of "213" is 3. n = len(s) if d == n - 1: return node + s[n - 1] + node # the children of "213" join to make "2134213" else: child = node + s[d] # first child node children = [child[i:] + child[:i] for i in range(d + 1)] # all child nodes strings = [build(child, s) for child in children] # recurse to the desired depth for j in range(1, d + 1): # cut off the overlapping parts strings[j] = strings[j][d:] return ''.join(strings) # join them all def stringContainingAllPermutationsOf(s): return build(s[:1], s) # main s = stringContainingAllPermutationsOf("12345") best = BRUTE_shortestStringContainingAllPermutationsOf("12345") print s == best # this prints "True" ```