31 lines
1.1 KiB
Python
31 lines
1.1 KiB
Python
def missing_permutation(arr):
|
|
"Find the missing permutation in an array of N! - 1 permutations."
|
|
|
|
# We won't validate every precondition, but we do have some basic
|
|
# guards.
|
|
if len(arr) == 0: raise Exception("Need more data")
|
|
if len(arr) == 1:
|
|
return [arr[0][1] + arr[0][0]]
|
|
|
|
# Now we know that for each position in the string, elements should appear
|
|
# an even number of times (N-1 >= 2). We can use a set to detect the element appearing
|
|
# an odd number of times. Detect odd occurrences by toggling admission/expulsion
|
|
# to and from the set for each value encountered. At the end of each pass one element
|
|
# will remain in the set.
|
|
missing_permutation = ''
|
|
for pos in range(len(arr[0])):
|
|
s = set()
|
|
for permutation in arr:
|
|
c = permutation[pos]
|
|
if c in s:
|
|
s.remove(c)
|
|
else:
|
|
s.add(c)
|
|
missing_permutation += list(s)[0]
|
|
return missing_permutation
|
|
|
|
given = '''ABCD CABD ACDB DACB BCDA ACBD ADCB CDAB DABC BCAD CADB CDBA
|
|
CBAD ABDC ADBC BDCA DCBA BACD BADC BDAC CBDA DBCA DCAB'''.split()
|
|
|
|
print missing_permutation(given)
|