如何从给定数组生成不同的组合，使得序列中的每个数字也不同

Question

我正在尝试从给定的 "n" 元素数组生成一个长度为 "k" 的序列，这样 "k" 中的每个 token/digit 只出现一次。

例如。如果我的输入数组是 {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 的值，所以我需要一些广义解决方案，是否有任何 way/algorithm 来生成复杂度降低的数字。

我也看到了一些类似的问题，但我的 objective 是为了获得一些通用的或更好的方法。

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;
}

它只是通过将一个元素设置为第一个元素并生成与其余元素的组合来生成组合。

你可以测试一下here。

如何从给定数组生成不同的组合，使得序列中的每个数字也不同

How to generate distinct combinations from a given array such that every digit in sequence is also distinct

algorithm

logic

permutation

combinatorics

number-theory