كيفية الحصول على جميع التوليفات الممكنة من قائمة العناصر ؟

https://stackoverflow.com/questions/464864

19-08-2019
|

سؤال

لدي قائمة مع 15 الأرقام في أحتاج إلى كتابة بعض التعليمات البرمجية التي تنتج كل 32,768 مجموعات من تلك الأرقام.

لقد وجدت بعض التعليمات البرمجية (قبل غوغلينغ) التي يبدو أنها ما أبحث عنه لكن وجدت رمز مبهمة إلى حد ما وأنا الحذر من استخدامه.زائد لدي شعور يجب أن يكون هناك حل أكثر أناقة.

الشيء الوحيد الذي خطر لي أن يكون مجرد حلقة خلال العشرية الصحيحه 1-32768 وتحويل تلك الثنائية ، واستخدام تمثيل ثنائي كعامل تصفية لاختيار الأعداد المناسبة.

لا أحد يعرف من طريقة أفضل ؟ باستخدام map(), ربما ؟

المحلول

وإلقاء نظرة على itertools.combinations :

<اقتباس فقرة>

itertools.combinations(iterable, r)

والمتتالية وطول العودة ص عناصر من وiterable الإدخال.

وتنبعث

ودمج في ترتيب lexicographic. لذلك، إذا كان يتم فرز المدخلات iterable، و سيتم إنتاج الصفوف الجمع في ترتيب فرزها.

ومنذ 2.6، يتم تضمين البطاريات!

نصائح أخرى

هذا الجواب غاب أحد جوانب:OP طلب جميع تركيبات...ليس فقط مجموعات من طول "r".

لذا أما أن حلقة من خلال كل الأطوال "L":

import itertools

stuff = [1, 2, 3]
for L in range(0, len(stuff)+1):
    for subset in itertools.combinations(stuff, L):
        print(subset)

أو-إذا كنت ترغب في الحصول على أنيق (أو ثني الدماغ من كل من يقرأ التعليمات البرمجية الخاصة بك بعد أن كنت) -- يمكنك إنشاء سلسلة من "تركيبات()" مولدات, و من خلال تكرار ذلك:

from itertools import chain, combinations
def all_subsets(ss):
    return chain(*map(lambda x: combinations(ss, x), range(0, len(ss)+1)))

for subset in all_subsets(stuff):
    print(subset)

هنا هو واحد كسول-بطانة أيضا باستخدام itertools:

from itertools import compress, product

def combinations(items):
    return ( set(compress(items,mask)) for mask in product(*[[0,1]]*len(items)) )
    # alternative:                      ...in product([0,1], repeat=len(items)) )

الفكرة الرئيسية وراء هذا الجواب:هناك 2^ن تركيبات-نفس عدد الثنائية سلاسل من طول N.لكل ثنائي السلسلة ، يمكنك اختيار جميع العناصر المقابلة "1".

items=abc * mask=###
 |
 V
000 -> 
001 ->   c
010 ->  b
011 ->  bc
100 -> a
101 -> a c
110 -> ab
111 -> abc

الأشياء في الاعتبار:

وهذا يتطلب أن يمكنك الاتصال len(...) على items (الحل:إذا items هو شيء مثل iterable مثل مولد تحويلها إلى القائمة الأولى مع items=list(_itemsArg))
وهذا يتطلب أن ترتيب التكرار على items ليست عشوائية (الحل:لا يكون مجنونا)
وهذا يتطلب أن العناصر هي فريدة من نوعها ، أو آخر {2,2,1} و {2,1,1} كل انهيار {2,1} (الحل:استخدام collections.Counter وقطرة في بديل set;انها في الأساس مولتيست...على الرغم من أنك قد تحتاج إلى استخدامها في وقت لاحق tuple(sorted(Counter(...).elements())) إذا كنت بحاجة إلى أن يكون hashable)

Demo

>>> list(combinations(range(4)))
[set(), {3}, {2}, {2, 3}, {1}, {1, 3}, {1, 2}, {1, 2, 3}, {0}, {0, 3}, {0, 2}, {0, 2, 3}, {0, 1}, {0, 1, 3}, {0, 1, 2}, {0, 1, 2, 3}]

>>> list(combinations('abcd'))
[set(), {'d'}, {'c'}, {'c', 'd'}, {'b'}, {'b', 'd'}, {'c', 'b'}, {'c', 'b', 'd'}, {'a'}, {'a', 'd'}, {'a', 'c'}, {'a', 'c', 'd'}, {'a', 'b'}, {'a', 'b', 'd'}, {'a', 'c', 'b'}, {'a', 'c', 'b', 'd'}]

