OCR相似字符场景下，如何按指定顺序生成数组全组合？

你已经搞定了最关键的前置步骤——按置信度从低到高排序字符分组，接下来要做的就是生成这些分组的笛卡尔积，同时严格保持分组的顺序（毕竟要优先替换置信度低的字符）。下面是清晰的思路和伪代码：

核心思路 #

我们的目标是把每个分组里的字符，和其他所有分组的字符进行全组合，并且保持分组的先后顺序（比如第一个分组的每个元素，都要和第二个分组的每个元素配对，以此类推）。这本质就是求多个集合的笛卡尔积，用迭代的方式实现最直观，容易理解和调试。

伪代码实现 #

FUNCTION generate_all_combinations(sorted_groups):
    # sorted_groups: 按置信度从低到高排序的分组列表，每个分组是[原字符, 相似字符1, 相似字符2, ...]
    
    # 处理边界情况：如果没有分组，返回空列表
    IF sorted_groups IS EMPTY:
        RETURN EMPTY LIST
    
    # 初始化结果：第一个分组的每个字符作为单独的组合
    result = [ [char] FOR char IN sorted_groups[0] ]
    
    # 遍历剩下的每个分组
    FOR group IN sorted_groups[1:]:
        # 临时存储新生成的组合
        temp_combinations = EMPTY LIST
        
        # 对当前结果里的每个组合，都和当前分组的每个字符拼接
        FOR combo IN result:
            FOR char IN group:
                # 复制原组合，然后添加当前字符，避免修改原组合
                new_combo = COPY(combo)
                new_combo.append(char)
                temp_combinations.append(new_combo)
        
        # 更新结果为新生成的组合列表
        result = temp_combinations
    
    RETURN result

示例验证 #

示例1 #

输入分组：[ ['1', 'l', 'I'], ['0', 'O'] ]

1. 初始结果：[ ['1'], ['l'], ['I'] ]
2. 处理第二个分组['0','O']：
   • 对['1']，生成['1','0']、['1','O']
   • 对['l']，生成['l','0']、['l','O']
   • 对['I']，生成['I','0']、['I','O']
3. 最终结果：[ ['1', '0'], ['l', '0'], ['I', '0'], ['1', 'O'], ['l', 'O'], ['I', 'O'] ]，完全符合预期。

示例2 #

输入分组：[ ['0', 'O'], ['2', 'Z'], ['5', 'S'] ]

1. 初始结果：[ ['0'], ['O'] ]
2. 处理第二个分组后：[ ['0','2'], ['0','Z'], ['O','2'], ['O','Z'] ]
3. 处理第三个分组后，每个组合分别加上'5'和'S'，最终得到8个组合，和需求一致。

补充说明 #

• 这里的COPY(combo)很重要，因为如果直接修改原组合，会导致后续迭代出错，所以必须生成新的列表。
• 迭代方式比递归更适合这里，尤其是当分组数量较多时，不会有栈溢出的问题，也更容易跟踪中间结果。

内容的提问来源于stack exchange，提问作者Marvin