重複なし乱数

最近手を動かしていないので，寝る前に簡単なコーディングをしたくなる．どう書く？orgを探してすぐに書けそうなものを選んだ．

• どう書く？org 重複無し乱数

実はアルゴリズムを全然知らない自分は，昔ビンゴゲームをつくるときにオブジェクト向で実装することでこれを実現していた．Listからランダムに選択し，\
選ばれた要素を取り出してリスト長を縮める，という方法．
Cで実装するにはどうしたらいいだろう，と思って考えていたら，素直な解が思いついた．

1からNの整数が入っている配列から，ランダムに選択されたk番目の数とN-1番目との数を交換して，N-1の大きさの配列と考えて同じ動作を計N回繰り返す，と\
いうもの．
Cで，と言っておきながら，Cの乱数が嫌いなのでJavaで書く．

import java.util.*;

class exrandom{
    public static void main(String args[]){

        int[] randomlist = getRandomList(10);

        /* print result */
        for(int i = 0; i < randomlist.length; i++){

            System.out.print(randomlist[i]);

            if(i < randomlist.length - 1){
                System.out.print(",");
            }else{
                System.out.println();
            }
        }
    }


    /* from 1 to N */
    public static int[] getRandomList(int N){

        int[] numberlist = new int[N];
        int[] randomlist = new int[N];

        for(int i = 0; i < N; i++){
            numberlist[i] = i + 1;
        }

        int restsize = N;
        for(int i = 0; i < N; i++){

            int choice = (int)(Math.random() * restsize);
            randomlist[i] = numberlist[choice];

            int tmp = numberlist[choice];
            numberlist[choice] = numberlist[restsize - 1];
            numberlist[restsize - 1] = tmp;

            restsize--;
        }

        return randomlist;
    }
}

ちょっと冗長な部分はあるけれど，こんなものでしょう．新B4の演習によいかもしんない．
投稿された回答を眺めてみると，あったあった．線形時間o(N)なので，これが一番速いんじゃないかなぁ，と思っていたりする．
ランダムソート，という名前を初めて知る．sortのcmpをランダムで1,-1を返すというもの．その発想はなかったわ．

やっぱりアルゴリズムは大事ですなぁ．