-2

次のように機能するアルゴリズムが必要です。

いくつかの要素が与えられた場合:

A B C D E F

アルゴリズムは、これらの要素を含む配列のすべての組み合わせを生成する必要があります。

[A,B,C,D,E,F]
[AB,C,D,E,F]
[ABC,D,E,F]
[A,BC,D,E,F]
[A,B,C,DEF]
[ABCDEF]

無効な組み合わせは次のとおりです (例):

[AC,B,D,E,F]
[AB,BC,D,E,F]
[BC,DE,FA]

つまり、要素は順番に維持する必要があります。

編集: 英語の文章でアルゴリズムを使用して、複合名詞を検出したいと考えています。

例えば：

On the table is a water jug.

以下の語群の連続として認識されるべきである。

Pronoun, Determiner, Noun, Verb, Determiner, Noun

だがしかし

Pronoun, Determiner, Noun, Verb, Determiner, Noun, Noun
4

2 に答える 2

1

この問題は、再帰を使用して解決できると思います。例として、A、B、C、D、E、F を取り上げます。A と B を組み合わせて新しい要素 AB を形成できます。残りの要素 C、D、E、F は同じ問題とみなして再帰的に解くことができます。また、A、B、C を組み合わせて新しい要素 ABC を形成し、残りの要素は D、E、F です。コードは以下のとおりです。

#include<iostream>
#include<string>
#include<vector>


using namespace std;

void sequential_combination(char input[],int start, int length,vector<string>& result)
{
     if(start>=length)
     {
        cout<<"[";
        for(int i=0;i<result.size()-1;++i)cout<<result[i]<<",";
        cout<<result[result.size()-1];
        cout<<"]";
        cout<<endl;
     }
     else
     {
         string prefix="";
         for(int i=start;i<length;++i)
         {
                 prefix+=input[i];
                 result.push_back(prefix);
                 sequential_combination(input,i+1,length,result);
                 result.pop_back();
         }
     }     
}

int main()
{

    char input[6]={'A','B','C','D','E','F'};
    vector<string> result;
    sequential_combination(input,0,6,result);
    getchar();
    getchar();
    return 0;
}

それが役に立てば幸い！

于 2012-11-27T13:36:47.367 に答える
1

問題を次のように減らします。

n文字の場合、n-1それらの間に場所があります。各位置にセパレーターを配置するかどうかを選択する必要がありますn-1。

The pseudocode will be something like this:

choose(set, size)
    if (size <= 0) return
    set1 = set
    set2 = set
    choose(set1+1, size-1);
    choose(set2+1, size-1);
    set1 = ',' U set1+1  //set1+1 here denotes the subset starting at second position
    set2 = ' ' U set2+1
    add set1, set2 to the output group

And invoke by choose(A, n-1).

于 2012-11-26T11:19:56.687 に答える