アルゴリズム・ランダムな順列

最終更新日: 2012年 1月19日
HomeBack

  1. 説明

  2. JAVAサンプル

パズルゲームなどでランダムな順列が必要な場合があります。 例えば、3 x 3 のマス目に、1〜9までの数字をランダムに配置して、1から順番に押していくゲームのようなケースです。 この場合、1〜9をランダムに並び変えたものが必要になります。 そのような場合に今回のアルゴリズムが使用できます。

これは「改訂C言語によるはじめてのアルゴリズム入門」（河西朝雄著・技術評論社）に載っていたものです。

説明

最初にサイズがnの配列を作成し、中身を入れておきます。 次に最後尾のn番目を除いた、１ 〜 (n-1)番目の中からランダムに１つ選択し、それとn番目の中身を入れ替えます。 次に最後尾から２つ目まで（n、n-1）を除いた、1〜 (n-2)番目の中からランダムに１つ選択し、(n-1)番目 と中身を入れ替えます。 これを繰り返して nから2まで繰り返せばランダムになります。

JAVAサンプル

例. 
    private int[] createRandomNumber(int n) {
        // 配列の中身は 1 ～ n の整数
        int[] ar = new int[n];
        for (int i = 0; i < n; i++) {
            ar[i] = i + 1;
        }

        // 配列の中身の整数をランダムに入れ替える
        Random rand = new Random();
        int r;
        int tmp;
        for (int i = n -1; i > 0; i--) {
            r = rand.nextInt(i);
            tmp = ar[i];
            ar[i] = ar[r];
            ar[r] = tmp;
        }
        return ar;
    }

HomeBack