가능한 모든 방법으로 목록을 쌍으로 나누는 방법

가능한 모든 방법으로 목록을 쌍으로 나누는 방법

---

목록이 있습니다 (단순함을 위해 6 개 요소)

L = [0, 1, 2, 3, 4, 5]

가능한 모든 방법 으로 쌍으로 묶고 싶습니다 . 몇 가지 구성을 보여줍니다.

[(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)]

이러한 구성의 총 수는 1*3*5*...*(N-1)어디에 N내 목록의 길이입니다.

임의의 가능한 모든 구성을 제공하는 Python 생성기를 어떻게 작성할 수 N있습니까?

---

를보세요 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)]

---

표준 라이브러리에는 필요한 기능을 정확히 수행하는 기능이 없다고 생각합니다. 사용하는 것만으로 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)를 다른 것으로 취급하고 쌍의 모든 순서를 제공하므로 중복을 얻습니다. 결국 결과를 필터링하는 것보다 처음부터 코딩하는 것이 더 쉽다고 생각 했으므로 여기에 올바른 함수가 있습니다.

def all_pairs(lst):
    if len(lst) < 2:
        yield []
        return
    if len(lst) % 2 == 1:
        # Handle odd length list
        for i in range(len(lst)):
            for result in all_pairs(lst[:i] + lst[i+1:]):
                yield result
    else:
        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

재귀 적이므로 긴 목록으로 스택 문제가 발생하지만 그렇지 않으면 필요한 작업을 수행합니다.

>>> x in all_pairs ([0,1,2,3,4,5]) :
    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)]

---

이것은 어떤가요:

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)]

---

@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)]]

---

내 상사는 아마도이 재미있는 문제에 약간의 시간을 보냈을 때 행복하지 않을 것입니다.하지만 여기에 재귀가 필요하지 않고 itertools.product. 독 스트링에 설명되어 있습니다. :). 결과는 괜찮아 보이지만 너무 많이 테스트하지는 않았습니다.

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 (i.e. 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

건배!

---

다음 재귀 생성기 함수를 시도하십시오.

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)]

---

순서가 중요하지 않은 모든 가능한 쌍을 찾는 비 재귀 함수 (예 : (a, b) = (b, a))

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

비 재귀 적이므로 긴 목록에서 메모리 문제가 발생하지 않습니다.

사용 예 :

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)]

---

모든 호환 솔루션을위한 작은 테스트 스위트를 만들었습니다. 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])
    """

그것들은 모두 똑같은 순서를 생성하는 것처럼 보이므로 세트가 필요하지는 않지만이 방법은 미래의 증거입니다. 저는 Python 3 변환으로 약간의 실험을했지만 목록을 구성 할 위치가 항상 명확하지는 않지만 몇 가지 대안을 시도하고 가장 빠른 것을 선택했습니다.

벤치 마크 결과는 다음과 같습니다.

% 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의 해결책으로 가라.

---

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)]

도움이 되었기를 바랍니다

---

이 코드는 목록의 길이가 2의 배수가 아닐 때 작동합니다. 작동하도록 해킹을 사용합니다. 이 작업을 수행하는 더 좋은 방법이있을 수 있습니다. 또한 쌍이 항상 튜플에 있고 입력이 목록이든 튜플이든 상관없이 작동하는지 확인합니다.

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

---

Hope this will help:

L = [0, 1, 2, 3, 4, 5]

[(i,j) for i in L for j in L]

output:

[(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (1, 0), (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 0), (2, 1), (2, 2), (2, 3), (2, 4), (2, 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)]

---

Not the most efficient or fastest, but probably the easiest. The last line is a simple way to dedupe a list in python. In this case, pairs like (0,1) and (1,0) are in the output. Not sure if you'd consider those duplicates or not.

l = [0, 1, 2, 3, 4, 5]
pairs = []
for x in l:
    for y in l:
        pairs.append((x,y))
pairs = list(set(pairs))
print(pairs)

Output:

[(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (1, 0), (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 0), (2, 1), (2, 2), (2, 3), (2, 4), (2, 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)]

ReferenceURL : https://stackoverflow.com/questions/5360220/how-to-split-a-list-into-pairs-in-all-possible-ways