next_permutation
(expansion/misc/next_permutation.py)

View this file on GitHub
Last update: 2023-06-18 15:21:26+09:00

概要

C++ にある next_permutation を真似して作ったやつです．

使い方

next_permutation(P)

P を与えた際に，P の並び替えのうち，辞書順で P の次に大きいものに変更して True を返します．．存在しない場合，False を返します．破壊的変更を行います．

prev_permutation(P)

P を与えた際に，P の並び替えのうち，辞書順で P の次に小さいものに変更して True を返します．．存在しない場合，False を返します．破壊的変更を行います．

all_permutations(P)

for Q in all_permutations(P)

とすると，P の並び替えのうち，P + P 寄りも辞書順で後ろのものを全て列挙します．Q に変更を加えると P 側にも変更が加わるので注意してください．回る順番は辞書順です．

rev_all_permutations(P)

all_permutations の逆順です．

Code

def next_permutation(P):
    n = len(P)
    for i in range(n - 2, -1, -1):
        if P[i] < P[i + 1]:
            l = i + 1
            r = n - 1
            while r > l:
                P[l], P[r] = P[r], P[l]
                l += 1
                r -= 1
            for j in range(i + 1, n):
                if P[i] < P[j]:
                    P[i], P[j] = P[j], P[i]
                    return True
    return False


def all_permutations(P):
    # 全列挙したい場合はソートしてある状態で渡す
    yield P
    while next_permutation(P):
        yield P


def prev_permutation(P):
    n = len(P)
    for i in range(n - 2, -1, -1):
        if P[i] > P[i + 1]:
            l = i + 1
            r = n - 1
            while r > l:
                P[l], P[r] = P[r], P[l]
                l += 1
                r -= 1
            for j in range(i + 1, n):
                if P[i] > P[j]:
                    P[i], P[j] = P[j], P[i]
                    return True
    return False


def rev_all_permutations(P):
    # 全列挙したい場合は逆順ソートしてある状態で渡す
    yield P
    while prev_permutation(P):
        yield P

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.11.4/x64/lib/python3.11/site-packages/onlinejudge_verify/documentation/build.py", line 81, in _render_source_code_stat
    bundled_code = language.bundle(
                   ^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.11.4/x64/lib/python3.11/site-packages/onlinejudge_verify/languages/python.py", line 108, in bundle
    raise NotImplementedError
NotImplementedError

next_permutation (expansion/misc/next_permutation.py)

概要