Permutation check for smaller alphabets
The snippet can be accessed without any authentication.
Authored by
Henke
Edited
cool_hashing.py 1.43 KiB
from functools import reduce
from fractions import gcd
MAXLEN = 3 * 10**12
ALPHABET = '0123'
def index_function(char):
return ord(char) - ord('0')
INDEX_FN = index_function
def lcm(*args):
def reduction(previous, current):
return previous * current / gcd(previous, current)
return reduce(reduction, args, 1)
def _find_base(string1, string2, maxlen, alphabet):
def holds(lcm_value, maximal):
# The last condition is just to restrain the search to 64-bit integers
return lcm_value > maxlen and maxlen * maximal**(len(alphabet) - 1) < 2**64
# Calculate the maximal possible lcm value for a given maximal number, such that the above holds
lcm_value = 2
maximal = 2
while not holds(lcm_value, maximal):
maximal += 1
lcm_value = lcm(lcm_value, maximal)
# Retrieve the base for that lcm value
base = []
while lcm_value > 1 and maximal > 1:
if lcm_value % maximal == 0:
base.append(maximal)
lcm_value = lcm_value / maximal
maximal -= 1
return base
find_base = _find_base
def _hash_for_power(string, power):
return sum(power**INDEX_FN(c) for c in string)
get_hash = _hash_for_power
def is_permutation(string1, string2):
if len(string1) != len(string2):
return False
base = find_base(string1, string2, MAXLEN, ALPHABET)
return all(get_hash(string1, power) == get_hash(string2, power) for power in base)
Please register or sign in to comment