في التعليقات تحت للغاية upvoted الجواب بواسطة @دان ساعة, إشارة powerset() وصفة في itertools الوثائقبما في ذلك واحد من قبل دان نفسه. ومع ذلك, حتى الآن لا أحد قد نشرت على أنها إجابة.بما انها على الارجح واحدة من أفضل إن لم يكن أفضل نهج المشكلة—ونظرا القليل من التشجيع من المعلق آخر ، هو مبين أدناه.وظيفة تنتج كل تركيبة فريدة من نوعها من قائمة عناصر كل طول ممكن (بما في ذلك تلك التي تحتوي على صفر و جميع العناصر).

ملاحظة:إذا بمهارة مختلفة ، الهدف هو الحصول فقط مجموعات من عناصر فريدة من نوعها, تغيير الخط s = list(iterable) إلى s = list(set(iterable)) للقضاء على أي عناصر مكررة.بغض النظر عن حقيقة أن iterable هو في نهاية المطاف تحولت إلى list يعني أنه سوف يعمل مع مولدات (على عكس العديد من إجابات أخرى).

from itertools import chain, combinations

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)  # allows duplicate elements
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

stuff = [1, 2, 3]
for i, combo in enumerate(powerset(stuff), 1):
    print('combo #{}: {}'.format(i, combo))

الإخراج:

combo #1: ()
combo #2: (1,)
combo #3: (2,)
combo #4: (3,)
combo #5: (1, 2)
combo #6: (1, 3)
combo #7: (2, 3)
combo #8: (1, 2, 3)

وهنا هو واحد باستخدام العودية:

>>> import copy
>>> def combinations(target,data):
...     for i in range(len(data)):
...         new_target = copy.copy(target)
...         new_data = copy.copy(data)
...         new_target.append(data[i])
...         new_data = data[i+1:]
...         print new_target
...         combinations(new_target,
...                      new_data)
...                      
... 
>>> target = []
>>> data = ['a','b','c','d']
>>> 
>>> combinations(target,data)
['a']
['a', 'b']
['a', 'b', 'c']
['a', 'b', 'c', 'd']
['a', 'b', 'd']
['a', 'c']
['a', 'c', 'd']
['a', 'd']
['b']
['b', 'c']
['b', 'c', 'd']
['b', 'd']
['c']
['c', 'd']
['d']

وهذا أونيلينير يعطيك كل المجموعات (بين 0 وn البنود إذا القائمة الأصلية / مجموعة يحتوي على عناصر متميزة n) ويستخدم أسلوب الأصلي <لأ href = "https://docs.python.org/2 /library/itertools.html#itertools.combinations "يختلط =" noreferrer "> itertools.combinations :

بايثون 2

from itertools import combinations

input = ['a', 'b', 'c', 'd']

output = sum([map(list, combinations(input, i)) for i in range(len(input) + 1)], [])

بيثون 3

from itertools import combinations

input = ['a', 'b', 'c', 'd']

output = sum([list(map(list, combinations(input, i))) for i in range(len(input) + 1)], [])

والناتج سيكون:

[[],
 ['a'],
 ['b'],
 ['c'],
 ['d'],
 ['a', 'b'],
 ['a', 'c'],
 ['a', 'd'],
 ['b', 'c'],
 ['b', 'd'],
 ['c', 'd'],
 ['a', 'b', 'c'],
 ['a', 'b', 'd'],
 ['a', 'c', 'd'],
 ['b', 'c', 'd'],
 ['a', 'b', 'c', 'd']]

وحاول على الانترنت:

http://ideone.com/COghfX

أنا أتفق مع دان ح أن بن وبالفعل طلبت كل تركيبات. itertools.combinations() لا يعطي جميع المجموعات.

مسألة أخرى ، إذا كان الإدخال iterable كبير, ربما من الأفضل أن عودة المولد بدلا من كل شيء في القائمة:

iterable = range(10)
for s in xrange(len(iterable)+1):
  for comb in itertools.combinations(iterable, s):
    yield comb

يمكنك توليد جميع تركيبات قائمة في بيثون باستخدام هذا كود بسيط

import itertools

a = [1,2,3,4]
for i in xrange(0,len(a)+1):
   print list(itertools.combinations(a,i))

النتيجة ستكون :

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

وفكرت وأود أن أضيف هذه الوظيفة للباحثين عن الإجابة دون استيراد itertools أو أي مكتبات إضافية أخرى.

