2 listelerinin eşsiz kombinasyonu bulmak için bir algoritma var mı?

7 Cevap php

I N Listeler Ben eşsiz kombinasyonu bulmak istiyorum var. Ben beyaz tahta üzerine yazdım ve hepsi bir desen var gibi görünüyor, ben henüz bulamadım. Ben bir kaba kuvvet yöntemini ifade edebilir ve bu kesinlikle takip şey olacak hissediyorum. Bir alternatif var mı? Farklı bir veri yapısı (ikili ağaç?) Bu daha uygun gibi bir iş yapmak istiyorsunuz?

Given:

#    1  2
a = [1, 2]
b = [a, b]

Sonucu olacaktır:

c = [1a, 1b, 2a, 2b] # (4 unique combinations)

Given:

v = [1, a]
w = [1, b]
x = [1, c]
y = [1, d]
z = [1, e]

Sonucu olacaktır:

r = [11111, 1bcde, 11cde, 111de, 1111e, a1111, ab111, abc11, abcd1, abcde, 1b1d1, 1bc1e, 11c11, 11c1e, ... ]

7 Cevap

Belki itertools.product arıyoruz:

#!/usr/bin/env python
import itertools
a=[1,2]
b=['a','b']
c=[str(s)+str(t) for s,t in itertools.product(a,b)]
print(c)
['1a', '1b', '2a', '2b']

v=[1,'a']
w=[1,'b']
x=[1,'c']
y=[1,'d']
z=[1,'e']

r=[''.join([str(elt) for elt in p]) for p in itertools.product(v,w,x,y,z)]
print(r)
# ['11111', '1111e', '111d1', '111de', '11c11', '11c1e', '11cd1', '11cde', '1b111', '1b11e', '1b1d1', '1b1de', '1bc11', '1bc1e', '1bcd1', '1bcde', 'a1111', 'a111e', 'a11d1', 'a11de', 'a1c11', 'a1c1e', 'a1cd1', 'a1cde', 'ab111', 'ab11e', 'ab1d1', 'ab1de', 'abc11', 'abc1e', 'abcd1', 'abcde']

Bu ürün, ürün olarak 2 ** 5 elemanları edin. İstediğin bu mu?

itertools.product Python 2.6 bulunmaktadır. Önceki sürümleri için, bu kullanabilirsiniz:

def product(*args, **kwds):
        '''
        Source: http://docs.python.org/library/itertools.html#itertools.product
        '''
        # 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)

Edit: Çıkış jelibon noktaları olarak, orijinal soru benzersiz kümeler için sorar. Yukarıdaki benzersiz kod setleri üretmek olmaz ise a, b, v, w, x, { [(5)]} ya da z tekrar elementler içerir. Bu sizin için bir sorun ise, o zaman itertools.product göndermeden önce bir dizi her liste dönüştürebilirsiniz:

r=[''.join([str(elt) for elt in p]) for p in itertools.product(*(set(elt) for elt in (v,w,x,y,z)))]

Ben başka bir cevap, bu cevap için, sırayla olduğunu düşünüyorum:

Ben beyaz tahta üzerine yazdım ve hepsi bir desen var gibi görünüyor, ben henüz bulamadım.

Orada is bir desen.

Birleştirmek için sadece iki liste olduğunu varsayalım. Sen bir ızgara yaparak tüm kombinasyonları bulabilirsiniz.

       black        blue
     +------------+------------+
coat | black coat | blue coat  |
     +------------+------------+
hat  | black hat  | blue hat   |
     +------------+------------+

Gördüğünüz gibi, 2 * 2 kombinasyonlar vardır. 30 renk ve giyim 14 çeşit olsaydı, 30 * 14 = 420 kombinasyonları olurdu.

Eğer daha çok liste eklemek gibi desen devam ediyor. Bunun yerine 2 boyutlu bir dikdörtgen, bir kutu 3-boyutlu bir dizi, ya da sonuçta bir n boyutlu hyperrectangle olsun. Ne olursa olsun, toplam kombinasyon sayısı her zaman tüm listelerinin uzunlukları ürünüdür.

