Source code for tryalgo.next_permutation
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""\
Next permutation
prochaine permuation
jill-jênn vie et christoph dürr - 2014-2020
"""
from sys import argv
import sys
from tryalgo.our_std import readint, readstr
# snip{
# pylint: disable=redefined-outer-name
[docs]
def next_permutation(tab):
"""find the next permutation of tab in the lexicographical order
:param tab: table with n elements from an ordered set
:modifies: table to next permutation
:returns: False if permutation is already lexicographical maximal
:complexity: O(n)
"""
n = len(tab)
pivot = None # find pivot
for i in range(n - 1):
if tab[i] < tab[i + 1]:
pivot = i
if pivot is None: # tab is already the last perm.
return False
for i in range(pivot + 1, n): # find the element to swap
if tab[i] > tab[pivot]:
swap = i
tab[swap], tab[pivot] = tab[pivot], tab[swap]
i = pivot + 1
j = n - 1 # invert suffix
while i < j:
tab[i], tab[j] = tab[j], tab[i]
i += 1
j -= 1
return True
# snip}
# snip{ word_addition
# pylint: disable=redefined-outer-name
[docs]
def convert(word, ass):
"""
solves a cryptogram in the style SEND + MORE = MONEY
"""
retval = 0
for x in word:
retval = 10 * retval + ass[x]
return retval
# pylint: disable=redefined-outer-name
[docs]
def solve_word_addition(S): # returns number of solutions
"""returns number of solutions"""
n = len(S)
letters = sorted(list(set(''.join(S))))
not_zero = '' # letters that cannot be 0
for word in S:
not_zero += word[0]
tab = ['@'] * (10 - len(letters)) + letters # minimal lex permutation
count = 0
while True:
ass = {tab[i]: i for i in range(10)} # dict = associative array
if tab[0] not in not_zero:
difference = -convert(S[n - 1], ass) # do the addition
for word in S[:n - 1]:
difference += convert(word, ass)
if difference == 0: # does it add up?
count += 1
if not next_permutation(tab):
break
return count
# snip}
if __name__ == "__main__":
if len(argv) > 1:
L = argv[1:]
if len(L) == 1:
L = list(L[0])
while True:
print(L)
if not next_permutation(L):
sys.exit(0)
n = readint()
S = [readstr() for _ in range(n)]
print(solve_word_addition(S))