Menemukan semua kombinasi substitusi unik dengan Python

Diberikan dua daftar label unik seperti:

a = ['Joe', 'Mary', 'Sue']
b = ['S0', 'S1', 'S2', 'S3', 'S4', 'S5']

Bagaimana cara saya menemukan secara efisien semua kemungkinan kombinasi di mana elemen dari daftar a diganti atau dipetakan ke dalam daftar b? misalnya Jika S0 = S1 = Joe, S2 = Mary, S3 = S4 = S5 = Sue maka saya akan mempunyai:

{'S0': 'Joe', 'S1': 'Joe', 'S2': 'Mary', 'S3': 'Sue', 'S4': 'Sue', 'S5': 'Sue'}

Saya mulai dengan pendekatan for-loop bersarang sederhana ini:

def iter_mapping_combos(names1, names2):
    q = [(names2, {})]
    priors = set()
    while q:
        _names2, _mapping = q.pop(0)
        key = (frozenset(_names2), frozenset(_mapping.items()))
        if key in priors:
            continue
        priors.add(key)
        for n1 in names1:
            for n2 in _names2:
                if n2 in _mapping:
                    continue
                _mapping_next = dict(_mapping)
                _mapping_next[n2] = n1
                _names2_next = set(_names2)
                _names2_next.remove(n2)
                if _names2_next:
                    q.append((_names2_next, _mapping_next))
                else:
                    yield _mapping_next

for mapping in iter_mapping_combos(['Joe', 'Mary', 'Sue'], ['S0', 'S1', 'S2', 'S3', 'S4', 'S5']):
    print(mapping)

Ini berfungsi, tetapi seperti yang dapat Anda bayangkan, ini tidak seefisien dan tidak dapat diskalakan dengan baik seiring bertambahnya panjang daftar. Apakah ada cara yang lebih baik untuk melakukan ini?


python combinatorics
person Cerin    schedule 25.09.2019    source sumber

Jawaban (4)


arrow_upward
2
arrow_downward

Anda dapat menggunakan itertools.product untuk menghasilkan produk kartesius yang diinginkan:

from itertools import product

def iter_mapping_combos(names1, names2):
    yield from (dict(zip(names2, p)) for p in product(names1, repeat=len(names2)))

sehingga:

for mapping in iter_mapping_combos(['Joe', 'Mary'], ['S0', 'S1', 'S2']):
    print(mapping)

keluaran:

{'S0': 'Joe', 'S1': 'Joe', 'S2': 'Joe'}
{'S0': 'Joe', 'S1': 'Joe', 'S2': 'Mary'}
{'S0': 'Joe', 'S1': 'Mary', 'S2': 'Joe'}
{'S0': 'Joe', 'S1': 'Mary', 'S2': 'Mary'}
{'S0': 'Mary', 'S1': 'Joe', 'S2': 'Joe'}
{'S0': 'Mary', 'S1': 'Joe', 'S2': 'Mary'}
{'S0': 'Mary', 'S1': 'Mary', 'S2': 'Joe'}
{'S0': 'Mary', 'S1': 'Mary', 'S2': 'Mary'}

Demo: https://repl.it/repls/BlondStalePostscript

person blhsing    schedule 25.09.2019
comment
Setelah meninjau kembali pertanyaan ini, saya yakin ini adalah metode paling efisien untuk membuat kombinasi yang diinginkan. - person Alexander; 28.09.2019

arrow_upward
1
arrow_downward

Anda dapat membuat kombinasi yang diinginkan dan kemudian menggunakan zip:

a = ['Joe', 'Mary', 'Sue']
b = ['S0', 'S1', 'S2', 'S3', 'S4', 'S5']
def combos(d, c = []):
  if len(b) == sum(map(len, c)):
     yield c
  for i in range(1, len(d)+1):
     yield from combos(d[i:], c+[d[:i]])

r = [[[j for _ in k] for j, k in zip(a, i)] for i in combos(b) if len(i) == 3]
result = [dict(zip(b, [i for k in j for i in k])) for j in r]

Keluaran:

