Pythonで理解する蟻本「2-1 特殊な状態の列挙」(p.39)

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の
「2-1 特殊な状態の列挙」(p.39)
のコードをPythonで書き直したものとなっています。

PythonとC++の違い

C++ではnext_permutationという関数を使って順列を生成していますが、Pythonではitertoolsモジュールのpermutations関数を使うことで順列を要素としたイテレータを生成できます。

Pythonで組み合わせを扱いたいときは、とりあえずitertoolsを使うことを考えてみるとよいでしょう。

コード

MAX_N = 10 ** 8
used = [0] * MAX_N
perm = [0] * MAX_N

# {0,1,2,3,4, ... ,n - 1}の並び替えn!通りを生成する

def permutation1(pos, n):
    if pos == n:
        '''
        permに対する操作
        '''
        return

    # permのpos番目を0～n-1のどれにするかのループ
    for i in range(n):
        if not used[i]:
            perm[pos] = i
            # iを使ったのでフラグをTrueにしておく
            used[i] = True
            permutation1(pos + 1, n)
            # 戻ってきたらフラグを戻しておく
            used[i] = False
    return

from itertools import permutations

def permutation2(n):
    perm2 = list(range(n))
    for tmp_perm in permutations(perm2, n):
        '''
        tmp_permに対する操作
        '''
    return

具体的な実行例も下に載せておきます。

実行例

サンプルコード

MAX_N = 10 ** 8
used = [0] * MAX_N
perm = [0] * MAX_N

# {0,1,2,3,4, ... ,n - 1}の並び替えn!通りを生成する

def permutation1(pos, n):
    if pos == n:
        print(perm[:n])
        return

    # permのpos番目を0～n-1のどれにするかのループ
    for i in range(n):
        if not used[i]:
            perm[pos] = i
            # iを使ったのでフラグをTrueにしておく
            used[i] = True
            permutation1(pos + 1, n)
            # 戻ってきたらフラグを戻しておく
            used[i] = False
    return

from itertools import permutations

def permutation2(n):
    perm2 = list(range(n))
    for tmp_perm in permutations(perm2, n):
        print(tmp_perm)
    return

permutation1(0, 3)
print()
permutation2(3)

実行結果

[0, 1, 2]
[0, 2, 1]
[1, 0, 2]
[1, 2, 0]
[2, 0, 1]
[2, 1, 0]

(0, 1, 2)
(0, 2, 1)
(1, 0, 2)
(1, 2, 0)
(2, 0, 1)
(2, 1, 0)