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

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

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

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

アルゴリズム

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

Q&A

解決済

3回答

11929閲覧

アナグラムのすべてのパターンを表示するプログラム。

退会済みユーザー

退会済みユーザー

総合スコア0

Java

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

アルゴリズム

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

0グッド

0クリップ

投稿2015/10/04 09:59

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ページで確認できます。

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

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

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

guest

回答3

0

次のページを google 検索で見つけました。

...
「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]

他にも次のページも参考になると思います。

投稿2015/10/04 12:03

katoy

総合スコア22324

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

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

退会済みユーザー

退会済みユーザー

2015/10/04 14:17

ありがとうございます。勉強させていただきます。
guest

0

ベストアンサー

配列の全組み合わせを生成する処理のことを、permutationと呼びます。

下記の質問で、数値ではありますが、permutationについて触れています。
これを、文字に置き換えればOKです。

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

投稿2015/10/04 10:29

argius

総合スコア9388

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

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

退会済みユーザー

退会済みユーザー

2015/10/04 14:16

ありがとうございます。リンク先がとても参考になりました。
guest

0

JavaでC++のnext_permutationに当たる関数の実装を見つけました。C++のnext_permutationであれば、同様のことが出来ますが、これで実現可能でしょうか。
http://d.hatena.ne.jp/tomerun/20081203/1228321480

投稿2015/10/04 10:21

taratail

総合スコア76

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

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

退会済みユーザー

退会済みユーザー

2015/10/04 14:18

ありがとうございます。ちょっとやってみます。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

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

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

質問する

関連した質問