Java:次の順列を作り、まだ次があるかをbooleanで返す関数(nextPermutation)

Javaの標準ライブラリには、C++の std::next_permutation のような「並びを辞書順で次に更新し、次があれば boolean を返す」関数が用意されていません。

この記事では、その場更新・O(n)で動く実装（pivot探索→後継探索→swap→末尾区間(suffix)反転）と使い方を紹介します。

※配列は破壊的更新されます。全列挙する場合は Arrays.sort で最小順から始めて do { … } while (nextPermutation(a)); としてください。

実装

import java.util.Arrays;

public class Main {
    static boolean nextPermutation(int[] a) {
        int n = a.length;
        int i = n - 2;
        while (i >= 0 && a[i] >= a[i + 1]) i--;
        if (i < 0) { reverse(a, 0, n-1); return false; }
        int j = n - 1;
        while (a[j] <= a[i]) j--;
        swap(a, i, j);
        reverse(a, i + 1, n - 1);
        return true;
    }
    static void swap(int[] a, int i, int j){ int t=a[i]; a[i]=a[j]; a[j]=t; }
    static void reverse(int[] a, int l, int r){ while (l < r) swap(a, l++, r--); }

    static void print(int[] a){
        for (int i = 0; i < a.length; i++) {
            if (i>0) System.out.print(" ");
            System.out.print(a[i]);
        }
        System.out.println();
    }

    public static void main(String[] args){
        int[] array = {1, 2, 2, 3};       
        Arrays.sort(array);          
        do {
            print(array);
        } while (nextPermutation(array));
    }
}

実行結果

1 2 2 3
1 2 3 2
1 3 2 2
2 1 2 3
2 1 3 2
2 2 1 3
2 2 3 1
2 3 1 2
2 3 2 1
3 1 2 2
3 2 1 2
3 2 2 1

アルゴリズムの簡単な解説

1.	右から見て初めて上がる所＝pivot i を探す
2.	末尾から a[i] より大きい最小の要素＝後継 j を探す
3.	swap(i, j) → i+1..末尾の“末尾区間(suffix)”を反転（いま降順なので反転で昇順になる）
※これで「次の辞書順」になります（重複要素対応は >= / <= が肝）。
※長さ0/1の配列は常に false を返します（実装上その通り）。

計算量

• 1回の nextPermutation は O(n)（末尾からの探索と反転）。
• 全列挙は O(n! × n)。

例題

ABC425B

実装例

import java.util.*;

public class Main {
    static boolean nextPermutation(int[] a) {
        int n = a.length;
        int i = n - 2;
        while (i >= 0 && a[i] >= a[i+1]) i--;    
        if (i < 0) { reverse(a, 0, n-1); return false; }
        int j = n - 1;
        while (a[j] <= a[i]) j--;
        swap(a, i, j);
        reverse(a, i+1, n-1);
        return true;
    }
    static void swap(int[] a, int i, int j){ int t=a[i]; a[i]=a[j]; a[j]=t; }
    static void reverse(int[] a, int l, int r){ while(l<r) swap(a,l++,r--); }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] A = new int[N];
        for (int i = 0; i < N; i++) A[i] = sc.nextInt();

        int[] P = new int[N];
        for (int i = 0; i < N; i++) P[i] = i + 1; 

        do {
            boolean ok = true;
            for (int i = 0; i < N; i++) {
                if (A[i] != -1 && A[i] != P[i]) { ok = false; break; }
            }
            if (ok) {
                System.out.println("Yes");
                for (int i = 0; i < N; i++) {
                    if (i>0) System.out.print(" ");
                    System.out.print(P[i]);
                }
                System.out.println();
                return; 
            }
        } while (nextPermutation(P)); 

        System.out.println("No");
    }
}