3

重複の可能性:
特定の文字列のすべての順列を生成する

n=4, 長さと aが与えられた場合set of characters -> {'a', 'b'}、セット内の文字を含む長さ n の可能なすべての文字列を生成する Java コードを作成する方法を教えてください。

上記の例では、結果には 2^4=16 個の文字列が含まれている必要があります。つまり、次のようになります。

aaaa
aaab
aabb
abbb
baaa
baab
babb
bbbb
bbaa
bbab
bbba
abaa
abab
abba
baba
aaba

ここに私のコードスニペットがあります:

public void process(String result, String string)
{
    if(string.length() == 0)
    {
        System.out.println(result);
    }else{
        for(int i = 0; i < string.length(); i++)
        {
            String newResult = new String(result+string.charAt(i));
            String newString = new String(string.substring(0,i) + string.substring(i+1, string.length()));
            process(newResult, newString);
        }
    }
}

それは、私が望むものではなく、順列を行うだけのようです....... よろしくお願いします:)

4

3 に答える 3

7

数えるのと同じように考えてください。技術的には、バイナリのように aaaa から bbbb まで「カウント」しています。

aaaa -> 0000
aaab -> 0001
aaba -> 0010
aabb -> 0011
...
bbbb -> 1111

あなたが何を試したか見なければ、それ以上のことはできませんが、基本的には、「最低」要素と「最高」要素の間のすべての「数字」を数え上げて列挙する必要があります。

要素数が多い場合は、カウントをより高いベースでカウントするように扱ってください。8 つの要素、Set = {a、b、c、d、e、f、g、h} の場合、基本的に 8 進数でカウントアップします。

aaaa -> 0000
aaab -> 0001
...
aaah -> 0007
aaba -> 0010
...
hhhh -> 7777

これは、0000 から 9999 まで数えることによって、長さ 4 の 0 から 9 のすべての組み合わせを列挙するのと同じ方法です。

編集：

コードを投稿していただきありがとうございます。あなたは正しいです、あなたは順列をやっています。より良い方法は、ここで説明したようなマルチコンビネーション (ordererd コンビネーション セット内の繰り返し要素との組み合わせ) アルゴリズムを使用することです。

于 2012-09-05T20:02:04.280 に答える
0

私はテストしていないので、これはエラーが発生しやすいかもしれませんが、動作するはずです。そうでない場合でも、探しているものに非常に近いはずです。追加するものがないため、最初のforループは値を設定する代わりにresultListにデータを入力することに注意してください。

問題がある場合はお知らせください。修正します。

ArrayList<String> results = new ArrayList<String>();
ArrayList<String> components = new ArrayList<String>(){"a","b","c"};
int n = 4;

int size = components.size();
for ( int j = 0; j < size; j++ )
{
  // start with size^(n-1) copies of each letter. 
  for ( int i = 0; i < Math.pow( size, n-1); i++ )
  {
    results.add( components.get( j ) );
  }
}

// At this point you have each letter in there once...

for( int depth = 1; depth < n; depth++ )
{
  for( int j = 0; j < size; j++ )
  {
    String toAppend = components.get( j );
    for( int i = j; i < results.size(); i += size )
    {
      String current = results.get( i );
      current += toAppend;
      results.set( i, current );
    }
  }
}
于 2012-09-05T20:45:09.637 に答える
0

あなたは答えを得ましたが、もう少し助けが必要だと思います：

if(string.length() == 0)
{
System.out.println(result);
}

なぜ空の文字列を出力するのですか? 何も印刷されません。メッセージを出力して関数を終了したい場合があります。

于 2012-09-05T20:55:28.617 に答える