Saya memiliki daftar n angka, mis. [1, 2, 3, 4] dan saya ingin menulis beberapa kode dengan python yang menemukan semua kemungkinan kombinasi di mana angka-angka dikelompokkan menjadi 2s atau 1s dan semua n elemen ada.

Misalnya dengan kasus n=4 solusinya adalah,

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

Untuk memberikan penjelasan intuitif, saya mencari semua kombinasi dari empat orang di mana mereka berpasangan atau bekerja sendiri.

Saya telah mencoba campuran kombinasi berikut tetapi saya tidak dapat melihat metode yang jelas untuk melanjutkan dari sini,

pairs = list(combinations([0, 1, 2, 3], 2))
groups = list(combinations(pairs, 2))

unique = []
for p in groups:
    if len(set([i for sub in p for i in sub])) == 4:
        unique.append(p)

unique + pairs
>> [((0, 1), (2, 3)),
    ((0, 2), (1, 3)),
    ((0, 3), (1, 2)),
    (0, 1),
    (0, 2),
    (0, 3),
    (1, 2),
    (1, 3),
    (2, 3)]

Jika saya bisa mengisi setiap entri sehingga keempat nomor hadir dengan memasukkannya sebagai individu (tidak berpasangan) ini akan memberikan solusi saya.

Saya tidak perlu melakukan ini untuk daftar yang sangat besar jadi saya tidak terlalu peduli dengan waktu berjalan (saya mengatakan ini karena saya sadar bahwa metode saya saat ini dapat keluar dari kendali dengan cepat dengan n besar).

Bantuan apa pun akan sangat bagus!

Terima kasih

0
Joe Emmens 11 Mei 2021, 18:34

2 jawaban

Jawaban Terbaik

Ini sangat rumit. Saya menggunakan fungsi combinations untuk menarik keluar setiap subset genap dan kemudian menulis proses pemasangan rekursif untuk membuat semua kemungkinan pasangan di subset genap tersebut.

from itertools import combinations

def make_pairs(source, pairs=None, used=None):
    if pairs is None: # entry level
        sin = 0
        results = []
        pairs = []
        used = [False] * len(source)
    else:
        sin = 1
        while used[sin]:
            sin +=1
    used[sin] = True
    for dex in range(sin + 1, len(source)):
        if not used[dex]:
            pairs.append( (source[sin], source[dex]))
            if len(pairs)*2 == len(source):
                yield tuple(pairs)
            else:
                used[dex] = True
                yield from make_pairs(source, pairs, used)
                used[dex] = False
            pairs.pop()
    used[sin]=False


def make_ones_and_twos(source):
    yield tuple(source) # all singles case
    inpair = 2
    while inpair <= len(source):
        for paired in combinations(source,inpair): # choose elements going in pairs
            singles = tuple(sorted(set(source)-set(paired))) # others are singleton
            # partition paired into actual pairs
            for pairing in make_pairs(paired):
                yield (pairing+singles)
        inpair += 2

# sample run       
elements = ['a','c','g','t','u']

print(*make_ones_and_twos(elements),sep='\n')

Memberikan keluaran

('a', 'c', 'g', 't', 'u')
(('a', 'c'), 'g', 't', 'u')
(('a', 'g'), 'c', 't', 'u')
(('a', 't'), 'c', 'g', 'u')
(('a', 'u'), 'c', 'g', 't')
(('c', 'g'), 'a', 't', 'u')
(('c', 't'), 'a', 'g', 'u')
(('c', 'u'), 'a', 'g', 't')
(('g', 't'), 'a', 'c', 'u')
(('g', 'u'), 'a', 'c', 't')
(('t', 'u'), 'a', 'c', 'g')
(('a', 'c'), ('g', 't'), 'u')
(('a', 'g'), ('c', 't'), 'u')
(('a', 't'), ('c', 'g'), 'u')
(('a', 'c'), ('g', 'u'), 't')
(('a', 'g'), ('c', 'u'), 't')
(('a', 'u'), ('c', 'g'), 't')
(('a', 'c'), ('t', 'u'), 'g')
(('a', 't'), ('c', 'u'), 'g')
(('a', 'u'), ('c', 't'), 'g')
(('a', 'g'), ('t', 'u'), 'c')
(('a', 't'), ('g', 'u'), 'c')
(('a', 'u'), ('g', 't'), 'c')
(('c', 'g'), ('t', 'u'), 'a')
(('c', 't'), ('g', 'u'), 'a')
(('c', 'u'), ('g', 't'), 'a')
2
Joffan 11 Mei 2021, 19:44

Ini mungkin melakukannya:

from itertools import combinations

elements = [0, 1, 2, 3]

pairs = list(combinations(elements, 2))
groups = list(combinations(pairs, 2))

unique = []
for p in groups:
    if len(set([i for sub in p for i in sub])) == 4:
        unique.append(p)

pairs_with_singles = []
for pair in pairs:
    missing = set(elements) - set(pair)
    pairs_with_singles.append((pair, *missing))

print(unique + pairs_with_singles + [tuple(elements)])
1
Matteo Zanoni 11 Mei 2021, 15:49