Loading

Paste #pbgfientp

1. import itertools
2.
3.
4. def pk(*args):
5.     print(*args)
6.     return args[-1]
7.
8.
9. def solve(tab, seed=None):
10.     if seed is None:
11.         solutions = []
12.     else:
13.         solutions = seed
14.
15.     combinations = []
16.     for i in range(1, len(tab) + 1):
17.         combinations.extend(''.join(x) for x in itertools.combinations(tab, i))
18.
19.     assert len(combinations) == 2**len(tab) - 1
20.
21.     px = ["".join(x) for x in itertools.permutations(tab) if "".join(x)]
22.
23.     for combination in combinations:
24.         pcx = [''.join(x) for x in itertools.permutations(combination)]
25.         # check for existing solution
26.         for solution in solutions:
27.             if any(solution.startswith(p) for p in pcx):
28.                 # yeah, there is an existing solution
29.                 break
30.         else:
31.             # there is no existing solution that is "permutation prefix" of the combination
32.             candidates = [p for p in px if p not in solutions]
33.             for candidate in candidates:
34.                 if any(candidate.startswith(p) for p in pcx):
35.                     # candidate is solution
36.                     solutions.append(candidate)
37.                     break
38.             else:
39.                 assert False, "should not happen, because..."
40.     return solutions
41.
42.
43. tab = '01234567'
44. rotations = [(tab[i:] + tab[:i]) for i in range(len(tab))]
45. out = solve(tab, rotations)
46. print(len(out))
47. for x in out:
48.     print(x)