Loading

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))