質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.49%

  • Java

    14048questions

    Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

  • アルゴリズム

    420questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

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

解決済

回答 5

投稿

  • 評価
  • クリップ 0
  • VIEW 4,188

Rino-T

score 25

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

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

また、ほかによい考え方があればぜひ教えてください。
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 5

+6

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


すべての並び替えた組み合わせを実現するには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]

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2015/06/15 17:08

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

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

    キャンセル

checkベストアンサー

+3

こんにちは。

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

 基本的な考え方は以下です。
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の間、末尾の
4カ所あり、これらの追加する位置の違いによって4つの順列、
 [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以上4以下の整数のすべての順列のリストを作成
        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]
5個の要素による順列の数は、公式nPr = n!/(n-r)! に n=r=5 を代入して

5P5 = 5!/(5-5)! = (5*4*3*2*1)/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

となりました。

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

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2015/06/15 17:07

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

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

    キャンセル

+3

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2015/06/15 16:57

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

    キャンセル

+2

こんなんいかがでしょう
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);
    }
}

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

+1

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

参考:
- リスト 8 : 順列の生成(再帰版) http://www.geocities.jp/m_hiroi/java/abcjava04.html
- 「6枚のカードの並べ方を求めて!」問題解説 #java https://codeiq.jp/magazine/2014/05/10469/

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2015/06/15 17:01

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

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.49%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る

  • Java

    14048questions

    Javaは、1995年にサン・マイクロシステムズが開発したプログラミング言語です。表記法はC言語に似ていますが、既存のプログラミング言語の短所を踏まえていちから設計されており、最初からオブジェクト指向性を備えてデザインされています。セキュリティ面が強力であることや、ネットワーク環境での利用に向いていることが特徴です。Javaで作られたソフトウェアは基本的にいかなるプラットフォームでも作動します。

  • アルゴリズム

    420questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。