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)