两个长度不等的表之间的排列

我很难理解我要实现的一个算法。我有两个链表，我想从这两个链表中取特定的组合。

举个例子。

names = ['a', 'b']
numbers = [1, 2]

这种情况下的输出将是:

[('a', 1), ('b', 2)]
[('b', 1), ('a', 2)]

我可能有更多的名字比数字，即len(names) >= len(numbers)。下面是一个有3个名字和2个数字的例子:

names = ['a', 'b', 'c']
numbers = [1, 2]

输出:

[('a', 1), ('b', 2)]
[('b', 1), ('a', 2)]
[('a', 1), ('c', 2)]
[('c', 1), ('a', 2)]
[('b', 1), ('c', 2)]
[('c', 1), ('b', 2)]
290868 次浏览
小开
最佳答案

请注意:这个答案是针对上面所问的特定问题的。如果你从谷歌来到这里，只是在寻找一种在Python中得到笛卡尔积的方法，itertools.product或一个简单的列表理解可能是你要找的-请参阅其他答案。

假设len(list1) >= len(list2)。然后，你似乎想要的是从list1中获取长度len(list2)的所有排列，并将它们与list2中的项匹配。在python中:

import itertools
list1=['a','b','c']
list2=[1,2]


[list(zip(x,list2)) for x in itertools.permutations(list1,len(list2))]

返回

[[('a', 1), ('b', 2)], [('a', 1), ('c', 2)], [('b', 1), ('a', 2)], [('b', 1), ('c', 2)], [('c', 1), ('a', 2)], [('c', 1), ('b', 2)]]
小开

对interjay的答案进行了微小的改进，使结果作为一个平坦的列表。

>>> list3 = [zip(x,list2) for x in itertools.permutations(list1,len(list2))]
>>> import itertools
>>> chain = itertools.chain(*list3)
>>> list4 = list(chain)
[('a', 1), ('b', 2), ('a', 1), ('c', 2), ('b', 1), ('a', 2), ('b', 1), ('c', 2), ('c', 1), ('a', 2), ('c', 1), ('b', 2)]

引用的链接

小开

最简单的方法是使用itertools.product:

a = ["foo", "melon"]
b = [True, False]
c = list(itertools.product(a, b))
>> [("foo", True), ("foo", False), ("melon", True), ("melon", False)]
小开

没有itertools作为扁平列表:

[(list1[i], list2[j]) for i in range(len(list1)) for j in range(len(list2))]

或在Python 2中:

[(list1[i], list2[j]) for i in xrange(len(list1)) for j in xrange(len(list2))]
小开

可能比上面最简单的一个更简单:

>>> a = ["foo", "bar"]
>>> b = [1, 2, 3]
>>> [(x,y) for x in a for y in b]  # for a list
[('foo', 1), ('foo', 2), ('foo', 3), ('bar', 1), ('bar', 2), ('bar', 3)]
>>> ((x,y) for x in a for y in b)  # for a generator if you worry about memory or time complexity.
<generator object <genexpr> at 0x1048de850>

没有任何进口

小开

我正在寻找一个列表乘以自身只有唯一的组合，这是提供作为这个函数。

import itertools
itertools.combinations(list, n_times)

下面是itertools中的Python文档的摘录，它可能会帮助你找到你要找的东西。

Combinatoric generators:


Iterator                                 | Results
-----------------------------------------+----------------------------------------
product(p, q, ... [repeat=1])            | cartesian product, equivalent to a
|   nested for-loop
-----------------------------------------+----------------------------------------
permutations(p[, r])                     | r-length tuples, all possible
|   orderings, no repeated elements
-----------------------------------------+----------------------------------------
combinations(p, r)                       | r-length tuples, in sorted order, no
|   repeated elements
-----------------------------------------+----------------------------------------
combinations_with_replacement(p, r)      | r-length tuples, in sorted order,
| with repeated elements
-----------------------------------------+----------------------------------------
product('ABCD', repeat=2)                | AA AB AC AD BA BB BC BD CA CB CC CD DA DB DC DD
permutations('ABCD', 2)                  | AB AC AD BA BC BD CA CB CD DA DB DC
combinations('ABCD', 2)                  | AB AC AD BC BD CD
combinations_with_replacement('ABCD', 2) | AA AB AC AD BB BC BD CC CD DD
小开

你可能想尝试一行列表理解:

>>> [name+number for name in 'ab' for number in '12']
['a1', 'a2', 'b1', 'b2']
>>> [name+number for name in 'abc' for number in '12']
['a1', 'a2', 'b1', 'b2', 'c1', 'c2']
小开

回答“给定两个列表，从每个列表中找到一个项对的所有可能排列”的问题，并使用基本的Python功能(即不使用itertools)，从而使其易于复制到其他编程语言:

def rec(a, b, ll, size):
ret = []
for i,e in enumerate(a):
for j,f in enumerate(b):
l = [e+f]
new_l = rec(a[i+1:], b[:j]+b[j+1:], ll, size)
if not new_l:
ret.append(l)
for k in new_l:
l_k = l + k
ret.append(l_k)
if len(l_k) == size:
ll.append(l_k)
return ret


a = ['a','b','c']
b = ['1','2']
ll = []
rec(a,b,ll, min(len(a),len(b)))
print(ll)

返回

[['a1', 'b2'], ['a1', 'c2'], ['a2', 'b1'], ['a2', 'c1'], ['b1', 'c2'], ['b2', 'c1']]
小开

找出大量列表的所有组合的最好方法是:

import itertools
from pprint import pprint


inputdata = [
['a', 'b', 'c'],
['d'],
['e', 'f'],
]
result = list(itertools.product(*inputdata))
pprint(result)

结果将是:

[('a', 'd', 'e'),
('a', 'd', 'f'),
('b', 'd', 'e'),
('b', 'd', 'f'),
('c', 'd', 'e'),
('c', 'd', 'f')]
小开

或者用KISS回答简短的清单:

[(i, j) for i in list1 for j in list2]

性能不如itertools，但你使用的是python，所以性能已经不是你最关心的…

我也喜欢其他的答案!

小开

更好的答案只适用于所提供的特定长度的列表。

这里有一个版本，适用于任何长度的输入。同时，从组合和排列的数学概念上明确了算法。

from itertools import combinations, permutations
list1 = ['1', '2']
list2 = ['A', 'B', 'C']


num_elements = min(len(list1), len(list2))
list1_combs = list(combinations(list1, num_elements))
list2_perms = list(permutations(list2, num_elements))
result = [
tuple(zip(perm, comb))
for comb in list1_combs
for perm in list2_perms
]


for idx, ((l11, l12), (l21, l22)) in enumerate(result):
print(f'{idx}: {l11}{l12} {l21}{l22}')

这个输出:

0: A1 B2
1: A1 C2
2: B1 A2
3: B1 C2
4: C1 A2
5: C1 B2

提交答案