### Paste #pzyntrvqt

1. import itertools
2.
3.
4. def pk(*args):
5.     print(*args)
6.     return args[-1]
7.
8.
9. def combinations(tab):
10.     out = []
11.     for i in range(1, len(tab) + 1):
12.         out.extend(''.join(x) for x in itertools.combinations(tab, i))
13.
14.     assert len(out) == 2**len(tab) - 1
15.     return out
16.
17.
18. def solve(tab, seed=None):
19.     if seed is None:
20.         solutions = []
21.     else:
22.         solutions = seed
23.
24.     cx = combinations(tab)
25.
26.     px = ["".join(x) for x in itertools.permutations(tab) if "".join(x)]
27.
28.     for combination in cx:
29.         pcx = [''.join(x) for x in itertools.permutations(combination)]
30.         # check for existing solution
31.         for solution in solutions:
32.             if any(solution.startswith(p) for p in pcx):
33.                 # yeah, there is an existing solution
34.                 break
35.         else:
36.             # there is no existing solution that is "permutation prefix" of the combination
37.             candidates = [p for p in px if p not in solutions]
38.             for candidate in candidates:
39.                 if any(candidate.startswith(p) for p in pcx):
40.                     # candidate is solution
41.                     solutions.append(candidate)
42.                     break
43.             else:
44.                 assert False, "should not happen, because..."
45.     return solutions
46.
47. def ok(solutions, tab):
48.     cx = combinations(tab)
49.
50.     px = ["".join(x) for x in itertools.permutations(tab) if "".join(x)]
51.
52.     for combination in cx:
53.         pcx = [''.join(x) for x in itertools.permutations(combination)]
54.         # check for existing solution
55.         for solution in solutions:
56.             if any(solution.startswith(p) for p in pcx):
57.                 # yeah, there is an existing solution
58.                 break
59.         else:
60.             break
61.     else:
62.         return True
63.     return False
64.
65.
66. # for i in range(6):
67. #     tab = ''.join(str(x) for x in range(i))
68. #     rotations = [(tab[i:] + tab[:i]) for i in range(len(tab))]
69. #     out = solve(tab, rotations)
70. #     print(i, len(out))
71. #     print(ok(out, tab))
72.
73. s_5 = [
74.     (0, 1, 3, 2, 4),
75.     (0, 2, 1, 3, 4),
76.     (0, 4, 3, 2, 1),
77.     (1, 2, 4, 0, 3),
78.     (1, 3, 4, 0, 2),
79.     (2, 3, 1, 0, 4),
80.     (3, 0, 2, 1, 4),
81.     (3, 4, 1, 2, 0),
82.     (4, 2, 3, 0, 1),
83.     (4, 1, 0, 3, 2),
84.     (4, 0, 2, 3, 1)
85. ]
86.
87. seed = []
88.
89. for s in s_5:
90.     seed.append(''.join(str(x) for x in s))
91.
92.
93. print(ok(seed, '01234'))
94. print(set(solve('01234', seed)) == set(seed))