c++ - 获取所有无重复的组合

给出所有可能的字符串组合，在c++中不包含重复项。
输入示例:“123”，输出组合为:

 1,12,123,13,2,23,3.

复制的示例为“12” ==“21”或“123” ==“213”。

假设一个字符不会被多次使用。我也不认为递归是强制性的。

这里有一个php答案。(Get all possible combinations without duplicates)。

我已经考虑过某种形式的结果树，但不确定如何使用递归实现。

我的答案包括重复项，如下所示:

#include <string>
#include <iostream>
using namespace std;

void get( string str, string res ) {

   cout << res << endl;

   for( int i = 0; i < str.length(); i++ )
      get( string(str).erase(i,1), res + str[i] );
}

int main( int argc, char **argv) {
   string str = "123";
   get( str, "" );
   return 0;
}

这是一个面试问题，没有重复的事情让我失望。在此先感谢您的帮助。

最佳答案

OP正在寻找的内容等于Power Set减去Empty Set。无需递归即可轻松实现所需的输出。这是一个简单的方法:

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

void GetPowerSet(std::string v) {

    std::string emptyString;
    std::vector<std::string> powerSet;
    int n = (int) std::pow(2.0, (double) v.size()); // Get size of power set of v
    powerSet.reserve(n);
    powerSet.push_back(emptyString); // add empty set

    for (std::string::iterator it = v.begin(); it < v.end(); it++) {
        unsigned int tempSize = powerSet.size();
        for (std::size_t j = 0; j < tempSize; j++)
            powerSet.push_back(powerSet[j] + *it);
    }

    // remove empty set element
    powerSet.erase(powerSet.begin());

    // print out results
    std::cout << "Here is your output : ";
    for (std::vector<std::string>::iterator it = powerSet.begin(); it < powerSet.end(); it++)
        std::cout << *it << ' ';
}

int main() {
    std::string myStr;
    std::cout << "Please enter a string : ";
    std::cin >> myStr;
    GetPowerSet(myStr);
    return 0;
}

这是输出:

Please enter a string : 123
Here is your output : 1 2 12 3 13 23 123

说明:

我们首先注意到，幂集的大小由2^n给出，其中n是初始集的大小。出于我们的目的，我们的最终 vector 将仅包含2^n - 1元素，但是我们仍然需要保留2^n以防止调整大小，因为构造结果需要“空”元素。

实际工作是在for loops中间的两个GetPowerSet内部进行的。我们从一个空白元素开始。然后，我们遍历原始 vector 中的每个字符，一路创建我们的幂集的子集。例如

用空集初始化功率集:powerSet = {}

将v的第一个元素添加到上面设定的幂的每个元素:'' + '1' = '1'。

powerSet = {{}, '1'}

将v的第二个元素添加到上面设置的幂的每个元素中:'' + '2' = '2', '1' + '2' = '12'

powerSet = {{}, '1', '2', '12'}

将v的第三个元素添加到上面设置的幂的每个元素中:'' + '3' = '3', '1' + '3' = '13', '2' + '3' = '23', '12' + '3' = '123'

powerSet = {{}, '1', '2', '12', '3', '13', '23', '123'}

现在删除上面设定的功率中的第一个元素。

powerSet = {'1', '2', '12', '3', '13', '23', '123'}

我们完成了。

关于c++ - 获取所有无重复的组合，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/49469238/

powerset

c++ - 获取所有无重复的组合