Skip to content
Snippets Groups Projects

Permutation check for smaller alphabets

  • Clone with SSH
  • Clone with HTTPS
  • Embed
  • Share
    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)
    
    0% Loading or .
    You are about to add 0 people to the discussion. Proceed with caution.
    Please register or to comment