[{'S0': 'Joe', 'S1': 'Mary', 'S2': 'Sue', 'S3': 'Sue', 'S4': 'Sue', 'S5': 'Sue'}, {'S0': 'Joe', 'S1': 'Mary', 'S2': 'Mary', 'S3': 'Sue', 'S4': 'Sue', 'S5': 'Sue'}, {'S0': 'Joe', 'S1': 'Mary', 'S2': 'Mary', 'S3': 'Mary', 'S4': 'Sue', 'S5': 'Sue'}, {'S0': 'Joe', 'S1': 'Mary', 'S2': 'Mary', 'S3': 'Mary', 'S4': 'Mary', 'S5': 'Sue'}, {'S0': 'Joe', 'S1': 'Joe', 'S2': 'Mary', 'S3': 'Sue', 'S4': 'Sue', 'S5': 'Sue'}, {'S0': 'Joe', 'S1': 'Joe', 'S2': 'Mary', 'S3': 'Mary', 'S4': 'Sue', 'S5': 'Sue'}, {'S0': 'Joe', 'S1': 'Joe', 'S2': 'Mary', 'S3': 'Mary', 'S4': 'Mary', 'S5': 'Sue'}, {'S0': 'Joe', 'S1': 'Joe', 'S2': 'Joe', 'S3': 'Mary', 'S4': 'Sue', 'S5': 'Sue'}, {'S0': 'Joe', 'S1': 'Joe', 'S2': 'Joe', 'S3': 'Mary', 'S4': 'Mary', 'S5': 'Sue'}, {'S0': 'Joe', 'S1': 'Joe', 'S2': 'Joe', 'S3': 'Joe', 'S4': 'Mary', 'S5': 'Sue'}]
person Ajax1234    schedule 25.09.2019

arrow_upward
1
arrow_downward

Meskipun Anda tidak menentukan persyaratan masalah Anda, dari satu contoh yang saya simpulkan bahwa Anda perlu memetakan setiap elemen b ke satu elemen a (walaupun elemen a tertentu mungkin memiliki lebih dari satu b elemen dipetakan padanya). Itu memiliki ledakan eksponensial, total len(b) ** len(a) pemetaan berbeda.

Anda dapat mempersingkat kode Anda sedikit: belajar menggunakan modul itertools; ini secara efektif merupakan penerapan metode product, melintasi enam salinan a. Secara sederhana:

product(*[a]*len(b))

Apakah itu membuat Anda maju?

person Prune    schedule 25.09.2019

arrow_upward
1
arrow_downward

Perhatikan bahwa metode Anda menghitung berlebihan sebanyak 6x (yaitu jumlah item dalam b). Pada sampel saya yang lebih kecil, misalnya, kode Anda menghasilkan yang berikut ini yang hanya merupakan penataan ulang item yang sama:

[{'S0': 'Joe', 'S2': 'Joe', 'S1': 'Joe'},
 {'S0': 'Joe', 'S1': 'Joe', 'S2': 'Joe'},
 {'S1': 'Joe', 'S2': 'Joe', 'S0': 'Joe'},
 ...]

Menggunakan contoh yang lebih kecil untuk menunjukkan penerapan saya:

from itertools import combinations_with_replacement, permutations

a = ['Joe', 'Mary'] 
b = ['S0', 'S1', 'S2'] 

result = []
combos = combinations_with_replacement(a, len(b))
for combo in combos:
    seen = set()
    for p in permutations(range(len(b)), len(b)):
        order = tuple(combo[idx] for idx in p)
        if order not in seen:
            seen.add(order)
            result.append(order)

>>> result
[('Joe', 'Joe', 'Joe'),
 ('Joe', 'Joe', 'Mary'),
 ('Joe', 'Mary', 'Joe'),
 ('Mary', 'Joe', 'Joe'),
 ('Joe', 'Mary', 'Mary'),
 ('Mary', 'Joe', 'Mary'),
 ('Mary', 'Mary', 'Joe'),
 ('Mary', 'Mary', 'Mary')]

Hasilnya kemudian perlu dikodekan ke kunci di b:

final_result = [{b[n]: val for n, val in enumerate(row)} 
                for row in result]
>>> final_result
[{'S0': 'Joe', 'S1': 'Joe', 'S2': 'Joe'},
 {'S0': 'Joe', 'S1': 'Joe', 'S2': 'Mary'},
 {'S0': 'Joe', 'S1': 'Mary', 'S2': 'Joe'},
 {'S0': 'Mary', 'S1': 'Joe', 'S2': 'Joe'},
 {'S0': 'Joe', 'S1': 'Mary', 'S2': 'Mary'},
 {'S0': 'Mary', 'S1': 'Joe', 'S2': 'Mary'},
 {'S0': 'Mary', 'S1': 'Mary', 'S2': 'Joe'},
 {'S0': 'Mary', 'S1': 'Mary', 'S2': 'Mary'}]
person Alexander    schedule 25.09.2019