在C++中获取一个数字的所有组合

Question

我需要获得给定集合的所有可能组合。例如，给定：[1, 4, 7]，则生成的组合应为：

111、114、117、141、144、147、171、174、177、411、414、417、441、444、447、471、474、477、711、714、717、741、744、747、771、774、777。

我尝试使用next_permutation方法，但这并不是我想要的（它不会返回值如111、144、717等）。

那么，有什么方法可以在C++中实现这一点吗？请注意，我是个完全的初学者。

提前致谢。

- Roshnal

---

对于一个由3个项目组成的集合，这就是使用替换符号进行三进制计数。这很容易进行推广。 - harold

说实话，我很难想象有人能够清晰地提出这个问题，却不知道如何想出解决这个问题的算法。希望我的话听起来不无礼或刻薄，这其实是一种夸奖。你显然理解这个问题——那么为什么算法不会立即跟随而来呢？ - David Schwartz

@Karoly：递归能做的事情，你也可以不用它来完成。 - ypercubeᵀᴹ

@David Nonsense. 这个问题只有在你真正解决它之后才显得微不足道。 - Konrad Rudolph

@Roshnal 所以要泛化.. - harold

Answer 1

仔细观察这些数字：你列出的所有数字也可以表示为列表{11,14,17,41,44,47,71,74,77}，其中一次以1为前缀，一次以4为前缀，一次以7为前缀。这指向一个通用规则：

引用： 从集合{1,4,7}中取3个数字构成的字符串是通过取2个相同集合中的数字并在每个元素前面加上集合中的元素来构建的。

将此规则中的3和2进行概括，并使用递归实现该思想，即可得到您问题的算法。

作为C++实现注意事项，请确保使用字符串而不是整数来表示您的数字。该问题不涉及算术，与十进制表示密切相关。使用字符串会让您的生活变得更加轻松。

- thiton

---

我之前没有注意到这个模式，但现在我可以采取一些行动。非常感谢！ - Roshnal

实际上，问题就在于算术 - 它只是在基数为n（这里是3）的情况下进行计数 - 因此，与十进制表示根本没有关联。 - Konrad Rudolph

@KonradRudolph：之后进行符号替换，当然可以。但是，我认为从字母和字符串的角度来考虑这个问题会更容易和高效。毕竟，OP试图生成{1,4,7}^N。算术非常基础（只有计数，但没有加法或更高级的算术），它们并不是非常有用。 - thiton

在编程方面，对于一个回答，应该温和地指导正确的方向，而不是展示最终目标或淹没提问者在技术细节中。 - Matthieu M.

Answer 2

创建一个带有值的数组，例如{1，4，7}。

使用length（array）来进行循环，每个循环都有length（array）次迭代。

在最内层循环中，输出100 * array [i] + 10 * array [j] + array [k]。

如果最大长度未知，则可以使用递归，例如伪代码：

void Solve(int[] array, int length, int position, int sum)
{
    position++;
    sum *= 10;

    for (int cnt = 0; cnt < length; cnt++)
    {
        int tempsum = sum + array[cnt];

        if (position == length)
            output(tempsum);
        else
            Solve(array, length, position, tempsum);
    }
}

- Danny Varod

---

笑，不，它不是一个固定的集合。你假设有三个值。 - Karoly Horvath

这显然适用于任意数量的值和非固定集合。 - David Schwartz

我相信他可以学习这种方法，然后自己扩展。如果不行的话，也许他应该放弃编程。 - Danny Varod

人们似乎忘记了他们已经熟悉解决这些问题的技巧。对于初学者来说，这并不是一件简单的事情。 - Karoly Horvath

@KarolyHorvath 可能吧，这取决于初学者。编辑以概括方法。 - Danny Varod

Answer 3

创建一个整数向量（称为vector），其大小等于集合中元素的数量。将每个条目初始化为0。然后按照以下算法执行：

1）遍历vector，输出相应的元素。（因此，如果向量是0,1,1，而集合是[9,8,7]，则输出988--第零个元素，第一个元素，第一个元素。）

