Cari kamus semua kombinasi item yang mungkin menggunakan Python

Semasa bekerja dengan Python, anda mungkin sering menghadapi situasi di mana anda perlu menjana semua kemungkinan gabungan item daripada kamus tertentu. Tugas ini sangat penting dalam pelbagai bidang seperti analisis data, pembelajaran mesin, pengoptimuman dan masalah gabungan. Dalam catatan blog teknikal ini, kami akan menyelami cara yang berbeza untuk mencari semua kombinasi projek yang mungkin menggunakan Python dengan cekap.

Mari kita wujudkan pemahaman yang jelas tentang masalah yang dihadapi. Katakan kita mempunyai kamus di mana kunci mewakili item yang berbeza dan nilai yang dikaitkan dengan setiap kunci mewakili atribut atau ciri masing-masing. Matlamat kami adalah untuk menjana kamus baharu yang mengandungi semua kemungkinan kombinasi dengan mengambil kira satu item bagi setiap kunci. Setiap gabungan harus diwakili sebagai kunci dalam kamus hasil, dan nilai yang sepadan harus mencerminkan sifat item dalam gabungan itu.

Untuk menggambarkan ini, pertimbangkan contoh kamus input berikut −

items = {
   'item1': ['property1', 'property2'],
   'item2': ['property3'],
   'item3': ['property4', 'property5', 'property6']
}

Dalam kes ini, kamus output yang dikehendaki ialah −

combinations = {
   ('item1', 'item2', 'item3'): ['property1', 'property3', 'property4'],
   ('item1', 'item2', 'item3'): ['property1', 'property3', 'property5'],
   ('item1', 'item2', 'item3'): ['property1', 'property3', 'property6'],
   ('item1', 'item2', 'item3'): ['property2', 'property3', 'property4'],
   ('item1', 'item2', 'item3'): ['property2', 'property3', 'property5'],
   ('item1', 'item2', 'item3'): ['property2', 'property3', 'property6']
}

Adalah penting untuk ambil perhatian bahawa dalam kamus output, kekunci mewakili gabungan item yang berbeza, manakala nilai sepadan dengan atribut yang dikaitkan dengan item tersebut dalam setiap gabungan.

Kaedah 1: Gunakan Itertools.product

Cara yang cekap untuk menyelesaikan masalah ini ialah dengan menggunakan fungsi produk yang berkuasa dalam modul itertools Python. Fungsi produk menjana produk Cartesian bagi objek boleh lelar input, yang sesuai untuk keperluan kita. Dengan menggunakan fungsi ini, kami boleh memperoleh semua kemungkinan gabungan atribut item dengan berkesan. Mari kita lihat coretan kod yang melaksanakan pendekatan ini −

import itertools

def find_all_combinations(items):
   keys = list(items.keys())
   values = list(items.values())
   combinations = {}

   for combination in itertools.product(*values):
      combinations[tuple(keys)] = list(combination)

   return combinations

Pertama, kami mengekstrak kunci dan nilai daripada kamus input. Dengan memanfaatkan fungsi produk, kami menjana semua kemungkinan gabungan atribut projek. Selepas itu, kami memetakan setiap gabungan ke kunci yang sepadan dan menyimpan hasilnya dalam kamus gabungan.

Masuk

items = {
   'item1': ['property1', 'property2'],
   'item2': ['property3'],
   'item3': ['property4', 'property5', 'property6']
}

Output

combinations = {
   ('item1', 'item2', 'item3'): ['property1', 'property3', 'property4'],
   ('item1', 'item2', 'item3'): ['property1', 'property3', 'property5'],
   ('item1', 'item2', 'item3'): ['property1', 'property3', 'property6'],
   ('item1', 'item2', 'item3'): ['property2', 'property3', 'property4'],
   ('item1', 'item2', 'item3'): ['property2', 'property3', 'property5'],
   ('item1', 'item2', 'item3'): ['property2', 'property3', 'property6']
}

Kaedah 2: Kaedah rekursif

Satu lagi cara yang mungkin untuk mencari semua kombinasi yang mungkin adalah dengan menggunakan fungsi rekursif. Pendekatan ini amat berguna apabila berurusan dengan kamus yang mengandungi item yang agak sedikit. Mari kita lihat pelaksanaannya −

def find_all_combinations_recursive(items):
   keys = list(items.keys())
   values = list(items.values())
   combinations = {}

   def generate_combinations(current_index, current_combination):
      if current_index == len(keys):
         combinations[tuple(keys)] = list(current_combination)
         return

      for value in values[current_index]:
         generate_combinations(current_index + 1, current_combination + [value])

   generate_combinations(0, [])

   return combinations

Masuk

items = {
   'item1': ['property1', 'property2'],
   'item2': ['property3'],
   'item3': ['property4', 'property5', 'property6']
}

Output

combinations = {
   ('item1', 'item2', 'item3'): ['property1', 'property3', 'property4'],
   ('item1', 'item2', 'item3'): ['property1', 'property3', 'property5'],
   ('item1', 'item2', 'item3'): ['property1', 'property3', 'property6'],
   ('item1', 'item2', 'item3'): ['property2', 'property3', 'property4'],
   ('item1', 'item2', 'item3'): ['property2', 'property3', 'property5'],
   ('item1', 'item2', 'item3'): ['property2', 'property3', 'property6']
}

