สร้าง Permutation ทั้งหมดของเซตใน Python

Permutation คือการจัดเรียงสมาชิกของเซตให้เป็นลำดับต่างๆ Python มีหลายวิธีสร้าง permutation

วิธี 1: ใช้ itertools (มาตรฐาน แนะนำ)

import itertools

# Permutation: ลำดับสำคัญ
>>> list(itertools.permutations([1,2,3,4], 2))
[(1, 2), (1, 3), (1, 4), (2, 1), (2, 3), (2, 4), (3, 1), (3, 2), (3, 4), (4, 1), (4, 2), (4, 3)]

# Combination: ลำดับไม่สำคัญ
>>> list(itertools.combinations('1234', 2))
[('1', '2'), ('1', '3'), ('1', '4'), ('2', '3'), ('2', '4'), ('3', '4')]

วิธี 2: Recursive Generator (ไม่สร้างลิสต์กลาง)

def permute(xs, low=0):
    if low + 1 >= len(xs):
        yield xs
    else:
        for p in permute(xs, low + 1):
            yield p
        for i in range(low + 1, len(xs)):
            xs[low], xs[i] = xs[i], xs[low]
            for p in permute(xs, low + 1):
                yield p
            xs[low], xs[i] = xs[i], xs[low]

for p in permute([1, 2, 3]):
    print(p)
# [1, 2, 3]
# [1, 3, 2]
# [2, 1, 3]
# [2, 3, 1]
# [3, 2, 1]
# [3, 1, 2]

วิธี 3: Recursion แบบคลาสสิก (ใช้ copy)

import copy

def perm(prefix, rest):
    for e in rest:
        new_rest = copy.copy(rest)
        new_prefix = copy.copy(prefix)
        new_prefix.append(e)
        new_rest.remove(e)
        if len(new_rest) == 0:
            print(new_prefix + new_rest)
        else:
            perm(new_prefix, new_rest)

perm([], [1, 2, 3])
# [1, 2, 3]
# [1, 3, 2]
# [2, 1, 3]
# [2, 3, 1]
# [3, 1, 2]
# [3, 2, 1]

สรุป

• itertools.permutations: เร็วที่สุด อ่านง่าย ใช้ในงานจริง
• Recursive generator: ประหยัดหน่วยความจำ (yield ทีละอัน) ใช้ได้กับ n ใหญ่
• Recursive แบบคลาสสิก: เข้าใจง่าย แต่ใช้หน่วยความจำมาก (copy ซ้ำ)