如何以一切可能的方式将一个列表分成几对
我有一个列表（简单来说就是6个元素）
L = [0, 1, 2, 3, 4, 5] 我想以各种可能的方式把它分成两半。 我展示了一些configuration：
[(0, 1), (2, 3), (4, 5)] [(0, 1), (2, 4), (3, 5)] [(0, 1), (2, 5), (3, 4)]
等等。 这里(a, b) = (b, a) ，对的顺序并不重要
[(0, 1), (2, 3), (4, 5)] = [(0, 1), (4, 5), (2, 3)]
这种configuration的总数是1*3*5*...*(N-1)其中N是我的列表的长度。
我怎样才能用Python编写一个生成器，为我提供了一个任意N所有可能的configuration？
看看itertools.combinations 。
matt@stanley:~$ python Python 2.6.5 (r265:79063, Apr 16 2010, 13:57:41) [GCC 4.4.3] on linux2 Type "help", "copyright", "credits" or "license" for more information. >>> import itertools >>> list(itertools.combinations(range(6), 2)) [(0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)]
我不认为标准库中有任何function可以完全满足您的需求。 只要使用itertools.combinations就可以得到所有可能的单个对的列表，但实际上并不能解决所有有效对组合的问题。
你可以很容易地解决这个问题：
import itertools def all_pairs(lst): for p in itertools.permutations(lst): i = iter(p) yield zip(i,i)
但是这会让你重复，因为它把（a，b）和（b，a）视为不同的东西，并且给出了所有对的sorting。 最后，我认为从头开始编码比试图过滤结果要容易，所以这里是正确的function。
def all_pairs(lst): if len(lst) < 2: yield lst return a = lst[0] for i in range(1,len(lst)): pair = (a,lst[i]) for rest in all_pairs(lst[1:i]+lst[i+1:]): yield [pair] + rest
它是recursion的，所以它会遇到一个很长的列表堆栈问题，但否则做你所需要的。
>>> for all_pairs（[0,1,2,3,4,5]）中的x：
打印x
[（0,1），（2,3），（4,5）]
[（0,1），（2,4），（3,5）]
[（0,1），（2,5），（3,4）]
[（0,2），（1,3），（4,5）]
[（0,2），（1,4），（3,5）]
[（0,2），（1,5），（3,4）]
[（0,3），（1,2），（4,5）]
[（0,3），（1,4），（2,5）]
[（0,3），（1,5），（2,4）]
[（0,4），（1,2），（3,5）]
[（0,4），（1,3），（2,5）]
[（0,4），（1,5），（2,3）]
[（0,5），（1,2），（3,4）]
[（0,5），（1,3），（2,4）]
[（0,5），（1,4），（2,3）]
从概念上类似于@ shang的回答，但并不假定组的大小为2：
import itertools def generate_groups(lst, n): if not lst: yield [] else: for group in (((lst[0],) + xs) for xs in itertools.combinations(lst[1:], n-1)): for groups in generate_groups([x for x in lst if x not in group], n): yield [group] + groups pprint(list(generate_groups([0, 1, 2, 3, 4, 5], 2)))
这产生：
[[(0, 1), (2, 3), (4, 5)], [(0, 1), (2, 4), (3, 5)], [(0, 1), (2, 5), (3, 4)], [(0, 2), (1, 3), (4, 5)], [(0, 2), (1, 4), (3, 5)], [(0, 2), (1, 5), (3, 4)], [(0, 3), (1, 2), (4, 5)], [(0, 3), (1, 4), (2, 5)], [(0, 3), (1, 5), (2, 4)], [(0, 4), (1, 2), (3, 5)], [(0, 4), (1, 3), (2, 5)], [(0, 4), (1, 5), (2, 3)], [(0, 5), (1, 2), (3, 4)], [(0, 5), (1, 3), (2, 4)], [(0, 5), (1, 4), (2, 3)]]
这个怎么样：
items = ["me", "you", "him"] [(items[i],items[j]) for i in range(len(items)) for j in range(i+1, len(items))] [('me', 'you'), ('me', 'him'), ('you', 'him')]
要么
items = [1, 2, 3, 5, 6] [(items[i],items[j]) for i in range(len(items)) for j in range(i+1, len(items))] [(1, 2), (1, 3), (1, 5), (1, 6), (2, 3), (2, 5), (2, 6), (3, 5), (3, 6), (5, 6)]
我的老板可能不会很高兴我花了一点时间在这个有趣的问题，但这是一个很好的解决scheme，不需要recursion，并使用itertools.product 。 它在docstring中解释:)。 结果看起来不错，但我没有太多testing。
import itertools def all_pairs(lst): """Generate all sets of unique pairs from a list `lst`. This is equivalent to all _partitions_ of `lst` (considered as an indexed set) which have 2 elements in each partition. Recall how we compute the total number of such partitions. Starting with a list [1, 2, 3, 4, 5, 6] one takes off the first element, and chooses its pair [from any of the remaining 5]. For example, we might choose our first pair to be (1, 4). Then, we take off the next element, 2, and choose which element it is paired to (say, 3). So, there are 5 * 3 * 1 = 15 such partitions. That sounds like a lot of nested loops (ie recursion), because 1 could pick 2, in which case our next element is 3. But, if one abstracts "what the next element is", and instead just thinks of what index it is in the remaining list, our choices are static and can be aided by the itertools.product() function. """ N = len(lst) choice_indices = itertools.product(*[ xrange(k) for k in reversed(xrange(1, N, 2)) ]) for choice in choice_indices: # calculate the list corresponding to the choices tmp = lst[:] result = [] for index in choice: result.append( (tmp.pop(0), tmp.pop(index)) ) yield result
干杯！
尝试下面的recursion生成器函数：
def pairs_gen(L): if len(L) == 2: yield [(L[0], L[1])] else: first = L.pop(0) for i, e in enumerate(L): second = L.pop(i) for list_of_pairs in pairs_gen(L): list_of_pairs.insert(0, (first, second)) yield list_of_pairs L.insert(i, second) L.insert(0, first)
用法示例：
>>> for pairs in pairs_gen([0, 1, 2, 3, 4, 5]): ... print pairs ... [(0, 1), (2, 3), (4, 5)] [(0, 1), (2, 4), (3, 5)] [(0, 1), (2, 5), (3, 4)] [(0, 2), (1, 3), (4, 5)] [(0, 2), (1, 4), (3, 5)] [(0, 2), (1, 5), (3, 4)] [(0, 3), (1, 2), (4, 5)] [(0, 3), (1, 4), (2, 5)] [(0, 3), (1, 5), (2, 4)] [(0, 4), (1, 2), (3, 5)] [(0, 4), (1, 3), (2, 5)] [(0, 4), (1, 5), (2, 3)] [(0, 5), (1, 2), (3, 4)] [(0, 5), (1, 3), (2, 4)] [(0, 5), (1, 4), (2, 3)]
def f(l): if l == []: yield [] return ll = l[1:] for j in range(len(ll)): for end in f(ll[:j] + ll[j+1:]): yield [(l[0], ll[j])] + end
用法：
for x in f([0,1,2,3,4,5]): print x >>> [(0, 1), (2, 3), (4, 5)] [(0, 1), (2, 4), (3, 5)] [(0, 1), (2, 5), (3, 4)] [(0, 2), (1, 3), (4, 5)] [(0, 2), (1, 4), (3, 5)] [(0, 2), (1, 5), (3, 4)] [(0, 3), (1, 2), (4, 5)] [(0, 3), (1, 4), (2, 5)] [(0, 3), (1, 5), (2, 4)] [(0, 4), (1, 2), (3, 5)] [(0, 4), (1, 3), (2, 5)] [(0, 4), (1, 5), (2, 3)] [(0, 5), (1, 2), (3, 4)] [(0, 5), (1, 3), (2, 4)] [(0, 5), (1, 4), (2, 3)]
我为所有兼容的解决scheme做了一个小testing套件。 我不得不改变这些函数来使它们在Python 3中工作。有趣的是，在某些情况下，PyPy中最快的函数是Python 2/3中最慢的函数。
import itertools import time from collections import OrderedDict def tokland_org(lst, n): if not lst: yield [] else: for group in (((lst[0],) + xs) for xs in itertools.combinations(lst[1:], n-1)): for groups in tokland_org([x for x in lst if x not in group], n): yield [group] + groups tokland = lambda x: tokland_org(x, 2) def gatoatigrado(lst): N = len(lst) choice_indices = itertools.product(*[ range(k) for k in reversed(range(1, N, 2)) ]) for choice in choice_indices: # calculate the list corresponding to the choices tmp = list(lst) result = [] for index in choice: result.append( (tmp.pop(0), tmp.pop(index)) ) yield result def shang(X): lst = list(X) if len(lst) < 2: yield lst return a = lst[0] for i in range(1,len(lst)): pair = (a,lst[i]) for rest in shang(lst[1:i]+lst[i+1:]): yield [pair] + rest def smichr(X): lst = list(X) if not lst: yield [tuple()] elif len(lst) == 1: yield [tuple(lst)] elif len(lst) == 2: yield [tuple(lst)] else: if len(lst) % 2: for i in (None, True): if i not in lst: lst = lst + [i] PAD = i break else: while chr(i) in lst: i += 1 PAD = chr(i) lst = lst + [PAD] else: PAD = False a = lst[0] for i in range(1, len(lst)): pair = (a, lst[i]) for rest in smichr(lst[1:i] + lst[i+1:]): rv = [pair] + rest if PAD is not False: for i, t in enumerate(rv): if PAD in t: rv[i] = (t[0],) break yield rv def adeel_zafar(X): L = list(X) if len(L) == 2: yield [(L[0], L[1])] else: first = L.pop(0) for i, e in enumerate(L): second = L.pop(i) for list_of_pairs in adeel_zafar(L): list_of_pairs.insert(0, (first, second)) yield list_of_pairs L.insert(i, second) L.insert(0, first) if __name__ =="__main__": import timeit import pprint candidates = dict(tokland=tokland, gatoatigrado=gatoatigrado, shang=shang, smichr=smichr, adeel_zafar=adeel_zafar) for i in range(1,7): results = [ frozenset([frozenset(x) for x in candidate(range(i*2))]) for candidate in candidates.values() ] assert len(frozenset(results)) == 1 print("Times for getting all permutations of sets of unordered pairs consisting of two draws from a 6-element deck until it is empty") times = dict([(k, timeit.timeit('list({0}(range(6)))'.format(k), setup="from __main__ import {0}".format(k), number=10000)) for k in candidates.keys()]) pprint.pprint([(k, "{0:.3g}".format(v)) for k,v in OrderedDict(sorted(times.items(), key=lambda t: t[1])).items()]) print("Times for getting the first 2000 permutations of sets of unordered pairs consisting of two draws from a 52-element deck until it is empty") times = dict([(k, timeit.timeit('list(islice({0}(range(52)), 800))'.format(k), setup="from itertools import islice; from __main__ import {0}".format(k), number=100)) for k in candidates.keys()]) pprint.pprint([(k, "{0:.3g}".format(v)) for k,v in OrderedDict(sorted(times.items(), key=lambda t: t[1])).items()]) """ print("The 10000th permutations of the previous series:") gens = dict([(k,v(range(52))) for k,v in candidates.items()]) tenthousands = dict([(k, list(itertools.islice(permutations, 10000))[-1]) for k,permutations in gens.items()]) for pair in tenthousands.items(): print(pair[0]) print(pair[1]) """
它们似乎都产生了完全相同的顺序，所以这些组合是没有必要的，但是这样做是未来的certificate。 我尝试了一下Python 3的转换，但并不总是清楚在哪里构build列表，但我尝试了一些替代scheme，并select了最快的。
以下是基准testing结果：
% echo "pypy"; pypy all_pairs.py; echo "python2"; python all_pairs.py; echo "python3"; python3 all_pairs.py pypy Times for getting all permutations of sets of unordered pairs consisting of two draws from a 6-element deck until it is empty [('gatoatigrado', '0.0626'), ('adeel_zafar', '0.125'), ('smichr', '0.149'), ('shang', '0.2'), ('tokland', '0.27')] Times for getting the first 2000 permutations of sets of unordered pairs consisting of two draws from a 52-element deck until it is empty [('gatoatigrado', '0.29'), ('adeel_zafar', '0.411'), ('smichr', '0.464'), ('shang', '0.493'), ('tokland', '0.553')] python2 Times for getting all permutations of sets of unordered pairs consisting of two draws from a 6-element deck until it is empty [('gatoatigrado', '0.344'), ('adeel_zafar', '0.374'), ('smichr', '0.396'), ('shang', '0.495'), ('tokland', '0.675')] Times for getting the first 2000 permutations of sets of unordered pairs consisting of two draws from a 52-element deck until it is empty [('adeel_zafar', '0.773'), ('shang', '0.823'), ('smichr', '0.841'), ('tokland', '0.948'), ('gatoatigrado', '1.38')] python3 Times for getting all permutations of sets of unordered pairs consisting of two draws from a 6-element deck until it is empty [('gatoatigrado', '0.385'), ('adeel_zafar', '0.419'), ('smichr', '0.433'), ('shang', '0.562'), ('tokland', '0.837')] Times for getting the first 2000 permutations of sets of unordered pairs consisting of two draws from a 52-element deck until it is empty [('smichr', '0.783'), ('shang', '0.81'), ('adeel_zafar', '0.835'), ('tokland', '0.969'), ('gatoatigrado', '1.3')] % pypy --version Python 2.7.12 (5.6.0+dfsg-0~ppa2~ubuntu16.04, Nov 11 2016, 16:31:26) [PyPy 5.6.0 with GCC 5.4.0 20160609] % python3 --version Python 3.5.2
所以我说，用gatoatigrado的解决scheme。
这个代码在列表的长度不是2的倍数的情况下工作。 它使用黑客来使其工作。 也许有更好的方法来做到这一点…它也确保了对总是在一个元组中，无论input是一个列表还是元组，它都可以工作。
def all_pairs(lst): """Return all combinations of pairs of items of ``lst`` where order within the pair and order of pairs does not matter. Examples ======== >>> for i in range(6): ... list(all_pairs(range(i))) ... [[()]] [[(0,)]] [[(0, 1)]] [[(0, 1), (2,)], [(0, 2), (1,)], [(0,), (1, 2)]] [[(0, 1), (2, 3)], [(0, 2), (1, 3)], [(0, 3), (1, 2)]] [[(0, 1), (2, 3), (4,)], [(0, 1), (2, 4), (3,)], [(0, 1), (2,), (3, 4)], [(0, 2) , (1, 3), (4,)], [(0, 2), (1, 4), (3,)], [(0, 2), (1,), (3, 4)], [(0, 3), (1, 2) , (4,)], [(0, 3), (1, 4), (2,)], [(0, 3), (1,), (2, 4)], [(0, 4), (1, 2), (3,)], [(0, 4), (1, 3), (2,)], [(0, 4), (1,), (2, 3)], [(0,), (1, 2), (3, 4)], [(0,), (1, 3), (2, 4)], [(0,), (1, 4), (2, 3)]] Note that when the list has an odd number of items, one of the pairs will be a singleton. References ========== http://stackoverflow.com/questions/5360220/ how-to-split-a-list-into-pairs-in-all-possible-ways """ if not lst: yield [tuple()] elif len(lst) == 1: yield [tuple(lst)] elif len(lst) == 2: yield [tuple(lst)] else: if len(lst) % 2: for i in (None, True): if i not in lst: lst = list(lst) + [i] PAD = i break else: while chr(i) in lst: i += 1 PAD = chr(i) lst = list(lst) + [PAD] else: PAD = False a = lst[0] for i in range(1, len(lst)): pair = (a, lst[i]) for rest in all_pairs(lst[1:i] + lst[i+1:]): rv = [pair] + rest if PAD is not False: for i, t in enumerate(rv): if PAD in t: rv[i] = (t[0],) break yield rv
L = [1, 1, 2, 3, 4] answer = [] for i in range(len(L)): for j in range(i+1, len(L)): if (L[i],L[j]) not in answer: answer.append((L[i],L[j])) print answer [(1, 1), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]
希望这可以帮助
（a，b）=（b，a）是一个非recursion函数，用于查找订单无关的所有可能的对，
def combinantorial(lst): count = 0 index = 1 pairs = [] for element1 in lst: for element2 in lst[index:]: pairs.append((element1, element2)) index += 1 return pairs
由于它是非recursion的，所以不会遇到长列表的内存问题。
使用示例：
my_list = [1, 2, 3, 4, 5] print(combinantorial(my_list)) >>> [(1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 5), (4, 5)]
希望这将有助于：
L = [0,1,2,3,4,5]
[（i，j）代表L代表L中的j]
输出：
（0,0），（0,1），（0,2），（0,3），（0,4），（0,5），（1,0），（1,1），（ （1,3），（1,4），（1,5），（2,0），（2,1），（2,2），（2,3），（2， （3,5），（3,0），（3,1），（3,2），（3,3），（3,4），（3,5），（4,0） （4,1），（4,2），（4,3），（4,4），（4,5），（5,0），（5,1），（5,2），（ 5，3），（5，4），（5，5）]
