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

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

목록이 있습니다(간단하게 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제 목록의 길이입니다.

임의의 모든 가능한 구성을 제공하는 생성기를 파이썬에서 작성하려면 어떻게 해야 합니까?N?

를 보십시오.

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

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

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

이거 어때:

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.productdocstring :)에 설명되어 있습니다.결과는 괜찮은 것 같은데, 별로 검사를 안 해봤어요.

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

건배!

순서가 중요하지 않은 가능한 모든 쌍을 찾기 위한 비순수 함수(예: (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)]

다음 재귀 생성기 함수를 사용해 보십시오.

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

저는 모든 호환 솔루션을 위한 작은 테스트 제품군을 만들었습니다.파이썬 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

그래서 저는 가타티그라도의 해결책을 따르라고 말합니다.

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

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

이것이 도움이 되길 바랍니다.

이것이 도움이 되기를 바랍니다.

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

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

출력:

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

이 코드는 목록의 길이가 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

저는 @shang과 @tokland가 제공하는 훌륭한 솔루션을 기반으로 하는 저의 기여를 추가하고 있습니다.제 문제는 12명으로 구성된 그룹에서 당신의 쌍 크기가 그룹 크기와 완벽하게 구분되지 않을 때 가능한 모든 쌍을 보고 싶었습니다.예를 들어, 입력 목록 크기가 12인 경우 5개의 요소로 구성된 가능한 모든 쌍을 보고 싶습니다.

이 코드의 캡처와 작은 수정은 이 문제를 해결해야 합니다.

import itertools

def generate_groups(lst, n):
    if not lst:
        yield []
    else:
        
        if len(lst) % n == 0:
        
        
            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
            
        else:
            
            for group in (((lst[0],) + xs) for xs in itertools.combinations(lst[1:], n-1)):
                group2 = [x for x in lst if x not in group]
                for grp in (((group2[0],) + xs2) for xs2 in itertools.combinations(group2[1:], n-1)):
                    yield [group] + [grp]

따라서 이 경우 다음과 같은 코드 스니핑을 실행하면 아래와 같은 결과를 얻을 수 있습니다.코드의 마지막 캡처는 중복되는 요소가 없는지 확인하는 것입니다.

i = 0
for x in generate_groups([1,2,3,4,5,6,7,8,9,10,11,12], 5):
    print(x)
    for elem in x[0]:
        if elem in x[1]:
            print('break')
            break

>>>
[(1, 2, 3, 4, 5), (6, 7, 8, 9, 10)]
[(1, 2, 3, 4, 5), (6, 7, 8, 9, 11)]
[(1, 2, 3, 4, 5), (6, 7, 8, 9, 12)]
[(1, 2, 3, 4, 5), (6, 7, 8, 10, 11)]
[(1, 2, 3, 4, 5), (6, 7, 8, 10, 12)]
[(1, 2, 3, 4, 5), (6, 7, 8, 11, 12)]
[(1, 2, 3, 4, 5), (6, 7, 9, 10, 11)]
...

가장 효율적이거나 가장 빠르지는 않지만 아마도 가장 쉬울 것입니다.마지막 줄은 파이썬의 목록을 추론하는 간단한 방법입니다.이 경우 (0,1) 및 (1,0)과 같은 쌍이 출력에 표시됩니다.당신이 그 복제품들을 고려할지 아닐지 확신할 수 없습니다.

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)

출력:

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

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