Javaで学ぶアルゴリズム -シャッフル（Fisher-Yates）

Fisher-Yatesのシャッフルアルゴリズム

• リストや配列の要素をランダムに並べ替えるための効率的で均等なシャッフルアルゴリズム
• リストの各要素を順番に見て、その要素とそれ以降にあるランダムに選んだ要素を入れ替える
• 各要素が均等な確率で任意の位置に配置され、完全にランダムなシャッフルを実現する

ソートされた配列をランダムな順序に並べ替えるには、シャッフルアルゴリズムを使用するのが一般的です。以下に、配列をランダムに並べ替える方法を示します。これはJavaのコードで、Fisher-Yatesアルゴリズムを用いています。

実行環境

• JUnit 5
• Java 8

テストコード

• 確認観点
  • サイズが同一
  • 要素が同一
  • 要素の順番が同一でない

FisherYatesShuffleTest.java

import static org.hamcrest.CoreMatchers.is;
import static org.hamcrest.CoreMatchers.not;
import static org.hamcrest.MatcherAssert.assertThat;
import static org.hamcrest.Matchers.contains;
import static org.hamcrest.Matchers.containsInAnyOrder;

public class FisherYatesShuffleTest {

	private final List<Integer> list = Arrays.asList(1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29);

	@DisplayName("サイズが同一であることを確認")
	@Test
	void testSameSize() {
		List<Integer> actual = FisherYatesShuffle.shuffle(list);
		assertThat(actual.size(), is(list.size()));
	}

	@DisplayName("要素が同一であることを確認")
	@Test
	void testContainsInAnyOrder() {
		List<Integer> actual = FisherYatesShuffle.shuffle(list);
		assertThat(actual, containsInAnyOrder(list.toArray()));
	}

	@DisplayName("要素の順番が同一でないことを確認")
	@Test
	void testDifferentOrder() {
		List<Integer> actual = FisherYatesShuffle.shuffle(list);
		assertThat(actual, not(contains(list)));
	}

	@DisplayName("要素が存在しない場合はそのまま返すことを確認")
	@Test
	void testEmptyList() {
		List<Integer> list = Arrays.asList();
		List<Integer> actual = FisherYatesShuffle.shuffle(list);
		assertThat(actual, is(list));
	}

	@DisplayName("リストがnullの場合はNPEがスローされることを確認")
	@Test
	void testThrowsNullPointerException() {
		assertThrows(NullPointerException.class, () -> {
			FisherYatesShuffle.shuffle(null);
		});
	}

シャッフルアルゴリズム（Fisher-Yates）

FisherYatesShuffle.java

import java.util.Random;

public class FisherYatesShuffle {

	public static List<Integer> shuffle(List<Integer> list) {
		Random random = new Random();
		for (int i = list.size() - 1; i > 0; i--) {
			int index = random.nextInt(i + 1);
			// リストの要素をスワップ
			Integer temp = list.get(index);
			list.set(index, list.get(i));
			list.set(i, temp);
		}
		return list;
	}
}

Collections.shuffle を使えば2行

public class FisherYatesShuffle {

	public static List<Integer> shuffle(List<Integer> list) {
		Collections.shuffle(list);
		return list;
	}
}

参考