Dalam kaedah ini, kami mentakrifkan fungsi pembantu yang dipanggil generate_combinations. Fungsi ini menerima argumen indeks yang mewakili item yang sedang diproses dan senarai gabungan yang mengandungi nilai terkumpul setakat ini. Kami mengulangi nilai yang dikaitkan dengan item semasa dan memanggil fungsi generate_combinations secara rekursif, menghantar indeks yang ditambah dan senarai gabungan yang dikemas kini. Apabila kami sampai ke penghujung senarai kunci, kami menyimpan gabungan yang terhasil dan sifat berkaitannya dalam kamus gabungan.

Analisis kerumitan masa dan ruang

Mari kita menganalisis kerumitan masa dan ruang bagi kedua-dua kaedah ini.

Untuk kaedah 1 menggunakan itertools.product, kerumitan masa boleh dianggarkan sebagai O(NM), dengan N ialah bilangan kekunci dalam kamus input dan M ialah bilangan purata yang dikaitkan dengan setiap kekunci. Ini kerana fungsi itertools.product menjana semua kombinasi yang mungkin dengan melelaran melalui nilai. Kerumitan ruang juga O(NM) kerana kami mencipta kamus baharu untuk menyimpan gabungan.

Dalam kaedah kedua, kaedah rekursif, kerumitan masa boleh dinyatakan sebagai O(N^M), di mana N ialah bilangan kekunci dan M ialah bilangan nilai maksimum yang dikaitkan dengan sebarang kekunci. Ini kerana untuk setiap kunci, fungsi memanggil dirinya secara rekursif untuk memproses setiap nilai yang dikaitkan dengan kunci tersebut. Oleh itu, bilangan panggilan fungsi meningkat secara eksponen dengan bilangan kunci dan nilai. Kerumitan ruang ialah O(N*M) disebabkan oleh panggilan fungsi rekursif dan storan gabungan dalam kamus.

Mengendalikan set data yang besar dan teknik pengoptimuman

Mengendalikan set data yang besar dan mengoptimumkan kod anda menjadi penting apabila berurusan dengan jumlah data yang besar. Memoisasi, yang menyimpan gabungan pengiraan sebelumnya, menghalang pengiraan berlebihan dan meningkatkan prestasi. Pemangkasan melangkau pengiraan yang tidak perlu berdasarkan kekangan untuk mengurangkan overhed pengiraan. Teknik pengoptimuman ini membantu mengurangkan kerumitan masa dan ruang. Selain itu, ia membolehkan kod untuk skala dengan cekap dan mengendalikan set data yang lebih besar. Dengan melaksanakan teknik ini, kod menjadi lebih dioptimumkan, memproses lebih cepat dan meningkatkan kecekapan dalam mencari semua kombinasi item yang mungkin.

Ralat pengendalian dan pengesahan input

Untuk memastikan keteguhan kod anda, adalah penting untuk mempertimbangkan pengendalian ralat dan pengesahan input. Berikut adalah beberapa senario yang perlu ditangani −

• Mengendalikan Kamus Kosong − Jika kamus input kosong, kod harus mengendalikan situasi ini dengan anggun dan mengembalikan output yang sesuai, seperti kamus kosong.

• Kunci Hilang − Jika kamus input tiada kekunci atau sesetengah kekunci tidak mempunyai nilai yang berkaitan, adalah penting untuk mengendalikan kes ini untuk mengelakkan ralat yang tidak dijangka. Anda boleh menambah semakan dan mesej ralat yang sesuai untuk memberitahu pengguna tentang data yang hilang atau tidak lengkap.

• Pengesahan jenis data − Mengesahkan jenis data kamus input untuk memastikan ia mematuhi format yang dijangkakan. Sebagai contoh, anda boleh menyemak sama ada kunci ialah rentetan dan nilainya ialah senarai atau jenis data lain yang sesuai. Ini membantu mengelakkan kemungkinan ralat jenis semasa pelaksanaan kod.

Dengan menambahkan pengendalian ralat dan pengesahan input, anda boleh meningkatkan kebolehpercayaan dan kemesraan pengguna bagi penyelesaian anda.

Kesimpulan

Di sini kami meneroka dua cara berbeza untuk mencari semua kemungkinan gabungan item dalam kamus menggunakan Python. Kaedah pertama bergantung pada fungsi produk dalam modul itertools, yang menjana semua kombinasi dengan cekap dengan mengira produk Cartesian. Kaedah kedua melibatkan fungsi rekursif yang melintasi kamus secara rekursif untuk mengumpul semua kombinasi yang mungkin.

Kedua-dua kaedah memberikan penyelesaian yang cekap kepada masalah, pilihan kaedah yang mana bergantung kepada faktor seperti saiz kamus dan bilangan entri yang terkandung di dalamnya.

Atas ialah kandungan terperinci Cari kamus semua kombinasi item yang mungkin menggunakan Python. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!