def powerSet(items):
    """
    Power set generator: get all possible combinations of a list’s elements

    Input:
        items is a list
    Output:
        returns 2**n combination lists one at a time using a generator 

    Reference: edx.org 6.00.2x Lecture 2 - Decision Trees and dynamic programming
    """

    N = len(items)
    # enumerate the 2**N possible combinations
    for i in range(2**N):
        combo = []
        for j in range(N):
            # test bit jth of integer i
            if (i >> j) % 2 == 1:
                combo.append(items[j])
        yield combo

وبسيط العائد مولد الاستخدام:

for i in powerSet([1,2,3,4]):
    print (i, ", ",  end="")

والناتج من الاستخدام المثال أعلاه:

<اقتباس فقرة>

[]، [1]، [2]، [1، 2]، [3]، [1 و 3]، [2، 3]، [1، 2، 3]، [4]، [1، 4]، [2، 4]، [1، 2، 4]، [3، 4]، [1، 3، 4]، [2، 3، 4]، [1، 2، 3، 4]،

وهنا بعد حل آخر (سفينة واحدة)، التي تنطوي على استخدام وظيفة itertools.combinations، ولكن هنا نستخدم قائمة الفهم المزدوج (في مقابل لحلقة أو مبلغ):

def combs(x):
    return [c for i in range(len(x)+1) for c in combinations(x,i)]

وعرض توضيحي:

>>> combs([1,2,3,4])
[(), 
 (1,), (2,), (3,), (4,), 
 (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4), 
 (1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4), 
 (1, 2, 3, 4)]

وهذا هو النهج الذي يمكن نقلها بسهولة إلى جميع لغات البرمجة دعم العودية على (لا itertools، لا الغلة، أي قائمة على الفهم) : ل

def combs(a):
    if len(a) == 0:
        return [[]]
    cs = []
    for c in combs(a[1:]):
        cs += [c, c+[a[0]]]
    return cs

>>> combs([1,2,3,4,5])
[[], [1], [2], [2, 1], [3], [3, 1], [3, 2], ..., [5, 4, 3, 2, 1]]

يمكن أن يتم ذلك باستخدام itertools

عن التباديل

يأخذ هذا الأسلوب قائمة كمدخل والعودة كائن قائمة الصفوف التي تحتوي على التقليب من طول L في شكل قائمة.

# A Python program to print all  
# permutations of given length 
from itertools import permutations 

# Get all permutations of length 2 
# and length 2 
perm = permutations([1, 2, 3], 2) 

# Print the obtained permutations 
for i in list(perm): 
    print (i)

الجمع بين

هذه الطريقة تستغرق وقتا قائمة المدخلات r كما المدخلات إرجاع كائن قائمة الصفوف التي تحتوي على كل تركيبة ممكنة من طول r في شكل قائمة.

# A Python program to print all  
# combinations of given length 
from itertools import combinations 

# Get all combinations of [1, 2, 3] 
# and length 2 
comb = combinations([1, 2, 3], 2) 

# Print the obtained combinations 
for i in list(comb): 
    print (i)

انظر هذا

وفيما يلي هو "الجواب متكررة القياسية"، على غرار الآخرين الجواب https://stackoverflow.com/a/23743696/ 711085 . (ليس لدينا واقعيا للقلق من نفاد مساحة مكدس منذ ليس هناك طريقة نتمكن من معالجة كل N! التباديل).

ووتزور كل عنصر بدوره، وإما يأخذ أو يترك (يمكننا أن نرى بشكل مباشر على 2 ^ N أصل من هذه الخوارزمية).

def combs(xs, i=0):
    if i==len(xs):
        yield ()
        return
    for c in combs(xs,i+1):
        yield c
        yield c+(xs[i],)

وعرض توضيحي:

>>> list( combs(range(5)) )
[(), (0,), (1,), (1, 0), (2,), (2, 0), (2, 1), (2, 1, 0), (3,), (3, 0), (3, 1), (3, 1, 0), (3, 2), (3, 2, 0), (3, 2, 1), (3, 2, 1, 0), (4,), (4, 0), (4, 1), (4, 1, 0), (4, 2), (4, 2, 0), (4, 2, 1), (4, 2, 1, 0), (4, 3), (4, 3, 0), (4, 3, 1), (4, 3, 1, 0), (4, 3, 2), (4, 3, 2, 0), (4, 3, 2, 1), (4, 3, 2, 1, 0)]