2）设置一个名为element的整数。

3）增加vector[element]。检查vector[element]是否等于集合中的元素数量。如果不是，请转到步骤1。

4）将vector[element]设置为零。增加element。如果element小于集合中的元素数量，则转到步骤3。

5）停止。你完成了。

- David Schwartz

Answer 4

我冒昧尝试实现了这个任务。我想恢复一下自己的算法知识。结果是这样的：

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

vector<int> allowedNumbers;

bool my_next_perm(vector<int>::iterator& begin, vector<int>::iterator& end) {
    for (vector<int>::iterator itr = end - 1; ; --itr)
    {
        if (*itr != allowedNumbers.back())
        {
            *itr = *upper_bound(allowedNumbers.begin(), allowedNumbers.end(), *itr);
            while ((++itr) != end) {
                *itr = allowedNumbers[0];
            }
            return true;
        }
        if (itr == begin)
        {
            return false;
        }
    }
}
void printAllPermutationsWithRepetitions(vector<int>& v)
{
    int n = v.size();
    set<int> allNumbers;
    for (int i = 0; i < n; i++)
    {
        allNumbers.insert(v[i]);
    }
    for (set<int>::iterator itr = allNumbers.begin(); itr != allNumbers.end(); ++itr) {
        allowedNumbers.push_back(*itr);
    }
    for (int i = 0; i < n; i++) {
        v[i] = allowedNumbers[0];
    }

    do {
        for (int i = 0; i < n; i++) {
            if (i != 0) cout << " ";
            cout << v[i];
        }
        cout << endl;
    } while(my_next_perm(v.begin(), v.end()));
}

int main (int argc, char *argv[]) {
    vector<int> v;
    v.push_back(7);
    v.push_back(1);
    v.push_back(3);
    printAllPermutationsWithRepetitions(v);
    return 0;
}

实现略微不够优化（因为我使用了upper_bound）。

- Boris Strandjev

Answer 5

您可以将从000到222的计数视为基于3的计数，并使用这些数字作为索引查找[1、4、7]数组。将其推广为可与任意大小的输入数组配合使用：

int n = digits.size();
int n_n = std::pow(n, n);
for (int i = 0; i < n_n; ++i)
{
     int x = i;
     for (int j = 0; j < n; ++j)
     {
          cout << digits[x % n];
          x /= n;
     }
     cout << ' ';
}

- Tony Delroy

Answer 6

请看我在这里的答案：PHP获取所有组合

提示：这不是C++代码，但你会明白的。（我建议使用递归）

- Dr.Kameleon

Answer 7

这是最简单的方法。您可以从用户输入任何数字，例如147，它将打印所有排列方式： 111、114、117、141、144、147、171、174、177、411、414、417、441、444、447、471、474、477、711、714、717、741、744、747、771、774、777。

#include <iostream>
#include <cstdlib>
#include <cmath>
using namespace std;

 bool Search(int A[],int num,int length)
    {
        for(int i = 0;i<length;i++)
            if(A[i] == num)
                return 1;
        return 0;
    }


    int main()
    {
        int n;
        cout << "Please Enter a Number\n";
        cin>>n;
        int num = n, k = 1;
        int count = 0;
        while(num>0)
        {
            num/=10;
            count++;
        }
        cout<<"The All Permutations of " <<n<<" are: "<<endl;
        num = n;
        int *A = new int[count];

        for(int i = 0;i<count;i++)
        {
            A[i] =  num%10;
            num/=10;
        }


        int fact = pow(count,count);
        int *Ar = new int[fact];
        int *B = new int[count];
        int value,number = 0;

        for(int i = 0;i<fact;)
        {

            for(int j = 0;j<count;++j)
            {
                value = (rand()%count);

                B[j] = value;
            }

            for(int k= 0;k<count;k++)
                number = number + A[B[k]]*pow(10,k);

            if(Search(Ar,number,fact) == 0)
            {
                cout<<k++<<". "<<number<<endl;
                Ar[i] = number;
                ++i;
            }
            number = 0;

        }

        return 0;
    }

- rpg