सवाल सूची को सभी संभावित तरीकों से जोड़े में कैसे विभाजित करें


मेरे पास एक सूची है (सादगी के लिए 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) और जोड़ों का क्रम महत्वपूर्ण नहीं है i.e.

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

ऐसी विन्यास की कुल संख्या है 1*3*5*...*(N-1) कहा पे N मेरी सूची की लंबाई है।

मैं पायथन में जनरेटर कैसे लिख सकता हूं जो मुझे मनमाने ढंग से सभी संभावित कॉन्फ़िगरेशन देता है N?


44
2018-03-19 05:07


मूल


आप उस मानक मॉड्यूल को देखना चाह सकते हैं itertools अगर आप पहले से नहीं हैं। इस समस्या के साथ मदद करने में सक्षम होना चाहिए (संभवतः permutations, combinations या product फ़ंक्शन)। - dappawit
यदि आदेश महत्वपूर्ण नहीं है, तो आपको शायद सेट या फ्रोजनसेट्स का उपयोग करना चाहिए। - asmeurer
Combinatorics की भाषा में, आप सभी उत्पन्न करना चाहते हैं सही मिलान किसी दिए गए सेट पर (एक पूर्ण ग्राफ में)। - Valentas


जवाब:


पर एक नज़र डालें 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



सवाल यह नहीं है कि सवाल पूछता है ... लेकिन ऐसा होता है जो मैं ढूंढ रहा था :) - gatoatigrado
यह सबसे ऊंचा जवाब क्यों है? ऐसा लगता है कि सवाल का जवाब नहीं है। - Halbort
यह इस साइट पर आने वाले अधिकांश लोगों के प्रश्न का उत्तर देता है। - Radio Controlled
@Halbort: xyproblem.info - Matt Joiner
@ हैल्बॉर्ट हालांकि यह शीर्षक का जवाब देता है, इसलिए यह बहुत से लोगों की मदद करता है। इसके अलावा, यह निश्चित रूप से मुख्य समस्या ओपी था वैसे भी। यहां संयोजन हैं एक पुनरावर्तनीय, अब आप इसे चाहते हैं तो इसे खंडित करें। - OJFord


मुझे नहीं लगता कि मानक पुस्तकालय में कोई फ़ंक्शन है जो आपको वही करता है जो आपको चाहिए। बस उपयोग कर रहा हूँ itertools.combinations आपको सभी संभावित व्यक्तिगत जोड़े की एक सूची मिल सकती है, लेकिन वास्तव में सभी मान्य जोड़ी संयोजनों की समस्या को हल नहीं करती है।

आप इसे आसानी से हल कर सकते हैं:

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

लेकिन यह आपको डुप्लिकेट करेगा क्योंकि यह (ए, बी) और (बी, ए) अलग-अलग व्यवहार करता है, और जोड़े के सभी ऑर्डर देता है। अंत में, मुझे लगा कि परिणामों को फ़िल्टर करने की कोशिश करने से स्क्रैच से इसे कोड करना आसान है, इसलिए यहां सही कार्य है।

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_pairs ([0,1,2,3,4,5]):
    प्रिंट एक्स

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



डिफ़ॉल्ट रूप से पायथन के पास रिटर्न स्टैक 1000 कॉल गहरी है। आप अंकों के जोड़े पर रिकर्स कर रहे हैं, इसलिए यह तब तक कोई मुद्दा नहीं होना चाहिए जब तक कि आपकी सूची लगभग 2000 आइटम लंबी न हो। केवल 50 आइटमों पर आपको 5 * 10 ^ 31 संयोजन मिलते हैं; स्टैक गहराई एक मुद्दा बनने से पहले आप अरब साल की गणना में भाग लेंगे। - Hugh Bothwell
यह लिखने का क्लासिक तरीका है। - hughdbrown
ऐसा लगता है कि इस उत्तर में समस्या है (पाइथन 2.7.11 चल रहा है)। बिल्कुल उसी कोड को चलाने पर आउटपुट की पहली पंक्ति रिटर्न: [(0, 1), (2, 3), 4]। - Alceu Costa
क्षमा करें, मुझे यकीन है कि उत्तर सर्वोत्तम इरादे से लिखा गया है, लेकिन यह अजीब लंबाई की सभी इनपुट सूचियों के लिए गलत है - Moritz Walter
@MoritzWalter फिक्स्ड! - shang


इस बारे में कैसा है:

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

10
2017-07-27 14:16



अच्छा, यह जोड़े के सेट समूह नहीं है - Janus Troelsen


संकल्पनात्मक रूप से @ शांग के उत्तर के समान, लेकिन यह नहीं मानता कि समूह आकार 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)]]

8
2018-03-19 13:56





मेरा मालिक शायद खुश नहीं होने वाला है, मैंने इस मजेदार समस्या पर थोडा समय बिताया, लेकिन यहां एक अच्छा समाधान है जिसे रिकर्सन और उपयोग की आवश्यकता नहीं है itertools.product। यह docstring में समझाया गया है :)। परिणाम ठीक लगते हैं, लेकिन मैंने इसका परीक्षण नहीं किया है।

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

चियर्स!


4
2017-10-22 21:54



एक और सटीक नाम होना चाहिए all_pairings तथा xrange द्वारा प्रतिस्थापित किया जाना चाहिए range पायथन 3 में। - Valentas


निम्नलिखित रिकर्सिव जेनरेटर फ़ंक्शन का प्रयास करें:

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

उपयोग:

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



ओह, शांग का जवाब नहीं देखा, जो वही काम करता है ... क्या मुझे इसे हटा देना चाहिए? - Jules Olléon
हटाने की कोई ज़रूरत नहीं है, लेकिन असली वैरिएबल नामों का शांग का उपयोग बेहतर है। - gatoatigrado


मैंने सभी अनुपालन समाधानों के लिए एक छोटा परीक्षण सूट बनाया। मुझे उन्हें पायथन 3 में काम करने के लिए थोड़ा सा बदलाव करना पड़ा। दिलचस्प बात यह है कि कुछ मामलों में पायपी में सबसे तेज़ काम पाइथन 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])
    """

वे सभी एक ही आदेश उत्पन्न करने लगते हैं, इसलिए सेट जरूरी नहीं हैं, लेकिन इस तरह यह भविष्य का सबूत है। मैंने पायथन 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 के समाधान के साथ जाओ।


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

उम्मीद है की यह मदद करेगा


1
2018-03-19 05:56





यह कोड तब काम करता है जब सूची की लंबाई 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

1
2018-02-06 21:45





सभी संभावित जोड़े को खोजने के लिए एक गैर-पुनरावर्ती कार्य जहां ऑर्डर कोई फर्क नहीं पड़ता, यानी, (ए, बी) = (बी, ए)

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

1
2018-06-02 14:15