>>> list(sorted( combs(range(5)), key=len))
[(), 
 (0,), (1,), (2,), (3,), (4,), 
 (1, 0), (2, 0), (2, 1), (3, 0), (3, 1), (3, 2), (4, 0), (4, 1), (4, 2), (4, 3), 
 (2, 1, 0), (3, 1, 0), (3, 2, 0), (3, 2, 1), (4, 1, 0), (4, 2, 0), (4, 2, 1), (4, 3, 0), (4, 3, 1), (4, 3, 2), 
 (3, 2, 1, 0), (4, 2, 1, 0), (4, 3, 1, 0), (4, 3, 2, 0), (4, 3, 2, 1), 
 (4, 3, 2, 1, 0)]

>>> len(set(combs(range(5))))
32

وهذا الرمز يستخدم خوارزمية بسيطة مع القوائم المتداخلة ...

# FUNCTION getCombos: To generate all combos of an input list, consider the following sets of nested lists...
#
#           [ [ [] ] ]
#           [ [ [] ], [ [A] ] ]
#           [ [ [] ], [ [A],[B] ],         [ [A,B] ] ]
#           [ [ [] ], [ [A],[B],[C] ],     [ [A,B],[A,C],[B,C] ],                   [ [A,B,C] ] ]
#           [ [ [] ], [ [A],[B],[C],[D] ], [ [A,B],[A,C],[B,C],[A,D],[B,D],[C,D] ], [ [A,B,C],[A,B,D],[A,C,D],[B,C,D] ], [ [A,B,C,D] ] ]
#
#  There is a set of lists for each number of items that will occur in a combo (including an empty set).
#  For each additional item, begin at the back of the list by adding an empty list, then taking the set of
#  lists in the previous column (e.g., in the last list, for sets of 3 items you take the existing set of
#  3-item lists and append to it additional lists created by appending the item (4) to the lists in the
#  next smallest item count set. In this case, for the three sets of 2-items in the previous list. Repeat
#  for each set of lists back to the initial list containing just the empty list.
#

def getCombos(listIn = ['A','B','C','D','E','F'] ):
    listCombos = [ [ [] ] ]     # list of lists of combos, seeded with a list containing only the empty list
    listSimple = []             # list to contain the final returned list of items (e.g., characters)

    for item in listIn:
        listCombos.append([])   # append an emtpy list to the end for each new item added
        for index in xrange(len(listCombos)-1, 0, -1):  # set the index range to work through the list
            for listPrev in listCombos[index-1]:        # retrieve the lists from the previous column
                listCur = listPrev[:]                   # create a new temporary list object to update
                listCur.append(item)                    # add the item to the previous list to make it current
                listCombos[index].append(listCur)       # list length and append it to the current list

                itemCombo = ''                          # Create a str to concatenate list items into a str
                for item in listCur:                    # concatenate the members of the lists to create
                    itemCombo += item                   # create a string of items
                listSimple.append(itemCombo)            # add to the final output list

    return [listSimple, listCombos]
# END getCombos()

أعلم أنها أكثر عملية استخدام itertools للحصول على كل تركيبات, ولكن يمكن تحقيق هذا جزئيا فقط مع قائمة الفهم إذا تحدث إلى الرغبة في منح تريد كود الكثير

على مجموعات من اثنين من أزواج:

    lambda l: [(a, b) for i, a in enumerate(l) for b in l[i+1:]]

و مجموعات من ثلاثة أزواج ، فإنه من السهل مثل هذا:

    lambda l: [(a, b, c) for i, a in enumerate(l) for ii, b in enumerate(l[i+1:]) for c in l[i+ii+2:]]

والنتيجة هي متطابقة باستخدام itertools.تركيبات:

import itertools
combs_3 = lambda l: [
    (a, b, c) for i, a in enumerate(l) 
    for ii, b in enumerate(l[i+1:]) 
    for c in l[i+ii+2:]
]
data = ((1, 2), 5, "a", None)
print("A:", list(itertools.combinations(data, 3)))
print("B:", combs_3(data))
# A: [((1, 2), 5, 'a'), ((1, 2), 5, None), ((1, 2), 'a', None), (5, 'a', None)]
# B: [((1, 2), 5, 'a'), ((1, 2), 5, None), ((1, 2), 'a', None), (5, 'a', None)]

ودون استخدام itertools:

def combine(inp):
    return combine_helper(inp, [], [])


def combine_helper(inp, temp, ans):
    for i in range(len(inp)):
        current = inp[i]
        remaining = inp[i + 1:]
        temp.append(current)
        ans.append(tuple(temp))
        combine_helper(remaining, temp, ans)
        temp.pop()
    return ans


print(combine(['a', 'b', 'c', 'd']))

وهنا نوعان من تطبيقات itertools.combinations

واحد يقوم بإرجاع قائمة

