从列表的顺序生成链
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)]
我正在寻找如何完成我已经掌握但不掌握的事情:
我有 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)]