javaで0,1,2,3,4の５つの数の並べ方をすべて導出したい

Question

現在javaの学習を行っております。
５点の最短閉路を再帰を用いて求めるプログラムを作りたいです。
今、５点のすべての並び方を調べて、すべての経路の長さを図ることで
最短閉路を求めたいと覆っています。

そこで、0,1,2,3,4の数字の並べ方をすべて導出するプログラムを教えてください。

また、ほかによい考え方があればぜひ教えてください。

Answer 1

もっと良い方法があるかも知れませんが、一例を紹介します。

すべての並び替えた組み合わせを実現するにはpermutationという操作を行います。他の言語では標準関数になっていることもある操作です。

Javaの場合、permutationするのに標準ライブラリーだけではたぶん難しいと思いますので、Uncommons Mathsというライブラリーを使います。

Uncommons Maths

Uncommons Mathsを使う場合、Mavenなら下記の依存関係を追加します。Mavenを使わない場合は、上記ページからライブラリーをダウンロードしてください。

    <dependency>
      <groupId>org.uncommons.maths</groupId>
      <artifactId>uncommons-maths</artifactId>
      <version>1.2.2</version>
    </dependency>
    <dependency>
      <groupId>jfree</groupId>
      <artifactId>jfreechart</artifactId>
      <version>1.0.13</version>
    </dependency>

5個だとここでは結果が多すぎるので、数字4個の例を示します。

// import java.util.Arrays;
// import java.util.List;
// import org.uncommons.maths.combinatorics.PermutationGenerator;

PermutationGenerator<Integer> gen = new PermutationGenerator<>(Arrays.asList(0, 1, 2, 3));
while (gen.hasMore()) {
    List<Integer> a = gen.nextPermutationAsList();
    System.out.println(a);
}

実行結果。

[0, 1, 2, 3]
[0, 1, 3, 2]
[0, 2, 1, 3]
[0, 2, 3, 1]
[0, 3, 1, 2]
[0, 3, 2, 1]
[1, 0, 2, 3]
[1, 0, 3, 2]
[1, 2, 0, 3]
[1, 2, 3, 0]
[1, 3, 0, 2]
[1, 3, 2, 0]
[2, 0, 1, 3]
[2, 0, 3, 1]
[2, 1, 0, 3]
[2, 1, 3, 0]
[2, 3, 0, 1]
[2, 3, 1, 0]
[3, 0, 1, 2]
[3, 0, 2, 1]
[3, 1, 0, 2]
[3, 1, 2, 0]
[3, 2, 0, 1]
[3, 2, 1, 0]

Comments

[Rino-T_C]

コメント遅れまして申し訳ありません。

そのようなライブラリがあるんですね！
参考にさせていただきます！！
ありがとうございます！

Answer 2

こんにちは。

　お手本になるようなアルゴリズムや、それを実装したコードがきっと
あるのだろうなと思いつつ、自分の頭の体操としてやってみました。

　基本的な考え方は以下です。

0 以上 n以下の(n+1)個の整数を要素とする順列 p(n+1) は、
0 以上 (n-1)以下の n個の整数を要素とするある順列 p(n)に、
要素 n を追加して作成する。
その際に、要素 n を追加する場所は、以下の(n+1)ヶ所ある。
・p(n)の先頭
・p(n)の要素と要素の間（これは、(n-1)ヶ所ある。）
・p(n)の末尾

たとえば、0以上2以下を要素として持つ、[0,1,2]という順列に
要素 3 を加える位置は、先頭、0と1の間、1と2の間、末尾の
４カ所あり、これらの追加する位置の違いによって４つの順列、
[3,0,1,2]
[0,3,1,2]
[0,1,3,2]
[0,1,2,3]
が作成されます。この考え方で再帰のアルゴリズムを作成しました。
以下のソースで、
private static List<List<Integer>> getPermutations(Integer n)
が再帰で解のリストを求めるメソッドです。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Q11179 {

	public static void main(String[] args) {

		// 0以上４以下の整数のすべての順列のリストを作成
		List<List<Integer>> list = getPermutations(4);

		// 結果の表示（逆順にリスト要素を出力）
		int counter = 0;
		for (int i = list.size() - 1; i >= 0; --i) {
			counter++;
			System.out.println(counter + ":" + list.get(i));
		}
	}

	/*
	 * 0以上 n以下の整数を要素とする順列（を表現したリスト）を
	 * 要素として持つリストを作成
	 */
	private static List<List<Integer>> getPermutations(Integer n) {

		// n が不正な値のとき、何もせず null を返して終了
		if (n == null || n < 0)
			return null;

		// このメソッドの返り値となるリストを作成
		List<List<Integer>> results = new ArrayList<List<Integer>>();

		// n = 0 の場合、要素の追加が可能なリスト[0]を要素とするリストを返す。
		if (n == 0) {			
			results.add(new ArrayList<Integer>(Arrays.asList(0)));
			return results;
		}

		// n > 0 の場合、まず、(n-1)に対する解のリストを再帰で取得
		List<List<Integer>> prevResults = getPermutations(n - 1);

		// (n-1)のときのリストをループし、要素の順列に n を加えた順列を作成
		for (List<Integer> permutation : prevResults) {
			for (int i = 0; i <= n; ++i) {	// n を加える位置についてのループ
				permutation.add(i, n);
				results.add(new ArrayList<Integer>(permutation));
				permutation.remove(n);
			}
			permutation.clear(); 	// 全要素を削除しておく
		}
		prevResults.clear(); 	// 全要素を削除しておく

		return results;
	}
}

