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

Question

I am trying to generate a sequence of length "k" from a given array of "n" elements such that every token/digit in "k" appears only once.

For Eg. if my input array is {1,2,3,4,5} and "k=4" then using the last 4 digits the sequence is generated and generated sequence can be

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

NOTE: Here, the first index cannot be used as we are not allowded to modify that index value.

Another Eg. input array = {1,2,3,4,5} and k="3", then using the last 3 digit the sequence generated is

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

From the first look it seems question belong to simple form of number thoery or combinatrics but i'm unable to figure out whom. My apologies in advance if the question is too trivial.

It seems to me that this can be generated using multiple for loops where number of loops = k and input being the last k number of sequence but at runtime i don't know the value of k so, i need some generalized solution and is there any way/algorithm to generate the digits with reduced complexity.

I have also seen some similar questions that have been asked already but my objective is to get some generalized or better approach.

Answer 1

A recursion can do the job:

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

It simply generates the combinations by setting an element as first and generating combinations with the rest.

You can test it here.