def powerSet(items):
"""
Power set generator: get all possible combinations of a list’s elements
Input:
items is a list
Output:
returns 2**n combination lists one at a time using a generator
Reference: edx.org 6.00.2x Lecture 2 - Decision Trees and dynamic programming
"""
N = len(items)
# enumerate the 2**N possible combinations
for i in range(2**N):
combo = []
for j in range(N):
# test bit jth of integer i
if (i >> j) % 2 == 1:
combo.append(items[j])
yield combo
简单的Yield Yield用法:
for i in powerSet([1,2,3,4]):
print (i, ", ", end="")
def get_combinations(list_of_things):
"""gets every combination of things in a list returned as a list of lists
Should be read : add all combinations of a certain size to the end of a list for every possible size in the
the list_of_things.
"""
list_of_combinations = [list(combinations_of_a_certain_size)
for possible_size_of_combinations in range(1, len(list_of_things))
for combinations_of_a_certain_size in itertools.combinations(list_of_things,
possible_size_of_combinations)]
return list_of_combinations
516
下面是"standard recursive answer",类似于其他类似答案https://stackoverflow.com/a/23743696/711085 . (我们不能't realistically have to worry about running out of stack space since there'我们无法处理所有N!排列 . )
它依次访问每个元素,并接受或离开它(我们可以直接从该算法中看到2 ^ N基数) .
def combs(xs, i=0):
if i==len(xs):
yield ()
return
for c in combs(xs,i+1):
yield c
yield c+(xs[i],)
# FUNCTION getCombos: To generate all combos of an input list, consider the following sets of nested lists...
#
# [ [ [] ] ]
# [ [ [] ], [ [A] ] ]
# [ [ [] ], [ [A],[B] ], [ [A,B] ] ]
# [ [ [] ], [ [A],[B],[C] ], [ [A,B],[A,C],[B,C] ], [ [A,B,C] ] ]
# [ [ [] ], [ [A],[B],[C],[D] ], [ [A,B],[A,C],[B,C],[A,D],[B,D],[C,D] ], [ [A,B,C],[A,B,D],[A,C,D],[B,C,D] ], [ [A,B,C,D] ] ]
#
# There is a set of lists for each number of items that will occur in a combo (including an empty set).
# For each additional item, begin at the back of the list by adding an empty list, then taking the set of
# lists in the previous column (e.g., in the last list, for sets of 3 items you take the existing set of
# 3-item lists and append to it additional lists created by appending the item (4) to the lists in the
# next smallest item count set. In this case, for the three sets of 2-items in the previous list. Repeat
# for each set of lists back to the initial list containing just the empty list.
#
def getCombos(listIn = ['A','B','C','D','E','F'] ):
listCombos = [ [ [] ] ] # list of lists of combos, seeded with a list containing only the empty list
listSimple = [] # list to contain the final returned list of items (e.g., characters)
for item in listIn:
listCombos.append([]) # append an emtpy list to the end for each new item added
for index in xrange(len(listCombos)-1, 0, -1): # set the index range to work through the list
for listPrev in listCombos[index-1]: # retrieve the lists from the previous column
listCur = listPrev[:] # create a new temporary list object to update
listCur.append(item) # add the item to the previous list to make it current
listCombos[index].append(listCur) # list length and append it to the current list
itemCombo = '' # Create a str to concatenate list items into a str
for item in listCur: # concatenate the members of the lists to create
itemCombo += item # create a string of items
listSimple.append(itemCombo) # add to the final output list
return [listSimple, listCombos]
# END getCombos()
2
我知道使用itertools来获取所有组合更加实际,但如果你碰巧想要的话,你只能通过列表理解来实现这一点,授予你想要编码 a lot
对于两对的组合:
lambda l: [(a, b) for i, a in enumerate(l) for b in l[i+1:]]
而且,对于三对组合,它就像这样简单:
lambda l: [(a, b, c) for i, a in enumerate(l) for ii, b in enumerate(l[i+1:]) for c in l[i+ii+2:]]
结果与使用itertools.combinations相同:
import itertools
combs_3 = lambda l: [
(a, b, c) for i, a in enumerate(l)
for ii, b in enumerate(l[i+1:])
for c in l[i+ii+2:]
]
data = ((1, 2), 5, "a", None)
print("A:", list(itertools.combinations(data, 3)))
print("B:", combs_3(data))
# A: [((1, 2), 5, 'a'), ((1, 2), 5, None), ((1, 2), 'a', None), (5, 'a', None)]
# B: [((1, 2), 5, 'a'), ((1, 2), 5, None), ((1, 2), 'a', None), (5, 'a', None)]
2
不使用itertools:
def combine(inp):
return combine_helper(inp, [], [])
def combine_helper(inp, temp, ans):
for i in range(len(inp)):
current = inp[i]
remaining = inp[i + 1:]
temp.append(current)
ans.append(tuple(temp))
combine_helper(remaining, temp, ans)
temp.pop()
return ans
print(combine(['a', 'b', 'c', 'd']))
14
来自itertools的组合
import itertools
col_names = ["aa","bb", "cc", "dd"]
all_combinations = itertools.chain(*[itertools.combinations(col_names,i+1) for i,_ in enumerate(col_names)])
print(list(all_combinations))
谢谢
5
可以使用itertools完成
For permutations
此方法将列表作为输入,并返回包含列表形式的长度为L的排列的元组的对象列表 .
# A Python program to print all
# permutations of given length
from itertools import permutations
# Get all permutations of length 2
# and length 2
perm = permutations([1, 2, 3], 2)
# Print the obtained permutations
for i in list(perm):
print (i)
For Combination
此方法将列表和输入r作为输入,并返回元组的对象列表,其中包含列表形式中长度为r的所有可能组合 .
# A Python program to print all
# combinations of given length
from itertools import combinations
# Get all combinations of [1, 2, 3]
# and length 2
comb = combinations([1, 2, 3], 2)
# Print the obtained combinations
for i in list(comb):
print (i)
def combinations(lst, depth, start=0, items=[]):
if depth <= 0:
return [items]
out = []
for i in range(start, len(lst)):
out += combinations(lst, depth - 1, i + 1, items + [lst[i]])
return out
一个人返回一个发电机
def combinations(lst, depth, start=0, prepend=[]):
if depth <= 0:
yield prepend
else:
for i in range(start, len(lst)):
for c in combinations(lst, depth - 1, i + 1, prepend + [lst[i]]):
yield c
请注意,建议为这些提供辅助函数,因为prepend参数是静态的,并且不会随每次调用而改变
print([c for c in combinations([1, 2, 3, 4], 3)])
# [[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]
# get a hold of prepend
prepend = [c for c in combinations([], -1)][0]
prepend.append(None)
print([c for c in combinations([1, 2, 3, 4], 3)])
# [[None, 1, 2, 3], [None, 1, 2, 4], [None, 1, 3, 4], [None, 2, 3, 4]]
这是一个非常肤浅的案例,但最好是安全而不是抱歉
2
如果有人正在寻找一个反向列表,就像我一样:
stuff = [1, 2, 3, 4]
def reverse(bla, y):
for subset in itertools.combinations(bla, len(bla)-y):
print list(subset)
if y != len(bla):
y += 1
reverse(bla, y)
reverse(stuff, 1)
1
怎么样..使用字符串而不是列表,但同样的事情..字符串可以像Python中的列表一样对待:
def comb(s, res):
if not s: return
res.add(s)
for i in range(0, len(s)):
t = s[0:i] + s[i + 1:]
comb(t, res)
res = set()
comb('game', res)
print(res)
1
在Python 3中 Withoutitertools 你可以这样做:
def combinations(arr, carry):
for i in range(len(arr)):
yield carry + arr[i]
yield from combinations(arr[i + 1:], carry + arr[i])
最初的地方 carry = "".
1
def combinations(iterable, r):
# combinations('ABCD', 2) --> AB AC AD BC BD CD
# combinations(range(4), 3) --> 012 013 023 123
pool = tuple(iterable)
n = len(pool)
if r > n:
return
indices = range(r)
yield tuple(pool[i] for i in indices)
while True:
for i in reversed(range(r)):
if indices[i] != i + n - r:
break
else:
return
indices[i] += 1
for j in range(i+1, r):
indices[j] = indices[j-1] + 1
yield tuple(pool[i] for i in indices)
x = [2, 3, 4, 5, 1, 6, 4, 7, 8, 3, 9]
for i in combinations(x, 2):
print i
23 回答
看看itertools.combinations:
自2.6以来,包括电池!
This answer错过了一个方面:OP要求所有组合...而不仅仅是长度"r"的组合 .
所以你要么必须遍历所有长度“L”:
或者 - 如果你想变得时髦(或弯曲你的代码之后的大脑) - 你可以生成“combination()”生成器链,并迭代:
这是一个懒惰的单行,也使用itertools:
这个答案背后的主要思想:有2 ^ N个组合 - 与长度为N的二进制字符串的数量相同 . 对于每个二进制字符串,您选择对应于“1”的所有元素 .
需要考虑的事项:
这要求您可以在
items
上调用len(...)
(解决方法:如果items
类似于像生成器一样的迭代,请先将其转换为列表,使用items=list(_itemsArg)
)这要求
items
上的迭代顺序不是随机的(解决方法:不要疯狂)这要求项目是唯一的,否则
{2,2,1}
和{2,1,1}
都将折叠为{2,1}
(解决方法:使用collections.Counter
作为set
的替代品;它基本上是一个多重集...但如果你可能需要稍后使用tuple(sorted(Counter(...).elements()))
需要它可以清洗)Demo
在@Dan H高度评价answer的评论中,提到itertools documentation中的
powerset()
食谱 - 包括Dan himself . 但是,到目前为止还没有人发布它作为答案 . 因为它可能是解决问题的最佳方法之一 - 并且从另一位评论者那里获得了little encouragement,如下所示 . 该函数生成 all _166826_长度列表元素的唯一组合(包括那些包含零和所有元素的组合) .Note :如果略有不同,目标是仅获取唯一元素的组合,请将行
s = list(iterable)
更改为s = list(set(iterable))
以消除任何重复元素 . 无论如何,iterable
最终变成list
的事实意味着它将与发生器一起工作(与其他几个答案不同) .输出:
这是一个使用递归:
我同意Dan H的观点,Ben确实要求 all 组合 .
itertools.combinations()
没有给出所有组合 .另一个问题是,如果输入可迭代很大,那么返回生成器而不是列表中的所有内容可能更好:
这个单行为您提供所有组合(如果原始列表/集包含
n
distinct元素,则在0
和n
项之间)并使用本机方法itertools.combinations:输出将是:
在线试用:
http://ideone.com/COghfX
You can generating all combinations of a list in python using this simple code
Result would be :
我想我会为那些寻求答案的人添加这个功能,而无需导入itertools或任何其他额外的库 .
简单的Yield Yield用法:
以上用法示例的输出:
这是另一个解决方案(单线程),涉及使用
itertools.combinations
函数,但这里我们使用双列表理解(而不是for循环或求和):演示:
这是我的实施
下面是"standard recursive answer",类似于其他类似答案https://stackoverflow.com/a/23743696/711085 . (我们不能't realistically have to worry about running out of stack space since there'我们无法处理所有N!排列 . )
它依次访问每个元素,并接受或离开它(我们可以直接从该算法中看到2 ^ N基数) .
演示:
此代码采用嵌套列表的简单算法...
我知道使用itertools来获取所有组合更加实际,但如果你碰巧想要的话,你只能通过列表理解来实现这一点,授予你想要编码 a lot
对于两对的组合:
而且,对于三对组合,它就像这样简单:
结果与使用itertools.combinations相同:
不使用itertools:
来自itertools的组合
谢谢
可以使用itertools完成
For permutations
此方法将列表作为输入,并返回包含列表形式的长度为L的排列的元组的对象列表 .
For Combination
此方法将列表和输入r作为输入,并返回元组的对象列表,其中包含列表形式中长度为r的所有可能组合 .
见this
使用列表理解:
输出将是:
这是
itertools.combinations
的两个实现一个返回列表
一个人返回一个发电机
请注意,建议为这些提供辅助函数,因为prepend参数是静态的,并且不会随每次调用而改变
这是一个非常肤浅的案例,但最好是安全而不是抱歉
如果有人正在寻找一个反向列表,就像我一样:
怎么样..使用字符串而不是列表,但同样的事情..字符串可以像Python中的列表一样对待:
在Python 3中 Without
itertools
你可以这样做:最初的地方
carry = "".