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

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

新規登録して質問してみよう
ただいま回答率
85.50%
Java

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

Q&A

解決済

4回答

2651閲覧

数字を並べ替えて組み合わせを作るアルゴリズムの理解の方法

publicstatic

総合スコア23

Java

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

0グッド

2クリップ

投稿2018/08/26 14:42

4つの数字を並べ替えてできる組み合わせをすべて表示するというプログラムを作ろうとしています。
ですがわからないのでまずは数を少なくして3つにして考えてみました。

abc

の3つだと組み合わせは
abc
acb
bac
bca
cab
cba
の6通りになり、
順列の組み合わせなので3×2×1=6通りで全てだと思います。

再帰関数を組み合わせるとできそうな気がするのですがそれをjavaのプログラムで表現する方法が思いつきませんでした。

前提・実現したいこと

1.組み合わせをjavaプログラムで表現する上で大切なポイントはどういうものがあるのでしょうか?

2.アルゴリズムを理解するのが苦手なのでよい訓練方法があればご教授お願いします。

発生している問題・エラーメッセージ

エラーメッセージ

該当のソースコード

ソースコード

試したこと

ネット上に探しているプログラムに似たものがありました。

java

1public class test { 2 public static void main(String[] args){ 3 permutation("abcd", ""); 4 } 5 6 public static void permutation(String q, String ans){ 7 // Base Case 8 if(q.length() <= 1) { 9 System.out.println(ans + q); 10 } 11 // General Case 12 else { 13 for (int i = 0; i < q.length(); i++) { 14 permutation(q.substring(0, i) + q.substring(i + 1), 15 ans + q.charAt(i)); 16 } 17 } 18 } 19}

上記のプログラムは
実行したときにabcd全ての組み合わせが出力されるものでしたが

java

1permutation(q.substring(0, i) + q.substring(i + 1),ans + q.charAt(i));

の部分がどう動いているのか理解できませんでした。

java

1if(q.length() <= 1) { 2System.out.println(ans + q); 3}

の部分で表示されているのはわかりましたがその過程がよくわからない状態です。

補足情報(FW/ツールのバージョンなど)

ここにより詳細な情報を記載してください。

気になる質問をクリップする

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

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

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答4

0

ベストアンサー

アルゴリズム全般に言えることですが、自分でアルゴリズムを考える場合は再帰に限らずデータの動きを紙などに順に書いてみるといいです。
サンプルがあるなら途中経過を出力してみるのもいいですね。
慣れてきたら頭ん中でデータを動かしてそれをそのままプログラムに落とし込めるようになるかと。

permutationの呼び出しの引数 q, ans を出力したのが以下です。
再帰ごとにインデントを増やしています。
(-> 以降は実際の表示です。)

Output

1abcd, 2 bcd, a 3 cd, ab 4 d, abc -> abcd 5 c, abd -> abdc 6 bd, ac 7 d, acb -> acbd 8 b, acd -> acdb 9 bc, ad 10 c, adb -> adbc 11 b, adc -> adcb 12 acd, b 13 cd, ba 14 d, bac -> bacd 15 c, bad -> badc 16 ad, bc 17 d, bca -> bcad 18 a, bcd -> bcda 19 ac, bd 20 c, bda -> bdac 21 a, bdc -> bdca 22 abd, c 23 bd, ca 24 d, cab -> cabd 25 b, cad -> cadb 26 ad, cb 27 d, cba -> cbad 28 a, cbd -> cbda 29 ab, cd 30 b, cda -> cdab 31 a, cdb -> cdba 32 abc, d 33 bc, da 34 c, dab -> dabc 35 b, dac -> dacb 36 ac, db 37 c, dba -> dbac 38 a, dbc -> dbca 39 ab, dc 40 b, dca -> dcab 41 a, dcb -> dcba

i番目の文字を抜いた文字列とans+i番目の文字列が、次のpermutationのq, ansになります。

qは再帰のたびにどんどん短くなり、最終的に1文字になったらansに連結したものが出力されます。

i番目を抜いて連結するというのを繰り返すので最終的に全組み合わせを列挙することができます、

投稿2018/08/26 15:17

toki_td

総合スコア2850

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

publicstatic

2018/08/26 16:13

回答ありがとうございます。 >自分でアルゴリズムを考える場合は再帰に限らずデータの動きを紙などに順に書いてみるといいです 再帰関数の結果を書こうとはしたのですが途中で結果がどうなるかが理解できず書ききれませんでした。 回答してくださった皆様のおかげで理解できた部分があるので自分でも一回トレースして書き出したいと思います。 i番目の文字を抜いてansに加えているというのは理解できました。 全組み合わせが列挙できるというのを完全に理解はしていないので頑張ってみたいと思います。
guest

0

なんとなく見覚えがあったのでもしかしてこの問題ですか?
原文:Lexicographic permutations
Problem 24

翻訳:Problem 24 「辞書式順列」
参考:全組み合わせの列挙 Java

概要:参考URLの流れをリスト追加に応用してます。

java

1 2import java.util.ArrayList; 3import java.util.List; 4 5public class pe_10024 { 6 7 public static void main(String[] args) { 8 9 long start = System.nanoTime(); 10 11 func(10, 1000000); 12 13 //正解 14 //2783915460 15 //657.64465ms 16 17 long end = System.nanoTime(); 18 System.out.println((end - start) / 1000000f + "ms"); 19 20 } 21 22 // sample 23 // 012 021 24 // 102 120 25 // 201 210 26 27 static void func(int num, int cntEnd) { 28 29 List<Integer> a = new ArrayList<Integer>(); 30 List<Integer> b = new ArrayList<Integer>(); 31 32 for (int i = 0; i < num; i++) { 33 a.add(i); 34 } 35 36 //a:0-9の数値 37 //b:空 38 perm(a, b, cntEnd); 39 40 } 41 42 static void perm(List<Integer> a, List<Integer> b, int cntEnd) { 43 44 int sum = 0; 45 46 //aが空になったら終わり 47 if (a.isEmpty()) { 48 sum++; 49 if (cntEnd == sum) { 50 for (int i = 0; i < b.size(); i++) { 51 System.out.print(b.get(i)); 52 } 53 System.out.println(); 54 } 55 } 56 57 for (int i = 0; i < a.size(); i++) { 58 List<Integer> c = new ArrayList<Integer>(b); 59 List<Integer> d = new ArrayList<Integer>(a); 60 61 //数字を1個づつ移動 62 //d→cへ (a→bへ) 63 c.add(d.get(i)); 64 d.remove(i); 65 66 //再帰 67 perm(d, c, cntEnd); 68 } 69 } 70} 71

投稿2018/08/26 17:27

opyon

総合スコア1009

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

permutation関数の引数qは選択候補の文字列です。ansは選択済みの文字列です。

q.substring(0, i) + q.substring(i + 1)は 文字列qでi番目より手前の文字列とi+1番目より後ろの文字列をつないた文字列、つまりi番目の文字列を除いた文字列です。

ans + q.charAt(i)は 選択済みの文字列に 文字列qのi番目の文字列を追加した文字列です。

つまり 選択候補の文字列qからi番目の文字を選択済みの文字列に移動させています。

あとはじっくり考えてください。

投稿2018/08/26 15:18

fu7mu4

総合スコア1088

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

publicstatic

2018/08/26 15:58

回答ありがとうございます。 q.substring(0, i) + q.substring(i + 1)の部分はi番目の文字を抜くための動きだったのですね。substringの終了のiの部分は含まれていると勘違いしていてわからなくなっていました。 ans+q.charAt(i)でi番目だけを足しているのは理解できました。 部分的にはわかるのですがまだその動きのおかげで全部の出力がされるというのを完全に理解はできていないので頑張ってみたいと思います。
guest

0

qから順に1文字取り除き、取り除いた文字をansに繋ぎ、
qが1文字になるまで自身を呼び出し、qが1文字になったらansにqを繋いで出力する。

つまり、
最初のループでまず
q="abcd",ans=""として呼ばれたのが、1段目の実行で
q="bcd",ans="a"となり、2段目の再帰処理の結果
q="cd",ans="ab"となり、3段目で
q="d",ans="abc"となった4段目では
"abcd"を出力して終わる。
3段目に戻って
q="cd",ans="ab"から2文字目を取り出すので、
q="c",ans="abd"となり、4段目では
"abdc"出力して抜け、3段目も2文字処理したので抜ける。
2段目に戻って
・・・・以下繰り返し。

投稿2018/08/26 15:14

編集2018/08/26 15:17
chun

総合スコア324

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

publicstatic

2018/08/26 16:26

回答ありがとうございます。 >qが1文字になるまで自身を呼び出し、qが1文字になったらansにqを繋いで出力する。 permutation(String q, String ans) で再帰関数として動作しているのということですね。 理屈ではわかっていてもそれを追跡しようとするとまだ理解できていない部分があるせいかわからなくなることが多い状態です。自分でもトレースして行きたいと思っています。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問