Как сгенерировать различные комбинации из заданного массива, чтобы каждая цифра в последовательности также отличалась

Я пытаюсь создать последовательность длины «k» из заданного массива «n» элементов, так что каждый токен/цифра в «k» появляется только один раз.

Например. если мой входной массив равен {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, поэтому мне нужно какое-то обобщенное решение, и есть ли любым способом/алгоритмом для генерации цифр с уменьшенной сложностью.

Я также видел некоторые похожие вопросы, которые уже задавались, но моя цель - получить какой-то обобщенный или лучший подход.


logic algorithm permutation combinatorics number-theory
person Anand    schedule 15.06.2020    source источник
comment
Можете ли вы дать какую-либо ссылку или ссылку на проблему   -  person Deepak Tatyaji Ahire    schedule 15.06.2020
comment
@DeepakTatyajiAhire На самом деле, это не проблема с какого-то сайта кодирования. Это уменьшенная часть большой проблемы, с которой у меня возникли проблемы, продемонстрированная в уменьшенном формате.   -  person Anand    schedule 15.06.2020

Ответы (1)


arrow_upward
1
arrow_downward

Рекурсия может выполнить эту работу:

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

Он просто генерирует комбинации, устанавливая элемент первым и создавая комбинации с остальными.

Вы можете протестировать его здесь.

person Daniel    schedule 15.06.2020
comment
Спасибо @Daniel, это решение работает. какова, по-вашему, временная сложность этого прогона? - person Anand; 15.06.2020
comment
Сложность O(k!), потому что k! будут генерироваться последовательности. Если вам нужно сгенерировать k! последовательностей, что, кажется, имеет место, вы не можете избежать этой сложности. Например, в вашем случае, когда k = 3, количество сгенерированных последовательностей равно 3! = 3 * 2 * 1 = 6. Алгоритм, с другой стороны, не добавляет дополнительной сложности. - person Daniel; 15.06.2020
comment
хорошо, кажется, что весь вопрос свелся к вычислению перестановки k. В любом случае спасибо - person Anand; 15.06.2020