在给定分组元素列表时查找哈希的所有可能排列

Question

展示我正在尝试做的事情的最佳方式：我有一个不同哈希的列表，这些哈希由有序元素组成，用下划线分隔。每个元素可能有也可能没有其他可能的替换值。在考虑替换值后，我正在尝试生成此哈希所有可能组合的列表。

示例： grouped_elements = [["1", "1a", "1b"], ["3", "3a"]] original_hash = "1_2_3_4_5"

我希望能够生成以下哈希的列表：

[
 "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",
]

挑战在于大型数据帧需要这样做。

到目前为止，这是我所拥有的：

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)

但问题在于，这只会附加给定 grouped_element 的所有组合的散列，而不是同时附加所有 grouped_elements 的所有组合。所以使用上面的例子，我的函数将 return:

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

我觉得我离解决方案不远了，但我也觉得卡住了，所以非常感谢任何帮助！

Answer 1

如果您列出原始散列值的元素并将每个元素替换为其所有可能变体的列表，则可以使用 itertools.product 获取这些子列表的笛卡尔积。使用 '_'.join() 将结果的每个元素转换回字符串将为您提供可能的哈希列表：

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']

要对存储在数据框列中的各种原始哈希值使用此函数，您可以这样做：

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

在给定分组元素列表时查找哈希的所有可能排列

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

python

statistics

pandas