从列表的顺序生成链

Generating chains from an order of lists

我正在寻找如何完成我已经掌握但不掌握的事情:

我有 n 个不同大小的列表:

{A, B, C, D}
    {1,2}
       {X, Y, Z}
            ...to the nth potentially

我如何从每个级别 A1X、A1Y、A1Z 等生成 1 个项目的所有可能链。这是一个算法和数学任务,不,它不是家庭作业(我知道学校开学了),它是我的一部分正在处理,我没有代码 --- 我只需要指出正确的方向来制定我的条款。

(你没有要求代码,但我倾向于使用Python来执行伪代码。你仍然需要将核心算法翻译成你选择的语言)。

实际上,您是在谈论形成列表的 Cartesian Product。它可以通过多种方式完成。如果事先不知道列表的数量,则递归方法是最自然的方法。

L1*L2* ... *Ln 表示具有以下形式的所有字符串的列表 s1+s2+...+sn 其中 Li+ 中的 si 是串联运算符。作为基础,您可以采用 n ==1,单个列表,或 n == 0,根本没有列表。在许多方面,后者更优雅,在这种情况下,很自然地将空字符串列表的乘积定义为唯一元素为空字符串的列表。

然后:

Return [''] 如果 n == 0

否则return

[a+b | a ranges over L1 and b ranges over (L2 * L3 * ... * Ln)]

其中 (L2 * L3 * ... *Ln) 已经递归计算(如果 n 为 1,则它只是空字符串)。

最后一个列表可以很容易地在嵌套循环中构建,或者用任何支持 list comprehensions 的语言更直接地表达。

这是一个 Python 实现,其中 return 是给定字符串列表(在代码中缩写为 lls)的所有产品的列表:

def product(lls):
    if len(lls) == 0:
        return ['']
    else:
        return [a+b for a in lls[0] for b in product(lls[1:])]

这样测试:

lists_of_strings = [['A','B','C','D'],['1','2','3'],['X','Y','Z']]
print(product(lists_of_strings))

输出:

['A1X', 'A1Y', 'A1Z', 'A2X', 'A2Y', 'A2Z', 'A3X', 'A3Y', 'A3Z', 'B1X', 'B1Y', 'B1Z', 'B2X', 'B2Y', 'B2Z', 'B3X', 'B3Y', 'B3Z', 'C1X', 'C1Y', 'C1Z', 'C2X', 'C2Y', 'C2Z', 'C3X', 'C3Y', 'C3Z', 'D1X', 'D1Y', 'D1Z', 'D2X', 'D2Y', 'D2Z', 'D3X', 'D3Y', 'D3Z']

在 Python 本身并没有太多的动力去做这个,因为 itertools 模块有一个很好的产品,同样的产品可以表示为:

[''.join(p) for p in itertools.product(*lists_of_strings)]