ฉันมีรายการองค์ประกอบ ซึ่งฉันต้องการกำหนดชุดค่าผสมที่เป็นไปได้ทั้งหมดที่สามารถจัดเรียงได้ - รักษาลำดับ - เพื่อไปถึงกลุ่ม 'n'
ตัวอย่างเช่น หากฉันมีรายการเรียงลำดับของ A, B, C, D, E และต้องการเพียง 2 กลุ่ม วิธีแก้ปัญหาทั้งสี่จะเป็นดังนี้
ABCD, E
ABC, DE
AB, CDE
A, BCDE
ตอนนี้ ด้วยความช่วยเหลือจาก โพสต์ StackOverflow อื่น ฉันจึงได้โซลูชันแบบ brute-force ที่ใช้งานได้ ซึ่งจะคำนวณชุดค่าผสมที่เป็นไปได้ทั้งหมด ของการจัดกลุ่มที่เป็นไปได้ทั้งหมด ซึ่งฉันเพียงแยกกรณีที่ตรงกับจำนวนการจัดกลุ่มเป้าหมายของฉัน
สำหรับองค์ประกอบในจำนวนที่สมเหตุสมผล นี่เป็นเรื่องปกติ แต่เมื่อฉันขยายจำนวนองค์ประกอบ จำนวนชุดค่าผสมจะเพิ่มขึ้นอย่างรวดเร็วมาก และฉันสงสัยว่าอาจมีวิธีที่ชาญฉลาดในการจำกัดโซลูชันที่คำนวณไว้เฉพาะที่ตรงตามเงื่อนไขหรือไม่ หมายเลขกลุ่มเป้าหมายของฉัน?
รหัสจนถึงตอนนี้มีดังนี้;
import itertools
import string
import collections
def generate_combination(source, comb):
res = []
for x, action in zip(source,comb + (0,)):
res.append(x)
if action == 0:
yield "".join(res)
res = []
#Create a list of first 20 letters of the alphabet
seq = list(string.ascii_uppercase[0:20])
seq
['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T']
#Generate all possible combinations
combinations = [list(generate_combination(seq,c)) for c in itertools.product((0,1), repeat=len(seq)-1)]
len(combinations)
524288
#Create a list that counts the number of groups in each solution,
#and counter to allow easy query
group_counts = [len(i) for i in combinations]
count_dic = collections.Counter(group_counts)
count_dic[1], count_dic[2], count_dic[3], count_dic[4], count_dic[5], count_dic[6]
(1, 19, 171, 969, 3876, 11628)
อย่างที่คุณเห็น ในขณะที่คำนวณชุดค่าผสมมากกว่าครึ่งล้านชุด หากฉันต้องการเพียงชุดค่าผสมที่มีความยาว = 5 ก็คำนวณได้เพียง 3,876 ชุดเท่านั้น
มีข้อเสนอแนะอะไรบ้าง?