Выведите k различных отсортированных перестановок данного массива

Для массива arr [], содержащего N целых чисел, задача состоит в том, чтобы вывести k различных перестановок индексов так, чтобы значения в этих индексах образовывали неубывающую последовательность. Выведите -1, если это невозможно.

Примеры:

Input: arr[] = {1, 3, 3, 1}, k = 3 
Output: 
0 3 1 2 
3 0 1 2 
3 0 2 1 
For every permutation, the values at the indices form the following sequence {1, 1, 3, 3}
Input: arr[] = {1, 2, 3, 4}, k = 3 
Output: -1 
There is only 1 non decreasing sequence possible {1, 2, 3, 4}. 

Подход: отсортируйте данный массив и отслеживайте исходные индексы каждого элемента. Это дает одну требуемую перестановку. Теперь, если любые 2 непрерывных элемента равны, их можно поменять местами, чтобы получить другую перестановку. Аналогичным образом может быть сгенерирована третья перестановка.

Ниже представлена реализация описанного выше подхода:

Сложность времени: O (N log N + KN)

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.