Eğer kaç listeleri biliyorsanız, iç içe döngüler tüm kombinasyonlar yapmak için doğal bir yoldur.

for color in colors:
    for kind in kinds:
        print color, kind  # "black coat", "black hat", etc.

Listeleri ile başlamak Sözlük amacıyla ve hiçbir çiftleri varsa, çıkış da sözlükte düzen olacak.

Ben soru girişlerin yeti sorar sanmıyorum, ben girdi setleri Kartezyen ürün (parçası) için sorar düşünüyorum. Ben yanılıyorsam biri bana doğru bekliyoruz.

Ve, bir algoritma gibi, sıra şimdi bu sizin aradığınız ne olduğunu biliyoruz, Google arkadaşınız olacak.

İkinci örnekte, sizin sonuç kümesinden gibi 1b1de gibi girdilerin dışlanması. Bu kasıtlı mı? Bu kasıtlı ise, çıkış inşa edildiği kural nedir?

Her listeden tam olarak bir öğe seçerek oluşturulan tüm olası listeler - Ben Kartezyen ürün istiyorum varsayarak yaşıyorum. Bu gibi yinelemeli uygulayabilirsiniz:

def cartesian_product(l):
    if l:
    	for b in cartesian_product(l[1:]):
    		for a in l[0]:
    			yield [a] + b
    else:
    	yield []		

l = [
 [ 'a', 'b' ],
 [ 'c', 'd', 'e' ],
 [ 'f', 'g' ],
]

for x in cartesian_product(l):
    print x

Güncelleme: ~ itertools.product of unutbu önerisi iyidir, ama ben yine de burada bırakacağım.

İhtiyacınız yana cartesian product, bu kullanın itertools!

>>> import itertools
>>> v = [1, 'a']
>>> w = [1, 'b']
>>> x = [1, 'c']
>>> y = [1, 'd']
>>> z = [1, 'e']

>>> p = [''.join(str(x) for x in c) for c in itertools.product(v,w,x,y,z)]
>>> p
['11111', '1111e', '111d1', '111de', '11c11', '11c1e', '11cd1', '11cde', '1b111'
, '1b11e', '1b1d1', '1b1de', '1bc11', '1bc1e', '1bcd1', '1bcde', 'a1111', 'a111e
', 'a11d1', 'a11de', 'a1c11', 'a1c1e', 'a1cd1', 'a1cde', 'ab111', 'ab11e', 'ab1d
1', 'ab1de', 'abc11', 'abc1e', 'abcd1', 'abcde']
>>>

Bu işi olabilir?

def getAllCombinations(listOfLists):
    if len(listOfLists) == 1:
        return [str(x) for x in listOfLists[0]]

    result = set()
    head, tail = listOfLists[0], listOfLists[1:]

    tailCombs = getAllCombinations(tail)
    for elem in head:
        for tc in tailCombs:
            result.add(str(elem) + tc)
    return result

v = [1, 'a']
w = [1, 'b']
x = [1, 'c']
y = [1, 'd']
z = [1, 'e']

>>> print getAllCombinations([v, w, x, y, z])
set(['111de', 'abc11', 'a1c1e', 'a111e', '11c11', 'ab11e', '1bc11', 'ab1d1', 'a1cd1', '1b1de', 'a11d1', '11111', '1b111', '11cd1', 'abcd1', '1bcde', 'ab111', '1bc1e', 'abc1e', '111d1', 'a1111', '11c1e', 'a1c11', '11cde', '1b11e', '1bcd1', 'abcde', 'a1cde', '1b1d1', 'a11de', 'ab1de', '1111e'])

Sen Kartezyen ürün arıyoruz. Python, dizilerini isterseniz:

c = [(x, y) for x in a for y in b]
r = [(vv, ww, xx, yy, zz)
     for vv in v  for ww in w  for xx in x  for yy in y  for zz in z]

etiketler