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"