重複ありの数列でも順列を返す関数
自分用のメモ
結局ネットにあったコードを使ったら出来たので、今後のために載せます。
参照URL:http://d.hatena.ne.jp/tomerun/20081203/1228321480
import java.util.Arrays; import java.util.Scanner; public class Main { 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(); } Arrays.sort(a); do { for(int i = 0 ; i < n ; i++) { System.out.print(a[i]); } System.out.println(); } while(nextPermutation(a)); } // nextPermutation 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); } }
今の段階では内容を全くと行っていいほど理解していませんが、いつか理解していきたい(遠い目)
深さ優先探索でも実装できればしていきたいなあ。