获取所有无重复的组合 [英] Get all combinations without duplicates

问题描述

给出在c ++中没有重复的字符串的所有可能组合。
输入示例为 123，输出组合为：

Give all possible combinations of a string without duplicates in c++. Example input: "123" and output combinations will be:

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

重复项的示例为 12 == 21或 123 == 213。

An example of a duplicate would be "12"=="21" or "123"=="213".

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

Assume a character will not be used more than once. Also I don't think recursion is mandatory.

这里有一个php答案。（获取所有可能没有重复的组合）。

There's a php answer here.(Get all possible combinations without duplicates).

我考虑过某种形式的结果树，但不确定

I have thought about some form of results tree but unsure how to implement with recursion.

我的包含重复项的答案如下：

My answer that includes duplicates is below:

#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;
}

这是一个面试问题，没有重复的东西扔给了我。在此先感谢您的帮助。

This was an interview question and the no duplicates thing threw me. Thanks in advance for any help.

推荐答案

OP所寻找的内容等同于功率集减去空集。无需递归即可轻松实现所需的输出。这是一种简单的方法：

What the OP is looking for is equivalent to the Power Set minus the Empty Set. The desired output can easily be achieved without recursion. Here is a simple approach:

#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 是初始集合的大小。为了我们的目的，我们的最终向量将只包含 2 ^ n-1 个元素，但是我们仍然需要保留 2 ^ n 为防止调整大小，因为需要使用空 元素来构造结果。

Explanation:

We first note that the size of the power set is given by 2^n where n is the size of the initial set. For our purposes, our final vector will only contain 2^n - 1 elements, however we still need to reserve 2^n in order to prevent resizing as the "empty" element is needed to construct our result.

实际工作是在在 GetPowerSet 中间有两个 for循环。我们从一个空白元素开始。然后，我们遍历原始向量中的每个字符，从而沿途创建幂集的子集。 例如

The real work is carried out inside the two for loops in the middle of GetPowerSet. We start with a blank element. We then iterate over each character in our original vector creating subsets of our power set along the way. E.g

1. 使用空集初始化功率集： powerSet = {}


2. 将 v 的第一个元素添加到上面设定的幂的每个元素中： ''+'1'='1'。
   
   
   
   
   • powerSet = {{}，'1'}
   
   

1. Initialize power set with the empty set: powerSet = {}
2. Add the first element of v to every element of the power set above: '' + '1' = '1' .
   • powerSet = {{}, '1'}

• powerSet = {{}，'1'，'2'，'12'}

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

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

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

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

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

完成。

这篇关于获取所有无重复的组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！