　上記を実行すると、以下のような出力が得られます。
行頭の数字は、組み合わせの数を数えるためのものです。

1:[0, 1, 2, 3, 4]
2:[0, 1, 2, 4, 3]
3:[0, 1, 4, 2, 3]
4:[0, 4, 1, 2, 3]
5:[4, 0, 1, 2, 3]
・・・
117:[3, 2, 1, 4, 0]
118:[3, 2, 4, 1, 0]
119:[3, 4, 2, 1, 0]
120:[4, 3, 2, 1, 0]

５個の要素による順列の数は、公式nPr = n!/(n-r)!　に n=r=5 を代入して

5P5 = 5!/(5-5)! = (54321)/0! = 120/1 = 120

ですので、出力例の行数は合っています。
また、ソースコードのmainメソッドの中で
List<List<Integer>> list = getPermutations(4);
としているところを
List<List<Integer>> list = getPermutations(5);
にしたり、
List<List<Integer>> list = getPermutations(0);
にしたりしてみましたが問題なく動くのを確認しました。
ただし私の手元のPCでは、
getPermutations(8);
まではいけましたが
getPermutations(9);
でヒープを使い果たして

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space

となりました。

以上、ご参考になれば幸いです。

Comments

[Rino-T_C]

コメント遅れまして申し訳ありません！

丁寧な説明、ありがとうございます！！
今は時間がないので、じっくり読ませていただくことはできないのですが、
とても参考になりそうな回答をいただけてこちらとしても非常に助かっています！
ありがとうございます。

Answer 3

最短閉路問題は、最短ハミルトン路問題あるいは巡回セールスマン問題として有名です。
基点(たとえば0)から隣接する点(1,2,3,4?)までの距離を情報として持つ必要があります。
私はあまり詳しくないので、上記問題名でググって確認してみてください。

Comments

[Rino-T_C]

コメント遅れました！
ありがとうございます！！
今は時間がないので後でググってみますね。
有名問題の名前がわかるだけで、調べるのが楽になります。
ありがとうございました！

Answer 4

こんなんいかがでしょう

package a;

public class TT11179 {
	public static void main(String[] args) {
		try {
			new Permutation() {
				@Override
				public void found(int[] list) {
					for(int val : list) {
						System.out.print(" " + val);
					}
					System.out.println("");
				}
			}
			.find(5);
		}
		catch(Throwable e) {
			e.printStackTrace();
		}
	}

	public static abstract class Permutation {
		private int _count;
		private boolean[] _picked;
		private int[] _list;

		public void find(int count) {
			_count = count;
			_picked = new boolean[count];
			_list = new int[count];
			pick(0);
		}

		private void pick(int index) {
			if(_count <= index) {
				found(_list);
				return;
			}
			for(int val = 0; val < _count; val++) {
				if(_picked[val] == false) {
					_picked[val] = true;
					_list[index] = val;
					pick(index + 1);
					_picked[val] = false;
				}
			}
		}

		public abstract void found(int[] order);
	}
}

Answer 5

順列を求める方法はいくつもあります。

参考：

• リスト 8 : 順列の生成（再帰版） http://www.geocities.jp/m_hiroi/java/abcjava04.html
• 「6枚のカードの並べ方を求めて！」問題解説 ＃java https://codeiq.jp/magazine/2014/05/10469/

Comments

[Rino-T_C]

ありがとうございます。
教えてくださったサイトも参考にさせていただきますね。