Wie erhält man alle möglichen Kombinationen der Elemente einer Liste?

Question

Ich habe eine Liste mit 15 Zahlen, und ich muss einen Code schreiben, der alle 32.768 Kombinationen dieser Zahlen erzeugt.

Ich habe gefunden einige Codes (durch Googeln), die anscheinend tut, was ich suche, aber ich fand den Code ziemlich undurchsichtig und bin vorsichtig, es zu benutzen. Außerdem habe ich das Gefühl, dass es eine elegantere Lösung geben muss.

Das Einzige, was mir einfällt, wäre, einfach eine Schleife durch die Dezimalzahlen 1-32768 zu ziehen und diese in Binärzahlen umzuwandeln, und die Binärdarstellung als Filter zu verwenden, um die entsprechenden Zahlen herauszufiltern.

Kennt jemand einen besseren Weg? Verwendung von map() vielleicht?

Answer 1

3 Funktionen:

1. alle Kombinationen von n Elementen Liste
2. alle Kombinationen von n Elementen der Liste, deren Reihenfolge nicht eindeutig ist

3. alle Permutationen

   import sys

   def permutations(a): return combinations(a, len(a))

   def combinations(a, n): if n == 1: for x in a: yield [x] else: for i in range(len(a)): for x in combinations(a[:i] + a[i+1:], n-1): yield [a[i]] + x

   def combinationsNoOrder(a, n): if n == 1: for x in a: yield [x] else: for i in range(len(a)): for x in combinationsNoOrder(a[:i], n-1): yield [a[i]] + x

   if name == "main": for s in combinations(list(map(int, sys.argv[2:])), int(sys.argv[1])): print(s)

Answer 2

from itertools import combinations

features = ['A', 'B', 'C']
tmp = []
for i in range(len(features)):
    oc = combinations(features, i + 1)
    for c in oc:
        tmp.append(list(c))

---

Ausgabe

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

Answer 3

Ich mag dieses Problem, weil es so viele Möglichkeiten gibt, es umzusetzen. Ich habe beschlossen, eine Referenzantwort für die Zukunft zu erstellen.

Was soll in der Produktion verwendet werden?

Die Dokumentation von intertools enthält ein in sich geschlossenes Beispiel, warum sollten Sie es nicht in Ihrem Code verwenden? Einige Leute schlugen die Verwendung von more_itertools.powerset aber es hat genau die gleiche Umsetzung ! An Ihrer Stelle würde ich nicht das ganze Paket wegen einer Kleinigkeit installieren. Wahrscheinlich ist dies der beste Weg zu gehen:

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

Andere mögliche Ansätze

Ansatz 0: Verwendung von Kombinationen

import itertools

def subsets(nums):
    result = []
    for i in range(len(nums) + 1):
        result += itertools.combinations(nums, i)
    return result

Ansatz 1: Geradlinige Rekursion

def subsets(nums):
    result = []

    def powerset(alist, index, curr):
        if index == len(alist):
            result.append(curr)
            return

        powerset(alist, index + 1, curr + [alist[index]])
        powerset(alist, index + 1, curr)

    powerset(nums, 0, [])
    return result

Ansatz 2: Backtracking

def subsets(nums):
    result = []

    def backtrack(index, curr, k):
        if len(curr) == k:
            result.append(list(curr))
            return
        for i in range(index, len(nums)):
            curr.append(nums[i])
            backtrack(i + 1, curr, k)
            curr.pop()

    for k in range(len(nums) + 1):
        backtrack(0, [], k)
    return result

ou

def subsets(nums):
    result = []

    def dfs(nums, index, path, result):
        result.append(path)
        for i in range(index, len(nums)):
            dfs(nums, i + 1, path + [nums[i]], result)

    dfs(nums, 0, [], result)
    return result

Ansatz 3: Bitmaskierung

def subsets(nums):
    res = []
    n = len(nums)
    for i in range(1 << n):
        aset = []
        for j in range(n):
            value = (1 << j) & i  # value = (i >> j) & 1
            if value:
                aset.append(nums[j])
        res.append(aset)
    return res

oder (nicht wirklich Bitmaskierung, sondern die Intuition, dass es genau 2^n Teilmengen gibt)

def subsets(nums):
    subsets = []
    expected_subsets = 2 ** len(nums)

    def generate_subset(subset, nums):
        if len(subsets) >= expected_subsets:
            return
        if len(subsets) < expected_subsets:
            subsets.append(subset)
        for i in range(len(nums)):
            generate_subset(subset + [nums[i]], nums[i + 1:])

    generate_subset([], nums)
    return subsets

Ansatz 4: Kaskadierung

def subsets(nums):
    result = [[]]
    for i in range(len(nums)):
        for j in range(len(result)):
            subset = list(result[j])
            subset.append(nums[i])
            result.append(subset)
    return result

Answer 4

Sie können auch die Powerset Funktion aus dem hervorragenden more_itertools Paket.

from more_itertools import powerset

l = [1,2,3]
list(powerset(l))

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

Wir können auch überprüfen, ob er die Anforderungen des Auftraggebers erfüllt

from more_itertools import ilen

assert ilen(powerset(range(15))) == 32_768

Answer 5

Hier ist noch eine weitere Lösung (Einzeiler), die die Verwendung der itertools.combinations Funktion, aber hier verwenden wir eine doppelte Listenauffassung (im Gegensatz zu einer for-Schleife oder Summe):

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

---

Demo:

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