Finding all possible permutations of a hash when given list of grouped elements

user_10489612 0
Viewed 31

Best way to show what I'm trying to do: I have a list of different hashes that consist of ordered elements, seperated by an underscore. Each element may or may not have other possible replacement values. I'm trying to generate a list of all possible combinations of this hash, after taking into account replacement values.

Example: grouped_elements = [["1", "1a", "1b"], ["3", "3a"]] original_hash = "1_2_3_4_5"

I want to be able to generate a list of the following hashes:

[
 "1_2_3_4_5",
 "1a_2_3_4_5",
 "1b_2_3_4_5",
 "1_2_3a_4_5",
 "1a_2_3a_4_5",
 "1b_2_3a_4_5",
]

The challenge is that this'll be needed on large dataframes.

So far here's what I have:

def return_all_possible_hashes(df, grouped_elements)
    rows_to_append = []
    for grouped_element in grouped_elements:
        for index, row in enriched_routes[
            df["hash"].str.contains("|".join(grouped_element))
        ].iterrows():
            (element_used_in_hash,) = set(grouped_element) & set(row["hash"].split("_"))
            hash_used = row["hash"]
            replacement_elements = set(grouped_element) - set([element_used_in_hash])
            for replacement_element in replacement_elements:
                row["hash"] = stop_hash_used.replace(
                    element_used_in_hash, replacement_element
                )
                rows_to_append.append(row)

    return df.append(rows_to_append)

But the problem is that this will only append hashes with all combinations of a given grouped_element, and not all combinations of all grouped_elements at the same time. So using the example above, my function would return:

[
 "1_2_3_4_5",
 "1a_2_3_4_5",
 "1b_2_3_4_5",
 "1_2_3a_4_5",
]

I feel like I'm not far from the solution, but I also feel stuck, so any help is much appreciated!

pandas statistics python
1 Answers

If you make a list of the original hash value's elements and replace each element with a list of all its possible variations, you can use itertools.product to get the Cartesian product across these sublists. Transforming each element of the result back to a string with '_'.join() will get you the list of possible hashes:

from itertools import product


def possible_hashes(original_hash, grouped_elements):
    
    hash_list = original_hash.split('_')
    variations = list(set().union(*grouped_elements))
    
    var_list = hash_list.copy()
    for i, h in enumerate(hash_list):
        if h in variations:
            for g in grouped_elements:
                if h in g:
                    var_list[i] = g
                    break
        else:
            var_list[i] = [h]
                    
    return ['_'.join(h) for h in product(*var_list)]


possible_hashes("1_2_3_4_5", [["1", "1a", "1b"], ["3", "3a"]]) 

['1_2_3_4_5',
 '1_2_3a_4_5',
 '1a_2_3_4_5',
 '1a_2_3a_4_5',
 '1b_2_3_4_5',
 '1b_2_3a_4_5']

To use this function on various original hash values stored in a dataframe column, you can do something like this:

df['hash'].apply(lambda x: possible_hashes(x, grouped_elements))
user_130141720
Related