山傘のプログラミング勉強日記

プログラミングに関する日記とどうでもよい雑記からなるブログです。

重複のない順列を列挙する

順列の列挙

要素に重複がない場合、順列の組み合わせは  n! 通りあります。階乗は発散する速度が大きいので、 n = 9 くらいまでが問題を解く上での限度だと思います。

ビット列の列挙すら完璧に理解していないので、順列の列挙のプログラムを作成できるわけもなかったです。なので、調べることに・・・。

参考にしたサイトは、

www.geocities.jp

です。

数字の順列を列挙

public class Test2 {
    public static void main(String[] args) {
        int n = 3;
        int []a = new int[n];
        for(int i = 0; i < n; i++) {
            a[i] = i;
        }

        perm(0, a, new boolean [n + 1]);
    }

    // 1~nまでの順列を生成
    static void perm(int n, int[] a, boolean[] flag) {
        if(n == a.length) {
            disp(a);
            return;
        }
        for(int i = 1; i <= a.length; i++) {
            if(flag[i]) continue;
            a[n] = i;
            flag[i] = true;
            perm(n + 1, a, flag);
            flag[i] = false;
        }

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

f:id:yamakasa3:20180705232748p:plain

感想

プログラムのしていることは何となく理解しているんですが、独力では書けないですね。

一応、ビット列と順列の列挙のプログラムを得たので、手持ちのカードが増えた感じです。良かった。