Python: สร้าง Permutation ของสตริงด้วย itertools.permutations

โมดูล itertools มีฟังก์ชัน permutations() สำหรับสร้าง Permutation (เรียงสับเปลี่ยน) ของลำดับข้อมูล เช่น สตริง, ลิสต์, ทูเพิล โดยคืนค่าเป็น Iterator ของ Tuples

ไวยากรณ์

itertools.permutations(iterable, r=None)
# r = ความยาวของ permutation (default = ความยาวเต็ม)

ตัวอย่างพื้นฐาน: สตริง "XYZ"

import itertools

string = "XYZ"

# ได้ Iterator -> แปลงเป็น List
perm_tuples = list(itertools.permutations(string))
print("Permutations as tuples:")
print(perm_tuples)
# [('X', 'Y', 'Z'), ('X', 'Z', 'Y'), ('Y', 'X', 'Z'), ('Y', 'Z', 'X'), ('Z', 'X', 'Y'), ('Z', 'Y', 'X')]

# แปลง Tuple -> String
print("\nPermutations as strings:")
for tup in perm_tuples:
    print(''.join(tup))
# XYZ
# XZY
# YXZ
# YZX
# ZXY
# ZYX

จำนวน Permutation

จำนวน Permutation ของ n องค์ประกแบบ = n! (Factorial)

import math

n = len("XYZ")
print(f"Length: {n}, Permutations: {math.factorial(n)}")  # 3! = 6

# สำหรับ String ยาว 10 ตัว -> 10! = 3,628,800 permutations (เยอะมาก!)
# ควรระวัง Memory/Performance

ระบุความยาว r (Partial Permutation)

# Permutation ความยาว 2 จาก "ABCD"
perms_r2 = list(itertools.permutations("ABCD", 2))
print(perms_r2)
# [('A','B'), ('A','C'), ('A','D'), ('B','A'), ('B','C'), ('B','D'), ('C','A'), ('C','B'), ('C','D'), ('D','A'), ('D','B'), ('D','C')]
# จำนวน = P(4,2) = 4!/(4-2)! = 12

การประยุกต์ใช้งานจริง

1. หา Permutation ที่เป็นคำอังกฤษที่ถูกต้อง (Anagram Solver)

import itertools

def find_valid_words(letters, dictionary_set, min_length=3):
    """หาคำใน Dictionary ที่ประกอบจาก letters ได้"""
    valid = set()
    for r in range(min_length, len(letters) + 1):
        for perm in itertools.permutations(letters, r):
            word = ''.join(perm)
            if word in dictionary_set:
                valid.add(word)
    return valid

# ตัวอย่าง Dictionary เล็ก
dictionary = {"cat", "act", "tac", "at", "ta", "dog", "god", "go", "car", "arc"}

print(find_valid_words("cat", dictionary))    # {'cat', 'act', 'tac', 'at', 'ta'}
print(find_valid_words("dog", dictionary))    # {'dog', 'god', 'go'}
print(find_valid_words("car", dictionary))    # {'car', 'arc'}

2. Traveling Salesman Problem (Brute Force - Small n)

import itertools

# Cities และระยะทาง
cities = ["A", "B", "C", "D"]
distances = {
    ("A","B"): 10, ("B","A"): 10,
    ("A","C"): 15, ("C","A"): 15,
    ("A","D"): 20, ("D","A"): 20,
    ("B","C"): 35, ("C","B"): 35,
    ("B","D"): 25, ("D","B"): 25,
    ("C","D"): 30, ("D","C"): 30,
}

def route_distance(route):
    return sum(distances[(route[i], route[i+1])] for i in range(len(route)-1))

# ลองทุก Permutation (เริ่มและจบที่ A)
best_route = None
best_dist = float('inf')

for perm in itertools.permutations(cities[1:]):  # Fix A as start
    route = ("A",) + perm + ("A",)
    dist = route_distance(route)
    if dist < best_dist:
        best_dist = dist
        best_route = route

print(f"Best Route: {' -> '.join(best_route)}")
print(f"Distance: {best_dist}")

3. Password/Pattern Generation

import itertools

# สร้าง Pattern ทั้งหมดจากชุดตัวอักษร
chars = "AB12"
for r in range(1, 4):
    for perm in itertools.permutations(chars, r):
        print(''.join(perm), end=' ')
# A B 1 2 AB A1 A2 BA B1 B2 1A 1B 12 2A 2B 21 AB1 AB2 A1B A12 A2B A21 BA1 BA2 B1A B12 B2A B21 1AB 1A2 1BA 1B2 12A 12B 2AB 2A1 2BA 2B1 21A 21B

Permutation vs Combination vs Product

from itertools import permutations, combinations, product

items = "ABC"

print("Permutations (2):", [''.join(p) for p in permutations(items, 2)])
# ['AB', 'AC', 'BA', 'BC', 'CA', 'CB']

print("Combinations (2):", [''.join(c) for c in combinations(items, 2)])
# ['AB', 'AC', 'BC']

print("Product (2):", [''.join(p) for p in product(items, repeat=2)])
# ['AA', 'AB', 'AC', 'BA', 'BB', 'BC', 'CA', 'CB', 'CC']

สรุป

• itertools.permutations สร้าง Permutation ได้อย่างมีประสิทธิภาพ (Lazy Iterator)
• จำนวน Permutation = n! / (n-r)! โตขึ้นเร็วมาก (Factorial Growth)
• ใช้ ''.join(tup) แปลง Tuple -> String
• เหมาะสำหรับ: Anagrams, Brute Force Search, Scheduling, Test Case Generation
• ระวัง Memory: อย่าแปลงเป็น List หาก n ใหญ่ ให้ Iterate ทีละตัว