はじめに
久しくプログラミング業務から離れているため、ちょっとしたアルゴリズムに触れて頭の体操をしようと思い立ち、Fisher-YatesのシャッフルをJavaで実装してみました。
アルゴリズムそのものは、Wikipediaに記載されているものを利用しています。
作成したコード
- 以下のコードは、Wikipediaの改良されたアルゴリズムをJavaのコードとして書き起こしたものになります。
- コード中のコメントは、Wikipediaに記載されているアルゴリズムと対応（一致）しています。
- int型の配列をStreamにした後、そのままmapメソッドでStringにしようとするとエラーになりました。
- こちらのサイトによると、int型配列をStreamにするとIntStreamになるものの、IntStreamではint型しか扱えないため、mapオブジェクトでString型に変換するとエラーが出てしまう...というのがエラーの理由だそうです。
- そのため、mapToObjメソッドで各要素をString型にしています。
FisherYatesRefined.java
import java.util.Arrays;
import java.util.Random;
import java.util.stream.Collectors;
/**
* フィッシャー・イェーツのシャッフルの改良版
* @author NKOJIMA
*
*/
public class FisherYatesRefined {
/**
* 要素数がnの配列aryをシャッフルする(添字は0からn-1):
* @param args
*/
public static void main(String[] args) {
int[] ary = {0,1,2,3,4,5,6,7,8,9};
System.out.println("シャッフル前");
System.out.println(Arrays.stream(ary).mapToObj(elem -> String.valueOf(elem)).collect(Collectors.joining(",")));
int n = ary.length;
Random rnd = new Random();
// iをn-1から1まで減少させながら、以下を実行する
for (int i=n-1; i>=1; i--) {
// jに0以上i以下のランダムな整数を代入する
int j = rnd.nextInt(i);
// a[j]とa[i]を交換する
int tmp = ary[i];
ary[i] = ary[j];
ary[j] = tmp;
}
System.out.println("シャッフル後");
System.out.println(Arrays.stream(ary).mapToObj(elem -> String.valueOf(elem)).collect(Collectors.joining(",")));
}
}
実行結果
- 「シャッフル前」の結果は常に同じですが、「シャッフル後」の結果の並び順はシャッフルされていることが分かります。
実行結果
シャッフル前
0,1,2,3,4,5,6,7,8,9
シャッフル後
8,7,3,0,2,4,9,5,6,1