Soru Bir listeyi olası tüm yollarla çiftlere nasıl bölersiniz?


Bir listem var (sadelik için 6 eleman)

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

ve ben onu çift olarak parçalamak istiyorum HERŞEY olası yollar. Bazı yapılandırmalar gösteriyorum:

[(0, 1), (2, 3), (4, 5)]
[(0, 1), (2, 4), (3, 5)]
[(0, 1), (2, 5), (3, 4)]

ve bunun gibi. İşte (a, b) = (b, a) ve çiftlerin sırası önemli değildir.

[(0, 1), (2, 3), (4, 5)] = [(0, 1), (4, 5), (2, 3)]

Bu tür yapılandırmaların toplam sayısı 1*3*5*...*(N-1) nerede N listemin uzunluğu.

Python'da nasıl bir rasgele yazılabilecek tüm konfigürasyonları veren bir jeneratörü nasıl yazabilirim? N?


44
2018-03-19 05:07


Menşei


Bu standart modüle bakmak isteyebilirsiniz. itertools eğer sen yapmadıysan. Buradaki işlevler, bu sorunla ilgili olarak yardımcı olabilir (muhtemelen permutations, combinations veya product fonksiyonlar). - dappawit
Sipariş önemli değilse, muhtemelen setleri veya frozensets kullanmalısınız. - asmeurer
Kombinatorics dilinde, tüm oluşturmak istediğiniz mükemmel eşlemeler Belirli bir sette (tam bir grafikte). - Valentas


Cevaplar:


Şuna baksana 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)]

63
2018-03-19 05:32



Soruyu soran bu değil ... ama aradığım şey buydu :) - gatoatigrado
Bu neden en tepedeki cevap? Bu soruya cevap vermiyor gibi görünüyor. - Halbort
Bu siteye gelen çoğu insanın sorusunu yanıtlıyor. - Radio Controlled
@Halbort: xyproblem.info - Matt Joiner
@Halbort Başlığa cevap veriyor, bu yüzden birçok kişiye yardımcı oluyor. Artı, bu kesinlikle OP'nin sahip olduğu asıl sorun. İşte kombinasyonları yinelenebilirşimdi, ancak istediğiniz şeyi parçalayın. - OJFord


Standart kütüphanede ihtiyaç duyduğunuz her şeyi yapan bir işlev olduğunu düşünmüyorum. Sadece kullanarak itertools.combinations olası tüm bireysel çiftlerin listesini alabilir, ancak tüm geçerli çift kombinasyonlarının problemini çözmez.

Bunu kolayca çözebilirsiniz:

import itertools
def all_pairs(lst):
    for p in itertools.permutations(lst):
        i = iter(p)
        yield zip(i,i)

Ama bu size (a, b) ve (b, a) farklı olarak davranır ve aynı zamanda tüm çiftlerin düzenlerini verirken size çiftleri katar. Sonunda, sonuçları filtrelemeye çalışmaktan sıfırdan kodlamanın daha kolay olduğunu düşündüm, işte doğru fonksiyon.

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

Yinelemeli, bu yüzden uzun bir listeyle yığın sorunlarına dönüşecek, ancak ihtiyacınız olan şeyi yapacaktır.

All_pairs içinde x için >>> ([0,1,2,3,4,5]):
    x yazdır

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

26
2018-03-19 05:56



Python varsayılan olarak 1000 çağrı derinliğine sahiptir. Basamak çiftleri üzerinde tekrarlıyorsunuz, bu yüzden listeniz neredeyse 2000 ürün uzunluğuna kadar bir sorun olmamalı. Sadece 50 öğede 5 * 10 ^ 31 kombinasyonundan daha fazlasına sahip olursunuz; Yığın derinliği bir sorun haline gelmeden çok önce milyar yıllık hesaplamalara gireceksiniz. - Hugh Bothwell
Bunu yazmanın klasik yolu budur. - hughdbrown
Bu cevapta bir sorun var gibi görünüyor (Python 2.7.11 çalıştıran). Tam olarak aynı kodu çalıştırırken çıktının ilk satırı: [(0, 1), (2, 3), 4]. - Alceu Costa
Maalesef, cevabın en iyi niyetle yazıldığından emin olabilirim, ancak tek uzunluktaki tüm girdi listeleri için yanlıştır - Moritz Walter
@MoritzWalter Sabit! - shang


Buna ne dersin:

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

veya

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

10
2017-07-27 14:16



iyi, çiftlerin kümelerini gruplamıyor - Janus Troelsen


Kavramsal olarak @ shang'ın cevabına benzer, ancak grupların 2 boyutunda olduğunu varsaymaz:

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

Bu verim:

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

8
2018-03-19 13:56





Patronum muhtemelen bu eğlenceli problemde biraz zaman geçirdiğim için mutlu olmayacak, ama burada tekrarlamaya ihtiyaç duymayan güzel bir çözüm ve itertools.product. Docstring'de açıklandı :). Sonuçlar iyi görünüyor, ama çok fazla test etmedim.

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

şerefe!


4
2017-10-22 21:54



daha kesin bir isim olmalı all_pairings ve xrange ile değiştirilmelidir range Python 3'te. - Valentas


Aşağıdaki yinelemeli jeneratör işlevini deneyin:

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)

Örnek kullanım:

>>> 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
2018-03-19 05:46





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

Kullanımı:

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

2
2018-03-19 06:34



Oops, shang'ın cevabını görmedim, aynı şeyi yapan ... bunu silmem gerekir mi? - Jules Olléon
Silmeye gerek yok, ama shang'in gerçek değişken isimlerini kullanması daha iyi. - gatoatigrado


Tüm uyumlu çözümler için küçük bir test paketi yaptım. Python 3'te çalışabilmeleri için işlevleri biraz değiştirmem gerekiyordu. İlginçtir ki, PyPy'deki en hızlı işlev bazı durumlarda Python 2/3'teki en yavaş işlevdir.

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

Hepsi aynı siparişi üretiyor gibi görünüyor, bu yüzden setler gerekli değil, ama bu şekilde gelecekteki kanıt. Python 3 dönüşümüyle biraz deneme yaptım, listeyi nerede oluşturduğum her zaman net değil, ama bazı alternatifleri denedim ve en hızlı seçtim.

İşte karşılaştırma sonuçları:

% 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

Demek istediğim, gatoatigrado'nun çözümüne git.


2
2018-05-14 20:13





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

Bu yardımcı olur umarım


1
2018-03-19 05:56





Bu kod, listenin uzunluğu 2'nin katları olmadığında çalışır; çalışmasını sağlamak için bir hack kullanır. Belki de bunu yapmanın daha iyi yolları vardır ... Ayrıca, çiftlerin her zaman bir tuple olmasını ve girişin bir liste mi yoksa tuple mı olduğunu çalışmasını sağlar.

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

1
2018-02-06 21:45





Siparişin önemli olmadığı tüm olası çiftleri bulmak için tekrarlayan bir işlev, yani (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

Yinelemeli olmadığı için uzun listelerle hafıza sorunları yaşamayacaksınız.

Kullanım örneği:

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

1
2018-06-02 14:15