Java初心者です。入力された文字のすべてのアナグラムのパターンを表示するプログラムを作ろうと考えています。例えば "ABC" と入力したら
ABC
ACB
BAC
BCA
CAB
CBA
と表示される具合です。
で、以下のコードを書きました。
Java
1import java.io.BufferedReader; 2import java.io.IOException; 3import java.io.InputStreamReader; 4public class anagram { 5 6 public static void main(String[] args)throws IOException { 7 System.out.println("文字の入力"); 8 9 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 10 String S = br.readLine(); 11 int L = S.length(); 12 char[] C = new char[L]; 13 14 for(int i = 0; i < L; i++){ 15 char c = S.charAt(i); 16 C[i] = c; 17 } 18 } 19 20}
ご覧のとおり、入力された文字を一文字ずつ配列にぶち込むコードを書きました。ですが、一番肝心のすべてのパターンを表すアルゴリズムがわかりません。どのように考えればいいのでしょうか。
また、このコードで直すべき部分、もっと簡潔に書ける部分がありましたらそれのご指摘もお願いいたします。
気になる質問をクリップする
クリップした質問は、後からいつでもMYページで確認できます。
またクリップした質問に回答があった際、通知やメールを受け取ることができます。
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
回答3件
0
次のページを google 検索で見つけました。
- 同じものを含む順列をJavaで解いてみた http://d.hatena.ne.jp/rsc96074/20120808/1344416134
...
「MATHEMATICS」の11文字から4文字を取りだして1列に並べる方法は何通りあるか?
...
ここに記載されていたプログラムを少し変更してみました。
java
1// See http://d.hatena.ne.jp/rsc96074/20120808/1344416134 2// 同じものを含む順列 3 4import java.util.Arrays; 5import java.io.BufferedReader; 6import java.io.IOException; 7import java.io.InputStreamReader; 8 9class PermSame02 { 10 static boolean next_perm(char[] p, int n, int r) { 11 int i, j; 12 char t; 13 14 if (r <= 0 || n < r) { 15 return(false); 16 } 17 for (i = r + 1; i <= n-1; i++) { 18 for (j = i; j >= r + 1 && p[j-1] < p[j]; j--) { 19 t = p[j]; p[j] = p[j-1]; p[j-1] = t; // swap(p, j, j - 1); 20 } 21 } 22 for (i = n - 1; i > 0 && p[i-1] >= p[i]; i--); 23 if (i == 0) { 24 return(false); 25 } 26 for (j = n - 1; j > i && p[i-1] >= p[j]; j--); 27 t = p[j]; p[j] = p[i-1]; p[i-1] = t; // swap(p, j, i - 1); 28 for (j = n - 1; i < j; i++, j--) { 29 t = p[i]; p[i] = p[j]; p[j] = t; // swap(p, i, j); 30 } 31 print_p(p, r); 32 return(true); 33 } 34 35 static void print_p(char[] p, int r) { 36 String s = ""; 37 for (char c : p) { 38 s += c; 39 } 40 System.out.println(s); 41 } 42 public static void main(String[] args) throws IOException { 43 // final String P="MATHEMATICS"; 44 // final String P = "ABC"; 45 // final int N = P.length(); 46 // final int R = N; 47 System.out.println("文字の入力"); 48 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 49 final String P = br.readLine(); 50 final int N = P.length(); 51 final int R = N; 52 53 char[] p = P.toCharArray(); // 順列生成用 54 long tm = System.nanoTime(); // Timer Start 55 int count = 0; 56 Arrays.sort(p); // 必須のソート 57 do { 58 count++; 59 } while(next_perm(p, N, R)); 60 61 System.out.println("計: " + count); 62 tm = System.nanoTime() - tm; // Timer Stop 63 System.out.printf("Runtime : %.3f [sec]\n",(double)tm / 1e9); 64 } 65} 66// See http://d.hatena.ne.jp/rsc96074/20120808/1344416134 67// 同じものを含む順列 68 69import java.util.Arrays; 70import java.io.BufferedReader; 71import java.io.IOException; 72import java.io.InputStreamReader; 73 74class PermSame02 { 75 static boolean next_perm(char[] p, int n, int r) { 76 int i, j; 77 char t; 78 79 if (r <= 0 || n < r) { 80 return(false); 81 } 82 for (i = r + 1; i <= n-1; i++) { 83 for (j = i; j >= r + 1 && p[j-1] < p[j]; j--) { 84 t = p[j]; p[j] = p[j-1]; p[j-1] = t; // swap(p, j, j - 1); 85 } 86 } 87 for (i = n - 1; i > 0 && p[i-1] >= p[i]; i--); 88 if (i == 0) { 89 return(false); 90 } 91 for (j = n - 1; j > i && p[i-1] >= p[j]; j--); 92 t = p[j]; p[j] = p[i-1]; p[i-1] = t; // swap(p, j, i - 1); 93 for (j = n - 1; i < j; i++, j--) { 94 t = p[i]; p[i] = p[j]; p[j] = t; // swap(p, i, j); 95 } 96 print_p(p, r); 97 return(true); 98 } 99 100 static void print_p(char[] p, int r) { 101 String s = ""; 102 for (char c : p) { 103 s += c; 104 } 105 System.out.println(s); 106 } 107 public static void main(String[] args) throws IOException { 108 // final String P="MATHEMATICS"; 109 // final String P = "ABC"; 110 // final int N = P.length(); 111 // final int R = N; 112 System.out.println("文字の入力"); 113 BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); 114 final String P = br.readLine(); 115 final int N = P.length(); 116 final int R = N; 117 118 char[] p = P.toCharArray(); // 順列生成用 119 long tm = System.nanoTime(); // Timer Start 120 int count = 0; 121 Arrays.sort(p); // 必須のソート 122 do { 123 count++; 124 } while(next_perm(p, N, R)); 125 126 System.out.println("計: " + count); 127 tm = System.nanoTime() - tm; // Timer Stop 128 System.out.printf("Runtime : %.3f [sec]\n",(double)tm / 1e9); 129 } 130}
実行例:
$ javac PermSame02.java $ java PermSame02 文字の入力 A 計: 1 Runtime : 0.001 [sec] $ java PermSame02 文字の入力 ABC ACB BAC BCA CAB CBA 計: 6 Runtime : 0.001 [sec] $ java PermSame02 文字の入力 AAB ABA BAA 計: 3 Runtime : 0.001 [sec] $ java PermSame02 文字の入力 ABC ACB BAC BCA CAB CBA 計: 6 Runtime : 0.001 [sec]
他にも次のページも参考になると思います。
- 重複を含む要素の順列(非数値もOK) http://sekai.hateblo.jp/entry/2013/09/24/203751
- Java8のStreamで順列を生成 http://qiita.com/saka1029/items/cba9d973888f90cb31de
- 同じものを含む順列をJavaで解いてみた >
- CS 314 - Specification 8 - Anagrams https://www.cs.utexas.edu/~scottm/cs314/Assignments/A8_Anagrams.html
投稿2015/10/04 12:03
総合スコア22324
0
ベストアンサー
配列の全組み合わせを生成する処理のことを、permutation
と呼びます。
下記の質問で、数値ではありますが、permutation
について触れています。
これを、文字に置き換えればOKです。
投稿2015/10/04 10:29
総合スコア9388
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
0
JavaでC++のnext_permutationに当たる関数の実装を見つけました。C++のnext_permutationであれば、同様のことが出来ますが、これで実現可能でしょうか。
http://d.hatena.ne.jp/tomerun/20081203/1228321480
投稿2015/10/04 10:21
総合スコア76
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
退会済みユーザー
2015/10/04 14:18
あなたの回答
tips
太字
斜体
打ち消し線
見出し
引用テキストの挿入
コードの挿入
リンクの挿入
リストの挿入
番号リストの挿入
表の挿入
水平線の挿入
プレビュー
質問の解決につながる回答をしましょう。 サンプルコードなど、より具体的な説明があると質問者の理解の助けになります。 また、読む側のことを考えた、分かりやすい文章を心がけましょう。
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
退会済みユーザー
2015/10/04 14:17