arrays - 如何在数组中生成长度为 M 的所有排列

Question

假设我们有一个长度为 N 的数组，我需要在数组中生成所有长度为 M 的排列

我尝试使用下一个排列，但如果我想生成长度为 5 的数组的所有长度为 3 的排列，我只能得到前 3 个数字的排列。

这是我的代码:

#include <iostream>

#include <algorithm>

using namespace std;

int main()
{
    int arr[5] = {1,2,3,4,5};
    int m=3;

    do {
    for(int i=0;i<m;i++) {
        cout<<arr[i]<<" ";
    }
    cout<<endl;
    } while(next_permutation(arr, arr+m));
    return 0;
}

提前致谢。

Answer 1

有更快的解决方案(参见 Knuth 4A)，但这个解决方案很简单并且在最佳线性因子内。与您编写的内容相比，唯一的变化是 (1) reverse 语句 (2) next_permutation 的参数(n 而不是 m )。

#include <iostream>

#include <algorithm>

using namespace std;

int main() {
  int arr[5] = {1, 2, 3, 4, 5};
  int m = 3;

  do {
    for (int i = 0; i < m; i++) {
      cout << arr[i] << " ";
    }
    cout << endl;
    reverse(arr + m, arr + 5);
  } while (next_permutation(arr, arr + 5));
  return 0;
}