順列組み合わせ

date: 2021-04-02 excerpt: 順列組み合わせ(permutaion)について

tag: algorithm math 順列組み合わせ permutaion integer

順列組み合わせについて

14世紀にNarayana Panditaに発見された方法

手順
- Find the largest index k such that vec[k] < vec[k + 1]. If no such index exists, just reverse vec and done.
- Find the largest index l > k such that vec[k] < vec[l].
- Swap vec[k] and vec[l].
- Reverse the sub-array vec[k + 1:].
参考
- https://leetcode.com/problems/next-permutation/discuss/13867/C++-from-Wikipedia

C++での実装例

template <typename T>
void nextPermutation(vector<T>& vec) {
    int n = vec.size(), k, l;
    for (k = n - 2; k >= 0; k--) {
        if (vec[k] < vec[k + 1]) {
            break;
        }
    }
    if (k < 0) {
        std::reverse(vec.begin(), vec.end());
    } else {
        for (l = n - 1; l > k; l--) {
            if (vec[l] > vec[k]) {
                break;
            }
        }
        std::swap(vec[k], vec[l]);
        std::reverse(vec.begin() + k + 1, vec.end());
    }
}

int main() {
    vector<int> vec{1,2,3,4,5};
    print_it(vec);
    for(int i=0; i<10; i++) {
        nextPermutation(vec);
        print_it(vec);
    }
    /*
    1; 2; 3; 4; 5;
    1; 2; 3; 5; 4;
    1; 2; 4; 3; 5;
    1; 2; 4; 5; 3;
    1; 2; 5; 3; 4;
    1; 2; 5; 4; 3;
    1; 3; 2; 4; 5;
    1; 3; 2; 5; 4;
    1; 3; 4; 2; 5;
    1; 3; 4; 5; 2;
    1; 3; 5; 2; 4;
    */
}

pythonでの実装例

def nextPermutation(vec):
    n = len(vec);
    k = 0
    l = 0
    for k in range(n-2, -1, -1):
        if (vec[k] < vec[k + 1]):
            break
    if k < 0:
        vec.reverse()
    else:
        for l in range(n-1, k, -1):
            if vec[l] > vec[k]:
                break
        vec[l], vec[k] = vec[k], vec[l]
        vec[:] = vec[:k+1] + vec[k+1:][::-1]

再帰を用いた実装法

def permutation(arr):
    if len(arr) <= 1:
        return [arr]
    lst = []
    for i in range(len(arr)):
        m = arr[i]
        # i番目のデータ以外のものを再度permutationを計算
        remarr = arr[:i] + arr[i+1:]
        for p in permutation(remarr):
            lst.append([m] + p)
    return lst


arr = list("123")
for p in permutation(arr):
    print(p)

yieldを用いた実装法

from typing import Optional, List

def permute(a: List, l: int, r: int) -> Optional[List]:
    if l==r:
        yield a
    else:
        for i in range(l,r+1):
            a[l], a[i] = a[i], a[l]
            yield from permute(a, l+1, r)
            a[l], a[i] = a[i], a[l] # もとに戻す
        None

a = list(range(10))
n = len(a)
gen = permute(a, 0, n-1)
print(next(gen)) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
print(next(gen)) # [0, 1, 2, 3, 4, 5, 6, 7, 9, 8]
print(next(gen)) # [0, 1, 2, 3, 4, 5, 6, 8, 7, 9]

google colab

ライブラリの速度とスクラッチによる速度の差

圧倒的にライブラリのほうが速度が早い

1 loop, best of 5: 231 ms per loop

%%timeit
from itertools import permutations
a = list(range(10))
for i in permutations(a):
    pass

1 loop, best of 5: 5.54 s per loop

%%timeit
a = list(range(10))
n = len(a)
for i in permute(a, 0, n-1):
    pass