c++ - 在 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++ 中做到这一点吗？请注意，我是一个完整的初学者。

提前致谢。

score 8 · Accepted Answer

仔细看一下数字：您列出的所有数字也可以表示为列表 {11,14,17,41,44,47,71,74,77}，前缀一次是 1，一次是 4，一次是 7 . 这指向一个通用规则：

具有集合 {1,4,7} 的 3 个数字的字符串是通过获取具有相同集合的 2 个数字的字符串并在集合的每个元素前面加上来构建的。

概括这条规则中的 3 和 2，用递归实现结果的想法，你就有了一个算法来解决你的问题。

作为 C++ 实现说明，请确保使用字符串而不是整数来表示数字。这个问题不是算术问题，并且与 base-10 表示紧密耦合。弦乐会让你的生活更轻松。

score 1 · Accepted Answer

使用值创建一个数组，例如 {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);
    }
}

score 1 · Accepted Answer

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

1) Walk vector，输出对应的元素。（所以如果向量是 0,1,1，集合是 [9,8,7]，输出 988——第零个元素，第一个元素，第一个元素。）

2) 设置一个被称为element0 的整数。

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

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

5) 停止。你完成了。

score 0 · Accepted Answer

在这里看看我的答案：PHP 采用所有组合

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

score 0 · Accepted Answer

好吧，我冒昧地尝试执行任务。我想锈掉一点我的算法知识。结果是这样的：

#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）。

score 0 · Accepted Answer

您实际上是从 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 << ' ';
}

score 0 · Accepted Answer

这是最简单的方法。您可以将任何数字作为用户的输入，例如 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;
    }

c++ - 在 C++ 中获取数字的所有组合

7 回答 7

Related

Reference