next permutation

目的

与えられた順列に対して、辞書順で次の順列をreturn。

計算量

ならし$O(1)$

使い方

boolean nextPermutation(int[] ord)
順列ordを辞書順で次の順列に書き換える。辞書順で次の順列が存在するときはtrue,存在しないときはfalseをreturn。

ソースコード

boolean nextPermutation(int[] ord) {
    int n = ord.length;
    int i = n - 1;
    while (i - 1 >= 0 && ord[i - 1] > ord[i]) {
	--i;
    }

    if (i == 0)
	return false;
    int j = i;

    while (j + 1 < n && ord[i - 1] < ord[j + 1]) {
	++j;
    }
    int tmp = ord[i - 1];
    ord[i - 1] = ord[j];
    ord[j] = tmp;
    int s = i;
    int t = n - 1;
    while (t - s > 0) {
	tmp = ord[t];
	ord[t] = ord[s];
	ord[s] = tmp;
	++s;
	--t;
    }

    return true;

}

Verified

yukicoder No.3024 等式