Hoe kan ik het Cartesiaanse product (elke mogelijke combinatie van waarden) van een groep lijsten?
Invoer:
somelists = [
[1, 2, 3],
['a', 'b'],
[4, 5]
]
Gewenste uitvoer:
[(1, 'a', 4), (1, 'a', 5), (1, 'b', 4), (1, 'b', 5), (2, 'a', 4), (2, 'a', 5) ...]
Antwoord 1, Autoriteit 100%
itertools.product
beschikbaar uit Python 2.6.
import itertools
somelists = [
[1, 2, 3],
['a', 'b'],
[4, 5]
]
for element in itertools.product(*somelists):
print(element)
Wat is hetzelfde als,
for element in itertools.product([1, 2, 3], ['a', 'b'], [4, 5]):
print(element)
Antwoord 2, Autoriteit 21%
import itertools
>>> for i in itertools.product([1,2,3],['a','b'],[4,5]):
... print i
...
(1, 'a', 4)
(1, 'a', 5)
(1, 'b', 4)
(1, 'b', 5)
(2, 'a', 4)
(2, 'a', 5)
(2, 'b', 4)
(2, 'b', 5)
(3, 'a', 4)
(3, 'a', 5)
(3, 'b', 4)
(3, 'b', 5)
>>>
Antwoord 3, Autoriteit 9%
Voor Python 2.5 en ouder:
>>> [(a, b, c) for a in [1,2,3] for b in ['a','b'] for c in [4,5]]
[(1, 'a', 4), (1, 'a', 5), (1, 'b', 4), (1, 'b', 5), (2, 'a', 4),
(2, 'a', 5), (2, 'b', 4), (2, 'b', 5), (3, 'a', 4), (3, 'a', 5),
(3, 'b', 4), (3, 'b', 5)]
Hier is een recursieve versie van product()(slechts een illustratie):
def product(*args):
if not args:
return iter(((),)) # yield tuple()
return (items + (item,)
for items in product(*args[:-1]) for item in args[-1])
Voorbeeld:
>>> list(product([1,2,3], ['a','b'], [4,5]))
[(1, 'a', 4), (1, 'a', 5), (1, 'b', 4), (1, 'b', 5), (2, 'a', 4),
(2, 'a', 5), (2, 'b', 4), (2, 'b', 5), (3, 'a', 4), (3, 'a', 5),
(3, 'b', 4), (3, 'b', 5)]
>>> list(product([1,2,3]))
[(1,), (2,), (3,)]
>>> list(product([]))
[]
>>> list(product())
[()]
Antwoord 4, Autoriteit 6%
Ik zou lijst begrijpen:
somelists = [
[1, 2, 3],
['a', 'b'],
[4, 5]
]
cart_prod = [(a,b,c) for a in somelists[0] for b in somelists[1] for c in somelists[2]]
Antwoord 5, Autoriteit 6%
met itertools.product :
import itertools
result = list(itertools.product(*somelists))
Antwoord 6, Autoriteit 3%
Hier is een recursieve generator, die geen tijdelijke lijsten opslaat
def product(ar_list):
if not ar_list:
yield ()
else:
for a in ar_list[0]:
for prod in product(ar_list[1:]):
yield (a,)+prod
print list(product([[1,2],[3,4],[5,6]]))
Uitgang:
[(1, 3, 5), (1, 3, 6), (1, 4, 5), (1, 4, 6), (2, 3, 5), (2, 3, 6), (2, 4, 5), (2, 4, 6)]
Antwoord 7, autoriteit 2%
In Python 2.6 en hoger kun je ‘itertools.product’ gebruiken. In oudere versies van Python kun je het volgende (bijna — zie documentatie) equivalent gebruiken code uit de documentatie, in ieder geval als startpunt:
def product(*args, **kwds):
# product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
# product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
pools = map(tuple, args) * kwds.get('repeat', 1)
result = [[]]
for pool in pools:
result = [x+[y] for x in result for y in pool]
for prod in result:
yield tuple(prod)
Het resultaat van beide is een iterator, dus als je echt een lijst nodig hebt voor verdere verwerking, gebruik dan list(result).
Antwoord 8, autoriteit 2%
Hoewel er al veel antwoorden zijn, wil ik graag enkele van mijn gedachten delen:
Iteratieve aanpak
def cartesian_iterative(pools):
result = [[]]
for pool in pools:
result = [x+[y] for x in result for y in pool]
return result
Recursieve benadering
def cartesian_recursive(pools):
if len(pools) > 2:
pools[0] = product(pools[0], pools[1])
del pools[1]
return cartesian_recursive(pools)
else:
pools[0] = product(pools[0], pools[1])
del pools[1]
return pools
def product(x, y):
return [xx + [yy] if isinstance(xx, list) else [xx] + [yy] for xx in x for yy in y]
Lambda-benadering
def cartesian_reduct(pools):
return reduce(lambda x,y: product(x,y) , pools)
Antwoord 9
Recursieve benadering:
def rec_cart(start, array, partial, results):
if len(partial) == len(array):
results.append(partial)
return
for element in array[start]:
rec_cart(start+1, array, partial+[element], results)
rec_res = []
some_lists = [[1, 2, 3], ['a', 'b'], [4, 5]]
rec_cart(0, some_lists, [], rec_res)
print(rec_res)
Iteratieve aanpak:
def itr_cart(array):
results = [[]]
for i in range(len(array)):
temp = []
for res in results:
for element in array[i]:
temp.append(res+[element])
results = temp
return results
some_lists = [[1, 2, 3], ['a', 'b'], [4, 5]]
itr_res = itr_cart(some_lists)
print(itr_res)
Antwoord 10
Een kleine wijziging aan de bovenstaande recursieve generatoroplossing in variadische smaak:
def product_args(*args):
if args:
for a in args[0]:
for prod in product_args(*args[1:]) if args[1:] else ((),):
yield (a,) + prod
En natuurlijk een wrapper waardoor het precies hetzelfde werkt als die oplossing:
def product2(ar_list):
"""
>>> list(product(()))
[()]
>>> list(product2(()))
[]
"""
return product_args(*ar_list)
met één afweging: het controleert of recursie moet breken bij elke buitenste lus, en één winst: geen opbrengst bij lege aanroep, bijv.product(()), wat volgens mij semantisch correcter zou zijn (zie de doctest).
Wat betreft het begrip van een lijst: de wiskundige definitie is van toepassing op een willekeurig aantal argumenten, terwijl het begrip van een lijst slechts een bekend aantal van hen kan behandelen.
Antwoord 11
Om iets toe te voegen aan wat al is gezegd: als je sympy gebruikt, kun je symbolen gebruiken in plaats van tekenreeksen, wat ze wiskundig bruikbaar maakt.
import itertools
import sympy
x, y = sympy.symbols('x y')
somelist = [[x,y], [1,2,3], [4,5]]
somelist2 = [[1,2], [1,2,3], [4,5]]
for element in itertools.product(*somelist):
print element
Over sympy.
Antwoord 12
Ik geloof dat dit werkt:
def cartesian_product(L):
if L:
return {(a,) + b for a in L[0]
for b in cartesian_product(L[1:])}
else:
return {()}
Antwoord 13
Met vroege afwijzing:
def my_product(pools: List[List[Any]], rules: Dict[Any, List[Any]], forbidden: List[Any]) -> Iterator[Tuple[Any]]:
"""
Compute the cartesian product except it rejects some combinations based on provided rules
:param pools: the values to calculate the Cartesian product on
:param rules: a dict specifying which values each value is incompatible with
:param forbidden: values that are never authorized in the combinations
:return: the cartesian product
"""
if not pools:
return
included = set()
# if an element has an entry of 0, it's acceptable, if greater than 0, it's rejected, cannot be negative
incompatibles = defaultdict(int)
for value in forbidden:
incompatibles[value] += 1
selections = [-1] * len(pools)
pool_idx = 0
def current_value():
return pools[pool_idx][selections[pool_idx]]
while True:
# Discard incompatibilities from value from previous iteration on same pool
if selections[pool_idx] >= 0:
for value in rules[current_value()]:
incompatibles[value] -= 1
included.discard(current_value())
# Try to get to next value of same pool
if selections[pool_idx] != len(pools[pool_idx]) - 1:
selections[pool_idx] += 1
# Get to previous pool if current is exhausted
elif pool_idx != 0:
selections[pool_idx] = - 1
pool_idx -= 1
continue
# Done if first pool is exhausted
else:
break
# Add incompatibilities of newly added value
for value in rules[current_value()]:
incompatibles[value] += 1
included.add(current_value())
# Skip value if incompatible
if incompatibles[current_value()] or \
any(intersection in included for intersection in rules[current_value()]):
continue
# Submit combination if we're at last pool
if pools[pool_idx] == pools[-1]:
yield tuple(pool[selection] for pool, selection in zip(pools, selections))
# Else get to next pool
else:
pool_idx += 1
Ik had een gevalwaarbij ik het eerste resultaat van een zeer groot cartesiaans product. En het zou eeuwen duren, ondanks dat ik maar één item wilde. Het probleem was dat het veel ongewenste resultaten moest doorlopen voordat het de juiste vond vanwege de volgorde van de resultaten. Dus als ik 10 lijsten van 50 elementen had en het eerste element van de twee eerste lijsten onverenigbaar was, moest het door het Cartesiaanse product van de laatste 8 lijsten gaan, ondanks dat ze allemaal zouden worden afgewezen.
Deze implementatie maakt het mogelijk om een resultaat te testen voordat het één item uit elke lijst bevat. Dus als ik controleer of een element niet compatibel is met de reeds opgenomen elementen uit de vorige lijsten, ga ik onmiddellijk naar het volgende element van de huidige lijst in plaats van alle producten van de volgende lijsten te doorlopen.
Antwoord 14
De volgende code is een 95% kopie van Numpy gebruiken om een array te bouwen van alle combinaties van twee arrays, allemaal credits gaan daar! Dit zou veel sneller zijn omdat het alleen in numpy is.
import numpy as np
def cartesian(arrays, dtype=None, out=None):
arrays = [np.asarray(x) for x in arrays]
if dtype is None:
dtype = arrays[0].dtype
n = np.prod([x.size for x in arrays])
if out is None:
out = np.zeros([n, len(arrays)], dtype=dtype)
m = int(n / arrays[0].size)
out[:,0] = np.repeat(arrays[0], m)
if arrays[1:]:
cartesian(arrays[1:], out=out[0:m, 1:])
for j in range(1, arrays[0].size):
out[j*m:(j+1)*m, 1:] = out[0:m, 1:]
return out
U moet het dtype als parameter definiëren als u het dtype niet uit de eerste invoer voor alle invoer wilt nemen. Neem dtype = ‘object’ als je letters en cijfers als items hebt. Test:
somelists = [
[1, 2, 3],
['a', 'b'],
[4, 5]
]
[tuple(x) for x in cartesian(somelists, 'object')]
Uit:
[(1, 'a', 4),
(1, 'a', 5),
(1, 'b', 4),
(1, 'b', 5),
(2, 'a', 4),
(2, 'a', 5),
(2, 'b', 4),
(2, 'b', 5),
(3, 'a', 4),
(3, 'a', 5),
(3, 'b', 4),
(3, 'b', 5)]
Antwoord 15
Stonehenge-aanpak:
def giveAllLists(a, t):
if (t + 1 == len(a)):
x = []
for i in a[t]:
p = [i]
x.append(p)
return x
x = []
out = giveAllLists(a, t + 1)
for i in a[t]:
for j in range(len(out)):
p = [i]
for oz in out[j]:
p.append(oz)
x.append(p)
return x
xx= [[1,2,3],[22,34,'se'],['k']]
print(giveAllLists(xx, 0))
uitvoer:
[[1, 22, 'k'], [1, 34, 'k'], [1, 'se', 'k'], [2, 22, 'k'], [2, 34, 'k'], [2, 'se', 'k'], [3, 22, 'k'], [3, 34, 'k'], [3, 'se', 'k']]
Antwoord 16
U kunt itertools.productin de standaardbibliotheek gebruiken om het Cartesiaanse product te krijgen. Andere coole, gerelateerde hulpprogramma’s in itertoolsomvatten permutations, combinations, en combinations_with_replacement. Hier is een link naar een Python-codepen voor het snippet hieronder:
from itertools import product
somelists = [
[1, 2, 3],
['a', 'b'],
[4, 5]
]
result = list(product(*somelists))
print(result)