def combinations(lst, depth, start=0, items=[]):
    if depth <= 0:
        return [items]
    out = []
    for i in range(start, len(lst)):
        out += combinations(lst, depth - 1, i + 1, items + [lst[i]])
    return out

ويعود أحد مولد

def combinations(lst, depth, start=0, prepend=[]):
    if depth <= 0:
        yield prepend
    else:
        for i in range(start, len(lst)):
            for c in combinations(lst, depth - 1, i + 1, prepend + [lst[i]]):
                yield c

تجدر الإشارة إلى أن توفير وظيفة مساعد لتلك ينصح لأن حجة أرفقت هي ثابتة ولن تتغير مع كل مكالمة

print([c for c in combinations([1, 2, 3, 4], 3)])
# [[1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4]]

# get a hold of prepend
prepend = [c for c in combinations([], -1)][0]
prepend.append(None)

print([c for c in combinations([1, 2, 3, 4], 3)])
# [[None, 1, 2, 3], [None, 1, 2, 4], [None, 1, 3, 4], [None, 2, 3, 4]]

وهذه هي حالة سطحية جدا ولكن يكون أفضل آمنة من آسف

وماذا عن هذا .. استخدام سلسلة بدلا من القائمة، ولكن نفس الشيء .. سلسلة ويمكن علاج مثل قائمة في بيثون:

def comb(s, res):
    if not s: return
    res.add(s)
    for i in range(0, len(s)):
        t = s[0:i] + s[i + 1:]
        comb(t, res)

res = set()
comb('game', res) 

print(res)

ومزيج من itertools

import itertools
col_names = ["aa","bb", "cc", "dd"]
all_combinations = itertools.chain(*[itertools.combinations(col_names,i+1) for i,_ in enumerate(col_names)])
print(list(all_combinations))

والشكر

دون itertools في بيثون 3 هل يمكن أن تفعل شيئا مثل هذا:

def combinations(arr, carry):
    for i in range(len(arr)):
        yield carry + arr[i]
        yield from combinations(arr[i + 1:], carry + arr[i])

حيث في البداية carry = "".

وعن طريق الفهم القائمة:

def selfCombine( list2Combine, length ):
    listCombined = str( ['list2Combine[i' + str( i ) + ']' for i in range( length )] ).replace( "'", '' ) \
                     + 'for i0 in range(len( list2Combine ) )'
    if length > 1:
        listCombined += str( [' for i' + str( i ) + ' in range( i' + str( i - 1 ) + ', len( list2Combine ) )' for i in range( 1, length )] )\
            .replace( "', '", ' ' )\
            .replace( "['", '' )\
            .replace( "']", '' )

    listCombined = '[' + listCombined + ']'
    listCombined = eval( listCombined )

    return listCombined

list2Combine = ['A', 'B', 'C']
listCombined = selfCombine( list2Combine, 2 )

والناتج سيكون:

['A', 'A']
['A', 'B']
['A', 'C']
['B', 'B']
['B', 'C']
['C', 'C']

وهذا هو تنفيذ بلدي

    def get_combinations(list_of_things):
    """gets every combination of things in a list returned as a list of lists

    Should be read : add all combinations of a certain size to the end of a list for every possible size in the
    the list_of_things.

    """
    list_of_combinations = [list(combinations_of_a_certain_size)
                            for possible_size_of_combinations in range(1,  len(list_of_things))
                            for combinations_of_a_certain_size in itertools.combinations(list_of_things,
                                                                                         possible_size_of_combinations)]
    return list_of_combinations

def combinations(iterable, r):
# combinations('ABCD', 2) --> AB AC AD BC BD CD
# combinations(range(4), 3) --> 012 013 023 123
pool = tuple(iterable)
n = len(pool)
if r > n:
    return
indices = range(r)
yield tuple(pool[i] for i in indices)
while True:
    for i in reversed(range(r)):
        if indices[i] != i + n - r:
            break
    else:
        return
    indices[i] += 1
    for j in range(i+1, r):
        indices[j] = indices[j-1] + 1
    yield tuple(pool[i] for i in indices)


x = [2, 3, 4, 5, 1, 6, 4, 7, 8, 3, 9]
for i in combinations(x, 2):
    print i

إذا كان شخص ما يبحث عن لائحة المعكوس، وكأنني:

stuff = [1, 2, 3, 4]

def reverse(bla, y):
    for subset in itertools.combinations(bla, len(bla)-y):
        print list(subset)
    if y != len(bla):
        y += 1
        reverse(bla, y)

reverse(stuff, 1)

مرخصة بموجب: CC-BY-SA مع الإسناد

لا تنتمي إلى StackOverflow