生成C ++中N个数字中的所有R位数字（组合，迭代）？

Question

我有一个程序，我必须在C ++中生成N个数字中的所有R位数字，例如N=3（从1到N的所有数字）和R=2程序应该生成12 13 21 23 31 32。我尝试使用如下的数组执行此操作，但它似乎无法正常工作。

#define nmax 20
#include <iostream>
using namespace std;
int n, r;
void print(int[]);

int main()
{
    cin >> n;
    cin >> r;

    int a[nmax];
    int b[nmax];
    int used[nmax];

    for (int p = 1; p <= n; p++) {
        //Filling the a[] array with numbers from 1 to n
        a[p] = n;
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < r; j++) {
            b[j] = a[i];
            used[j] = 1;
            if (used[j]) {
                b[j] = a[i + 1];
            }
            used[j] = 0;
        }
        print(b);
    }

    return 0;
}

void print(int k[]) {
    for (int i = 0; i < r; i++) {
        cout << k[i];
    }
}

Answer 1

如果我正确理解你的问题，你可以探索this website解释问题并彻底提出解决方案。

这是一个略有改动的代码：

注意时间是更大N值的问题。

#define N    5   // number of elements to permute.  Let N > 2
#include <iostream>
using namespace std;

// NOTICE:  Original Copyright 1991-2010, Phillip Paul Fuchs

void PrintPerm(unsigned int *a, unsigned int j, unsigned int i){
   for(unsigned int x = 0; x < N; x++)
      cout << " " << a[x];
   cout << "    swapped( " << j << " , " << i << " )\n";
}

void QuickPerm(void){
   unsigned int a[N], p[N+1];
   register unsigned int i, j, PermCounter = 1; // Upper Index i; Lower Index j

   for(i = 0; i < N; i++){   // initialize arrays; a[N] can be any type
      a[i] = i + 1;   // a[i] value is not revealed and can be arbitrary
      p[i] = i;
   }
   p[N] = N; // p[N] > 0 controls iteration and the index boundary for i
   PrintPerm(a, 0, 0);   // remove comment to PrintPerm array a[]
   i = 1;   // setup first swap points to be 1 and 0 respectively (i & j)
   while(i < N){
      p[i]--;             // decrease index "weight" for i by one
      j = i % 2 * p[i];   // IF i is odd then j = p[i] otherwise j = 0
      swap(a[i], a[j]);   // swap(a[j], a[i])
      PrintPerm(a, j, i);   // remove comment to PrintPerm target array a[]
      PermCounter++;
      i = 1;              // reset index i to 1 (assumed)
      while (!p[i]) {      // while (p[i] == 0)
         p[i] = i;        // reset p[i] zero value
         i++;             // set new index value for i (increase by one)
      } // while(!p[i])
   } // while(i < N)
    cout << "\n\n ---> " << PermCounter << " permutations. \n\n\n";
} // QuickPerm()

int main(){
    QuickPerm();
} //main

---

以下是原始代码中已修改项目的列表。

1. N定义为5而不是12。
2. 添加了一个计数器以获得更多信息。
3. 通过使用c ++标准库的swap()函数减少了原始交换指令。
4. getch()已被删除。
5. 'Display（）'函数已重命名为'PrintPerm（）'。
6. printf()函数已被cout取代。
7. 已添加打印输入数量。