Python: สร้าง Permutation แบบมีการซ้ำ (Permutation with Repetition)

บทนำ

โค้ดตัวอย่างสาธิตการสร้าง permutation แบบมีการซ้ำ (repetition allowed) ของตัวอักษรในสตริง ความยาวของ permutation เท่ากับความยาวสตริงต้นทาง

อัลกอริทึม: Recursive Backtracking

สร้างทุกความเป็นไปได้โดยวางตัวอักษรแต่ละตัวในแต่ละตำแหน่ง แบบ recursive

โค้ดต้นฉบับ


def to_string(my_list):
    return ''.join(my_list)

def lex_recurrence(my_string, my_data, last_val, index_val):
    length = len(my_string)
    for i in range(length):
        my_data[index_val] = my_string[i]
        if index_val == last_val:
            print(to_string(my_data))
        else:
            lex_recurrence(my_string, my_data, last_val, index_val + 1)

def all_lex(my_string):
    length = len(my_string)
    my_data = [""] * (length + 1)
    my_string = sorted(my_string)
    lex_recurrence(my_string, my_data, length - 1, 0)

my_string = "MQ"
print(f"สตริง: {my_string}")
print(f"Permutations with repetition:")
all_lex(my_string)

ผลลัพธ์


สตริง: MQ
Permutations with repetition:
MM
MQ
QM
QQ

วิธีที่ง่ายกว่า: ใช้ itertools.product


from itertools import product

def permutations_with_repetition(s):
    """Permutation with repetition: n^r patterns"""
    return [''.join(p) for p in product(sorted(s), repeat=len(s))]

print(permutations_with_repetition("MQ"))
# ['MM', 'MQ', 'QM', 'QQ']

print(permutations_with_repetition("ABC"))
# ['AAA', 'AAB', 'AAC', 'ABA', 'ABB', 'ABC', 'ACA', 'ACB', 'ACC',
#  'BAA', 'BAB', 'BAC', 'BBA', 'BBB', 'BBC', 'BCA', 'BCB', 'BCC',
#  'CAA', 'CAB', 'CAC', 'CBA', 'CBB', 'CBC', 'CCA', 'CCB', 'CCC']

เปรียบเทียบ: Permutation แบบต่างๆ

ประเภท	ฟังก์ชัน	จำนวน	ตัวอย่าง "AB"
Permutation (ไม่ซ้ำ)	itertools.permutations	n!	AB, BA
Permutation with repetition	itertools.product	n^n	AA, AB, BA, BB
Combination (ไม่ซ้ำ)	itertools.combinations	C(n,r)	AB
Combination with repetition	itertools.combinations_with_replacement	C(n+r-1,r)	AA, AB, BB

กรณีใช้งานจริง

สร้างรหัสผ่าน/ปักหมุดทุกความเป็นไปได้
Brute force search
Game theory: กลยุทธ์ทั้งหมด
ทดสอบระบบ: generate test cases

ข้อควรระวัง

จำนวนเพิ่มขึ้นแบบ exponential: n^n (สตริงยาว 10 ตัวอักษรต่างกัน = 10^10 = 10 billion)
หน่วยความจำ: ใช้ generator แทน list สำหรับข้อมูลใหญ่
โค้ดต้นฉบับมี bug: my_data = [""] * (length + 1) ควรเป็น length ไม่ใช่ length+1

Generator Version (ประหยัดหน่วยความจำ)


def perm_repetition_gen(s):
    """Generator version - ไม่เก็บทั้งหมดในหน่วยความจำ"""
    for p in product(sorted(s), repeat=len(s)):
        yield ''.join(p)

# ใช้งาน
for i, perm in enumerate(perm_repetition_gen("ABCD")):
    if i >= 5:
        break
    print(perm)
# AAAA
# AAAB
# AAAC
# AAAD
# AABA

สรุป

ใช้ itertools.product(sorted(s), repeat=len(s)) สำหรับ permutation with repetition โค้ดสั้น เร็ว และถูกต้อง โค้ด recursive ต้นฉบับทำงานได้แต่ซับซ้อนและมี off-by-one bug