Javaでnext_permutation

というわけで、Javaでnext_permutation関数を作ってみました。

  // 配列版
  public static boolean nextPermutation(int[] a) {
    for (int i = a.length - 1; i > 0; --i) {
      if (a[i - 1] < a[i]) {
        int swapIndex = find(a[i - 1], a, i, a.length - 1);
        int temp = a[swapIndex];
        a[swapIndex] = a[i - 1];
        a[i - 1] = temp;
        Arrays.sort(a, i, a.length);
        return true;
      }
    }
    return false;
  }

  // destより大きい要素の中で最小のもののインデックスを二分探索で探す
  private static int find(int dest, int[] a, int s, int e) {
    if (s == e) {
      return s;
    }
    int m = (s + e + 1) / 2;
    return a[m] <= dest ? find(dest, a, s, m - 1) : find(dest, a, m, e);
  }


  // List版
  public static <T extends Comparable<? super T>> boolean nextPermutation(
      List<T> l) {
    int size = l.size();
    for (int i = size - 1; i > 0; --i) {
      if (l.get(i - 1).compareTo(l.get(i)) < 0) {
        int swapIndex = find(l.get(i - 1), l, i, size - 1);
        Collections.swap(l, i - 1, swapIndex);
        Collections.sort(l.subList(i, size));
        return true;
      }
    }
    return false;
  }

  private static <T extends Comparable<? super T>> int find(T dest,
      List<T> a, int s, int e) {
    if (s == e) {
      return s;
    }
    int m = (s + e + 1) / 2;
    return a.get(m).compareTo(dest) <= 0 ? find(dest, a, s, m - 1)
                                         : find(dest, a, m, e);
  }

互いに異なる要素が昇順にソートされた初期状態からnextPermutationを繰り返し実行して、全てが降順にソートされるまでの実行時間をごく簡単に計測するとこんな感じでした。使った整数は 1〜N です。

10要素int配列	11要素int配列	10要素ArrayList	10要素LinkedList
0.25秒	2.7秒	4.4秒	4.6秒

（Athlon64×2 4200+、TopCoderサーバーより1割遅い程度）

これを見ると、SRMでは配列で10要素が限界ですね。コレクション使ってやることじゃないわな。
このくらいのサイズしか扱えないのだったら、わざわざ二分探索せずとも線形探索で十分そうだ。

もっと効率いい方法あるんだろうか。C++のSTLでの実装を見ればいいのか？