-2

文字列の可能な固定長の組み合わせを見つける関数を作成する必要があります。必要なのは、すべてのコンビが必要なわけではないということです。たとえば、文字列が「abcde」で、長さ 3 のコンビが必要な場合、関数は次を返す必要があります。

abc
abd
abe
acd
ace
ade
bcd
bde
bce
cde

そして他にはありません。私は再帰を使用してそれを試みてきましたが、期待どおりにうまくいきませんでした。同様の質問もいくつか見ましたが、あまり役に立ちませんでした。アルゴリズムまたはコード (C、C++、Java)、どんな助けでも大歓迎です。ありがとう。！

注: 組み合わせは注文する必要があります。つまり、文字は入力文字列と同じ順序に従う必要があります。

4

4 に答える 4

3

3 つの入力がある場合、3 つのインデックスがあり、最初は入力文字列の最初の 3 つのインデックスに設定されます。それを出力してから、最後のインデックスを 1 増やし、すべてのインデックスを出力します。入力文字列の最後に到達するまで続行し、2 番目のインデックスを増やして 3 番目を 2 番目の次のインデックスにリセットします。2 番目のインデックスが最後から 2 番目の文字になるまで続けてから、最初のインデックスを増やし、最初のインデックスの後に 2 番目と 3 番目のインデックスを連続して配置します。継続する...

説明してみましょう：

入力: [abcde]
         ^^^
         123

出力: abc

次の反復:

入力: [abcde]
         ^^ ^
         12 3

出力: abd

次の反復:

入力: [abcde]
         ^^ ^
         12 3

出力：阿部

次の反復:

入力: [abcde]
         ^^ ^^
         1 23

出力: acd

次の反復:

入力: [abcde]
         ^ ^ ^
         1 2 3

出力：エース

次の反復:

入力: [abcde]
          ^^^
          123

出力: bcd

次の反復:

入力: [abcde]
          ^^ ^
          12 3

出力: bce

次の反復:

入力: [abcde]
          ^^ ^^
          1 23

出力: bde

次の反復:

入力: [abcde]
           ^^^
           123

出力: cde
于 2012-08-20T09:36:53.693 に答える
0

もっとうまくやれると思いますが、これは私がすぐに思いつくことができたものです。

私はList順序を維持するためにを使用し、厄介な重複を避ける必要がありました。代わりに使用するSetと、チェックをスキップできresult.contains(s)ますが、より良いアルゴリズムでは、よりクリーンな方法で重複を回避できる可能性があります。

private static List<String> substrings(int i, String input) {
    List<String> result = new ArrayList<String>();
    if (i == 0)
        return result;

    String first = input.substring(0, i);
    result.add(first);

    if (input.length() == i) {
        return result;
    }

    // Recursively find substrings of next smaller length not including the first character
    List<String> tails = substrings(i-1, input.substring(1));

    // Append first char to each result of the recursive call.
    for (String sub: tails) {
        String s = input.substring(0, 1) + sub;
        if (!(result.contains(s)))
            result.add(s);
    }

    // Add all substring of current length not including first character
    result.addAll(substrings(i, input.substring(1)));
    return result;
}
于 2012-08-20T12:05:05.500 に答える
0

  1. 要件は特定の長さ 3 であるため、String3 のチャンクに分割してからアルゴリズムを適用します。

  2. 3 のうちの1 文字を脇に置きString、残りの 2 の可能な順列を計算します。

  3. 計算された順列のすべての可能な位置にその 1 文字を配置します。

  4. 上記を繰り返します。

于 2012-08-20T09:32:54.497 に答える
0 
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>


int main()
{
    char buf[6] = "abcde";
    int len = strlen(buf);
   // std::vector<std::string> char_list;
    for(int i = 0; i < len; ++i){
        for(int j = i+1; j < len;++j){
                //if (i==j)continue;
                for(int k = j+1; k < len;++k){
                        //if(i == k || j == k)
                        //      continue;
                        char temp[4]="";
                        temp[0] = buf[i];
                        temp[1] = buf[j];
                        temp[2] = buf[k];
                        temp[3] = '\0';
                        std::cout << temp << std::endl;
                        //show(temp,3);
                        //char_list.push_back(key);
                }
        }
    }

    return 0;
}
于 2012-08-20T09:54:02.850 に答える