如何高效生成总长度为n的不等长字符串集合笛卡尔积

问题核心 #

需求是生成字符串集合S的多轮自笛卡尔积，筛选出所有拼接后总长度**严格等于目标值n**的结果。S内元素长度不固定。

• 参考示例：S = ['1', '22', '333']，目标长度n=4时，正确输出为：

['1111', '1122', '1221', '1333', '2211', '2222', '3331']

原有先生成全量S^n笛卡尔积、再截断去重的方案会产生大量长度超标的无效中间结果，数据规模稍大就会耗尽内存和算力，效率极低。

实现思路 #

核心是从根源上避免生成无效组合，采用动态规划按长度递推，全程只保留长度符合要求的中间值：

1. 预处理S：先过滤掉自身长度就大于n的元素（这类元素永远不可能出现在合法结果中），再把剩余元素按长度分组，减少后续重复计算
2. 定义状态dp[l]：存储所有拼接后总长度恰好为l的合法字符串集合
3. 初始状态：dp[0] = {""}，即长度为0时只有空字符串
4. 递推规则：对每个长度l从1遍历到n，遍历所有合法的元素长度k（要求k <= l），将dp[l-k]中所有前缀字符串，拼接上所有长度为k的S内元素，得到的结果全部加入dp[l]
5. 最终dp[n]就是所求的全部结果。

和原方案相比，这个方法的计算量和最终合法结果的总数量线性相关，不会产生任何超长的无效条目，当n较大时效率比全量笛卡尔积方案高几个数量级。

Python 可运行代码 #

from collections import defaultdict

def fixed_length_product(s: list[str], n: int) -> list[str]:
    # 预处理：按元素长度分组，过滤超长无效元素
    len_group = defaultdict(list)
    for item in set(s):  # 先对S去重，避免重复计算
        item_len = len(item)
        if item_len <= n:
            len_group[item_len].append(item)
    valid_lengths = list(len_group.keys())

    # 初始化dp数组
    dp = [set() for _ in range(n + 1)]
    dp[0].add("")

    for current_len in range(1, n + 1):
        for step_len in valid_lengths:
            if step_len > current_len:
                continue
            # 拼接前缀和当前步长的元素
            for prefix in dp[current_len - step_len]:
                for suffix in len_group[step_len]:
                    dp[current_len].add(prefix + suffix)
    
    return list(dp[n])

# 示例测试
if __name__ == "__main__":
    S = ['1', '22', '333']
    target_n = 4
    res = fixed_length_product(S, target_n)
    print(sorted(res))
    # 输出：['1111', '1122', '1221', '1333', '2211', '2222', '3331']

大规模场景优化建议 #

• 如果n极大、结果集量级很高，可以将dp替换为生成器迭代模式，不需要把所有长度的中间结果全量存在内存中，进一步降低内存占用
• 如果不需要对结果去重，可以把dp里的set换成list，省去哈希去重的开销，速度会更快
• 若需要按字典序返回结果，只在最终输出前做一次排序即可，递推过程中排序会增加不必要的性能损耗

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