[Java] 対称群と置換のユーティリティ
================================================================================
15 ゲームの不可能性に関して、その 15 ゲームをあらわす置換の符号が 1 の場合は、
ゲームが解けるが、-1 の場合は解けない。
これについて、その符号を取り出してみるユーティリティを作った。
これだけではなく、関数としては、次のものがある。
---
static int[] getPermutation(int size)
指定された要素数の置換を取得する。
static boolean isPermutation(int[] permutation)
指定された配列が置換になっているかどうかを確認する。
static int sgn(int[] permutation)
指定された置換の符号を取得する。
---
■ 参考 URL
１５ゲームの不可能性の評価
http://www004.upp.so-net.ne.jp/s_honma/game15.htm
「対称群と15ゲーム」スライド
http://ocw.tsukuba.ac.jp/25a0-v-1-65705b66985e/65705b66727952258b1b7fa9i/300c5bfe79f07fa430681530fc30e0300d30b930e930a4-pdf30d530a130a430eb
■ ソース
コードの内容については、中のコメントを参考。とくに、ここでは補足しない。
また、今後(気が向けば)関数を追加していく。
□ SymmetricGroupUtil.java
---
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
/**
* 対称群関係のユーティリティ。
*
* @author marunomaruno
* @version 1.0, 2012-01-06
*/
public class SymmetricGroupUtil {
private SymmetricGroupUtil() {
super();
}
/**
* 指定された置換の符号を取得する。
*
* @param permutation
* 置換を意味する配列
* @return 置換の符号
*/
public static int sgn(int[] permutation) {
System.out.printf("a=%s; [", Arrays.toString(permutation));
// 置換群かどうかを確認する
if (!isPermutation(permutation)) {
throw new IllegalArgumentException(
"指定された配列は、置換群になっていません。");
}
// ゼロ相対の添字と合わせるので、値を1引いたものにする
int[] sigma = new int[permutation.length];
for (int i = 0; i < permutation.length; i++) {
sigma[i] = permutation[i] - 1;
}
// 転倒数を数える
int count = 0;
for (int i = 0; i < sigma.length; i++) {
// すでに循環置換として抽出したものは除く
if (sigma[i] < 0) {
continue;
}
// 巡回置換の(長さ-1)を加える
count += (length(sigma, i) - 1);
}
System.out.printf("]; count=%d%n", count);
return (count % 2 == 0) ? 1 : -1; // 本来は、(int) Math.pow(-1, count);
}
/**
* 指定された置換の、指定された添字からの巡回置換の長さを取得する。
* なお、引数の置換は、中身が変更される可能性がある。
*
* @param permutation
* 置換
* @param from
* 添字
* @return 指定された置換の、指定された添字からの巡回置換の長さ
*/
private static int length(int[] permutation, int from) {
int length = 0;
System.out.print(String.format("[%d", permutation[from] + 1));
int i = permutation[from];
while (permutation[from] >= 0 && i != from) {
System.out.print(String.format(", %d", permutation[i] + 1));
length++;
// つぎの循環置換の添字を取得し、循環置換に採用した要素を消す
int k = i;
i = permutation[i];
permutation[k] = -1; // 要素を消す
}
length++;
System.out.printf("](%d), ", length);
return length;
}
/**
* 指定された配列が置換になっているかどうかを確認する。
* この置換は、次の条件を満たしている配列。
* ・要素数 n が 1 以上
* ・値は 1 ~ n までのそれぞれがひとつずつ入っている
*
* @param permutation
* 置換の配列
* @return 置換になっていれば true
*/
public static boolean isPermutation(int[] permutation) {
// ひとつ以上の要素を持つ
if (permutation.length < 1) {
return false;
}
// 置換をコピーして、ソートする
int[] sigma = Arrays.copyOf(permutation, permutation.length);
Arrays.sort(sigma);
// それぞれの添字がその要素値と違えば、置換にはなっていない
for (int i = 0; i < sigma.length; i++) {
if (sigma[i] != i + 1) {
return false;
}
}
return true;
}
/**
* 指定された要素数の置換を取得する。
*
* @param size
* 要素数
* @return 置換
*/
public static int[] getPermutation(int size) {
// ひとつ以上の要素を持つ
if (size < 1) {
throw new IllegalArgumentException(String.format(
"置換の要素数は1以上です。(%d)%n", size));
}
List<Integer> sigma = new ArrayList<Integer>(size);
for (int i = 0; i < size; i++) {
sigma.add(i + 1);
}
Collections.shuffle(sigma); // シャッフルする
int[] permutation = new int[size];
for (int i = 0; i < size; i++) {
permutation[i] = sigma.get(i);
}
assert isPermutation(permutation); // 事後条件
return permutation;
}
}
---
■ JUnit のテストケース
□ SymmetricGroupUtilTest.java
---
import java.util.Arrays;
import junit.framework.TestCase;
public class SymmetricGroupUtilTest extends TestCase {
public void testSgn() {
assertEquals(1, SymmetricGroupUtil.sgn(new int[] { 1, }));
assertEquals(1, SymmetricGroupUtil.sgn(new int[] { 1, 2, 3, }));
assertEquals(1, SymmetricGroupUtil.sgn(new int[] { 2, 3, 1, }));
assertEquals(1, SymmetricGroupUtil.sgn(new int[] { 3, 1, 2, }));
assertEquals(-1, SymmetricGroupUtil.sgn(new int[] { 1, 3, 2, }));
assertEquals(-1, SymmetricGroupUtil.sgn(new int[] { 2, 1, 3, }));
assertEquals(-1, SymmetricGroupUtil.sgn(new int[] { 3, 2, 1, }));
assertEquals(1, SymmetricGroupUtil.sgn(new int[] { 3, 7, 1, 2, 5, 8, 4,
6, }));
assertEquals(1, SymmetricGroupUtil.sgn(new int[] { 1, 2, 3, 4, 5, 6, 7,
8, 9, 10, 11, 12, 13, 14, 15, }));
assertEquals(-1, SymmetricGroupUtil.sgn(new int[] { 1, 2, 3, 4, 5, 6,
7, 8, 9, 10, 11, 12, 13, 15, 14, }));
assertEquals(-1, SymmetricGroupUtil.sgn(new int[] { 6, 12, 9, 2, 15, 1,
14, 11, 13, 8, 3, 5, 4, 10, 7, }));
try {
assertEquals(1, SymmetricGroupUtil.sgn(new int[] {}));
fail();
} catch (IllegalArgumentException e) {
}
}
public void testIsPermutation() {
assertEquals(false, SymmetricGroupUtil.isPermutation(new int[] {}));
assertEquals(true, SymmetricGroupUtil.isPermutation(new int[] { 1, }));
assertEquals(true, SymmetricGroupUtil.isPermutation(new int[] { 1, 2,
3, }));
assertEquals(true, SymmetricGroupUtil.isPermutation(new int[] { 1, 3,
2, }));
assertEquals(true, SymmetricGroupUtil.isPermutation(new int[] { 3, 7,
1, 2, 5, 8, 4, 6, }));
assertEquals(true, SymmetricGroupUtil.isPermutation(new int[] { 1, 2,
3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, }));
assertEquals(true, SymmetricGroupUtil.isPermutation(new int[] { 1, 2,
3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 14, }));
assertEquals(false, SymmetricGroupUtil.isPermutation(new int[] { 0, }));
assertEquals(false, SymmetricGroupUtil.isPermutation(new int[] { 2, }));
assertEquals(false, SymmetricGroupUtil
.isPermutation(new int[] { 1, 1, }));
assertEquals(false, SymmetricGroupUtil
.isPermutation(new int[] { 1, 3, }));
}
public void testGetPermutation() {
assertEquals(true, SymmetricGroupUtil.isPermutation(SymmetricGroupUtil
.getPermutation(1)));
assertEquals(true, SymmetricGroupUtil.isPermutation(SymmetricGroupUtil
.getPermutation(15)));
System.out.println("---");
System.out.println(Arrays.toString(SymmetricGroupUtil
.getPermutation(15)));
System.out.println(Arrays.toString(SymmetricGroupUtil
.getPermutation(15)));
System.out.println(Arrays.toString(SymmetricGroupUtil
.getPermutation(15)));
System.out.println(Arrays.toString(SymmetricGroupUtil
.getPermutation(15)));
try {
assertEquals(true, SymmetricGroupUtil
.isPermutation(SymmetricGroupUtil.getPermutation(0)));
fail();
} catch (IllegalArgumentException e) {
}
}
}
---
