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

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

ただいまの
回答率

88.21%

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

解決済

回答 3

投稿

  • 評価
  • クリップ 0
  • VIEW 7,537
退会済みユーザー

退会済みユーザー

Java初心者です。入力された文字のすべてのアナグラムのパターンを表示するプログラムを作ろうと考えています。例えば "ABC" と入力したら

ABC
ACB
BAC
BCA
CAB
CBA

と表示される具合です。
で、以下のコードを書きました。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class anagram {

    public static void main(String[] args)throws IOException {
        System.out.println("文字の入力");
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String S = br.readLine();
        int L = S.length();
        char[] C = new char[L];
        
        for(int i = 0; i < L; i++){
            char c = S.charAt(i);
            C[i] = c;
        }
    }

}
ご覧のとおり、入力された文字を一文字ずつ配列にぶち込むコードを書きました。ですが、一番肝心のすべてのパターンを表すアルゴリズムがわかりません。どのように考えればいいのでしょうか。
また、このコードで直すべき部分、もっと簡潔に書ける部分がありましたらそれのご指摘もお願いいたします。
  • 気になる質問をクリップする

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

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

    クリップを取り消します

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

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

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

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

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

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

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

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

    質問の評価を下げる

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

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

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

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

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

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

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

    詳細な説明はこちら

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

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

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

回答 3

checkベストアンサー

0

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


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

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

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2015/10/04 23:16

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

    キャンセル

0

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

投稿

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2015/10/04 23:18

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

    キャンセル

0

次のページを google 検索で見つけました。
- 同じものを含む順列をJavaで解いてみた http://d.hatena.ne.jp/rsc96074/20120808/1344416134 
...
「MATHEMATICS」の11文字から4文字を取りだして1列に並べる方法は何通りあるか?
...

ここに記載されていたプログラムを少し変更してみました。

// See http://d.hatena.ne.jp/rsc96074/20120808/1344416134
//     同じものを含む順列

import java.util.Arrays;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class PermSame02 {
    static boolean next_perm(char[] p, int n, int r) {
    int i, j;
    char t;

        if (r <= 0 || n < r) {
        return(false);
    }
    for (i = r + 1; i <= n-1; i++) {
        for (j = i; j >= r + 1 && p[j-1] < p[j]; j--) {
        t = p[j]; p[j] = p[j-1]; p[j-1] = t;    // swap(p, j, j - 1);
        }
    }
    for (i = n - 1; i > 0 && p[i-1] >= p[i]; i--);
    if (i == 0) {
        return(false);
    }
    for (j = n - 1; j > i && p[i-1] >= p[j]; j--);
    t = p[j]; p[j] = p[i-1]; p[i-1] = t;        // swap(p, j, i - 1);
    for (j = n - 1; i < j; i++, j--) {
        t = p[i]; p[i] = p[j]; p[j] = t;        // swap(p, i, j);
    }
    print_p(p, r);
    return(true);
    }

    static void print_p(char[] p, int r) {
    String s = "";
    for (char c : p) {
        s += c;
    }
    System.out.println(s);
    }
    public static void main(String[] args) throws IOException {
    // final String P="MATHEMATICS";
    // final String P = "ABC";
    // final int N = P.length();
    // final int R = N;
    System.out.println("文字の入力");
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    final String P = br.readLine();
    final int N = P.length();
    final int R = N;

    char[] p = P.toCharArray();      // 順列生成用
        long tm = System.nanoTime();     // Timer Start
    int count = 0;
    Arrays.sort(p);                  // 必須のソート
    do {
        count++;
    } while(next_perm(p, N, R));

    System.out.println("計: " + count);
    tm = System.nanoTime() - tm;        // Timer Stop
    System.out.printf("Runtime : %.3f [sec]\n",(double)tm / 1e9);
    }
}
// See http://d.hatena.ne.jp/rsc96074/20120808/1344416134
//     同じものを含む順列

import java.util.Arrays;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class PermSame02 {
    static boolean next_perm(char[] p, int n, int r) {
    int i, j;
    char t;

        if (r <= 0 || n < r) {
        return(false);
    }
    for (i = r + 1; i <= n-1; i++) {
        for (j = i; j >= r + 1 && p[j-1] < p[j]; j--) {
        t = p[j]; p[j] = p[j-1]; p[j-1] = t;    // swap(p, j, j - 1);
        }
    }
    for (i = n - 1; i > 0 && p[i-1] >= p[i]; i--);
    if (i == 0) {
        return(false);
    }
    for (j = n - 1; j > i && p[i-1] >= p[j]; j--);
    t = p[j]; p[j] = p[i-1]; p[i-1] = t;        // swap(p, j, i - 1);
    for (j = n - 1; i < j; i++, j--) {
        t = p[i]; p[i] = p[j]; p[j] = t;        // swap(p, i, j);
    }
    print_p(p, r);
    return(true);
    }

    static void print_p(char[] p, int r) {
    String s = "";
    for (char c : p) {
        s += c;
    }
    System.out.println(s);
    }
    public static void main(String[] args) throws IOException {
    // final String P="MATHEMATICS";
    // final String P = "ABC";
    // final int N = P.length();
    // final int R = N;
    System.out.println("文字の入力");
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    final String P = br.readLine();
    final int N = P.length();
    final int R = N;

    char[] p = P.toCharArray();      // 順列生成用
        long tm = System.nanoTime();     // Timer Start
    int count = 0;
    Arrays.sort(p);                  // 必須のソート
    do {
        count++;
    } while(next_perm(p, N, R));

    System.out.println("計: " + count);
    tm = System.nanoTime() - tm;        // Timer Stop
    System.out.printf("Runtime : %.3f [sec]\n",(double)tm / 1e9);
    }
}
実行例:
$ 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 23:17

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

    キャンセル

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

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

関連した質問

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