如何从一个给定的数组中产生不同的组合，使序列中的每个数字也是不同的。

Question

我试图从一个给定的 "n "元素数组中生成一个长度为 "k "的序列，使 "k "中的每个tokendigit只出现一次。

例如，如果我的输入数组是{1,2,3,4,5}，并且 "k=4"，那么使用最后4位数字生成序列，生成的序列可以是

1,2,3,4,5
1,2,3,5,4
1,2,4,3,5
1,2,4,5,3
...
...

注意：这里，第一个索引不能被使用，因为我们不允许修改该索引值。

另一个例子，输入数组={1,2,3,4,5}，k="3"，那么使用最后3位数字生成的序列是

1,2,3,4,5
1,2,3,5,4
1,2,4,3,5
1,2,4,5,3
1,2,5,3,4
1,2,5,4,3

从第一眼看，似乎问题属于简单形式的数论或组合论，但我无法找出谁。如果问题太琐碎，我提前道歉。

在我看来，这可以使用多重for循环生成，其中循环数=k，输入是序列的最后k个数，但在运行时我不知道k的值，所以，我需要一些通用的解决方案，是否有任何方法算法来生成降低复杂性的数字。

我也看到一些类似的问题已经被问到了，但我的目标是得到一些通用的或更好的方法。

Answer 1

递归可以完成这项工作。

#include <bits/stdc++.h>    
using namespace std;

int v[] = {1, 2, 3, 4, 5};
int n = 5;
int k = 4;

void rec(deque<int> &d, string s = ""){
    if(d.size() == 0) {
        cout<<s<<endl;
        return;
    }
    for (int i = 0, len = d.size(); i < len; i++) {
        int x = d[0];
        d.pop_front();
        rec(d, s + to_string(x) + " ");
        d.push_back(x);
    }
}

int main(){
    deque<int> d;
    for(int i = n - k; i < n; i++) d.push_back(v[i]);

    string s = "";        
    for(int i = 0; i < n - k; i++) s += to_string(v[i]) + " ";

    rec(d, s);    
    return 0;
}

它只是通过将一个元素设置为第一个元素，然后与其余元素生成组合。

你可以测试一下 此处.