-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

将问题减少到这一点：

对于n字母n-1，它们之间有位置。您需要选择是否在每个n-1位置放置分隔符。

伪代码将是这样的：

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

并由 调用choose(A, n-1)。

于 2012-11-26T11:19:56.687 回答
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 回答