Imprimir k diferentes permutaciones ordenadas de una array dada

Dada una array arr[] que contiene N enteros, la tarea es imprimir k permutaciones diferentes de índices de modo que los valores en esos índices formen una secuencia no decreciente. Imprime -1 si no es posible.

Ejemplos: 

Entrada: arr[] = {1, 3, 3, 1}, k = 3 
Salida: 
0 3 1 2 
3 0 1 2 
3 0 2 1 
Para cada permutación, los valores en los índices forman la siguiente secuencia {1, 1 , 3, 3}
Entrada: arr[] = {1, 2, 3, 4}, k = 3 
Salida: -1 
Solo hay 1 secuencia no decreciente posible {1, 2, 3, 4}. 

Enfoque: ordene la array dada y realice un seguimiento de los índices originales de cada elemento. Eso da una permutación requerida. Ahora, si 2 elementos continuos cualesquiera son iguales, entonces se pueden intercambiar para obtener otra permutación. De manera similar, se puede generar la tercera permutación.

A continuación se muestra la implementación del enfoque anterior: 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
int next_pos = 1;
// Utility function to print the original indices
// of the elements of the array
void printIndices(int n, pair<int, int> a[])
{
    for (int i = 0; i < n; i++)
        cout << a[i].second << " ";
    cout << endl;
}
 
// Function to print the required permutations
void printPermutations(int n, int a[], int k)
{
 
    // To keep track of original indices
    pair<int, int> arr[n];
    for (int i = 0; i < n; i++)
    {
        arr[i].first = a[i];
        arr[i].second = i;
    }
 
    // Sort the array
    sort(arr, arr + n);
 
    // Count the number of swaps that can
    // be made
    int count = 1;
    for (int i = 1; i < n; i++)
        if (arr[i].first == arr[i - 1].first)
            count++;
 
    // Cannot generate 3 permutations
    if (count < k) {
        cout << "-1";
        return;
    }
 
    for (int i = 0; i < k - 1; i++)
    {
        // Print the first permutation
        printIndices(n, arr);
 
        // Find an index to swap and create
        // second permutation
        for (int j = next_pos; j < n; j++)
        {
            if (arr[j].first == arr[j - 1].first)
            {
                swap(arr[j], arr[j - 1]);
                next_pos = j + 1;
                break;
            }
        }
    }
 
    // Print the last permutation
    printIndices(n, arr);
}
 
// Driver code
int main()
{
    int a[] = { 1, 3, 3, 1 };
    int n = sizeof(a) / sizeof(a[0]);
 
    int k = 3;
   
    // Function call
    printPermutations(n, a, k);
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
 
class GFG {
    static int next_pos = 1;
    static class pair {
        int first, second;
        pair()
        {
            first = 0;
            second = 0;
        }
    }
 
    // Utility function to print the original indices
    // of the elements of the array
    static void printIndices(int n, pair a[])
    {
        for (int i = 0; i < n; i++)
            System.out.print(a[i].second + " ");
        System.out.println();
    }
    static class sort implements Comparator<pair>
    {
        // Used for sorting in ascending order
        public int compare(pair a, pair b)
        {
            return a.first < b.first ? -1 : 1;
        }
    }
 
    // Function to print the required permutations
    static void printPermutations(int n, int a[], int k)
    {
 
        // To keep track of original indices
        pair arr[] = new pair[n];
        for (int i = 0; i < n; i++)
        {
            arr[i] = new pair();
            arr[i].first = a[i];
            arr[i].second = i;
        }
 
        // Sort the array
        Arrays.sort(arr, new sort());
 
        // Count the number of swaps that can
        // be made
        int count = 1;
        for (int i = 1; i < n; i++)
            if (arr[i].first == arr[i - 1].first)
                count++;
 
        // Cannot generate 3 permutations
        if (count < k)
        {
            System.out.print("-1");
            return;
        }
 
        for (int i = 0; i < k - 1; i++)
        {
            // Print the first permutation
            printIndices(n, arr);
 
            // Find an index to swap and create
            // second permutation
            for (int j = next_pos; j < n; j++)
            {
                if (arr[j].first == arr[j - 1].first)
                {
                    pair t = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = t;
 
                    next_pos = j + 1;
                    break;
                }
            }
        }
 
        // Print the last permutation
        printIndices(n, arr);
    }
 
    // Driver code
    public static void main(String arsg[])
    {
        int a[] = { 1, 3, 3, 1 };
        int n = a.length;
 
        int k = 3;
       
        // Function call
        printPermutations(n, a, k);
    }
}
 
// This code is contributed by Arnab Kundu

# Python 3 implementation of the approach
 
# Utility function to print the original
# indices of the elements of the array
 
 
def printIndices(n, a):
    for i in range(n):
        print(a[i][1], end=" ")
    print("\n", end="")
 
# Function to print the required
# permutations
 
 
def printPermutations(n, a, k):
 
    # To keep track of original indices
    arr = [[0, 0] for i in range(n)]
    for i in range(n):
        arr[i][0] = a[i]
        arr[i][1] = i
 
    # Sort the array
    arr.sort(reverse=False)
 
    # Count the number of swaps that
    # can be made
    count = 1
    for i in range(1, n):
        if (arr[i][0] == arr[i - 1][0]):
            count += 1
 
    # Cannot generate 3 permutations
    if (count < k):
        print("-1", end="")
        return
 
    next_pos = 1
    for i in range(k - 1):
 
        # Print the first permutation
        printIndices(n, arr)
 
        # Find an index to swap and create
        # second permutation
        for j in range(next_pos, n):
            if (arr[j][0] == arr[j - 1][0]):
                temp = arr[j]
                arr[j] = arr[j - 1]
                arr[j - 1] = temp
                next_pos = j + 1
                break
 
    # Print the last permutation
    printIndices(n, arr)
 
 
# Driver code
if __name__ == '__main__':
    a = [1, 3, 3, 1]
    n = len(a)
    k = 3
     
    # Function call
    printPermutations(n, a, k)
 
# This code is contributed by
# Surendra_Gangwar

// C# implementation of the approach
using System;
using System.Collections;
using System.Collections.Generic;
 
class GFG {
  static int next_pos = 1;
  public class pair {
    public int first, second;
    public pair()
    {
      first = 0;
      second = 0;
    }
  }
 
  class sortHelper : IComparer
  {
    int IComparer.Compare(object a, object b)
    {
      pair first = (pair)a;
      pair second = (pair)b;
      return first.first < second.first ? -1 : 1;
    }
  }
 
  // Utility function to print the original indices
  // of the elements of the array
  static void printIndices(int n, pair []a)
  {
    for (int i = 0; i < n; i++)
      Console.Write(a[i].second + " ");
    Console.WriteLine();
  }
 
  // Function to print the required permutations
  static void printPermutations(int n, int []a, int k)
  {
 
    // To keep track of original indices
    pair []arr = new pair[n];
    for (int i = 0; i < n; i++)
    {
      arr[i] = new pair();
      arr[i].first = a[i];
      arr[i].second = i;
    }
 
    // Sort the array
    Array.Sort(arr, new sortHelper());
 
    // Count the number of swaps that can
    // be made
    int count = 1;
    for (int i = 1; i < n; i++)
      if (arr[i].first == arr[i - 1].first)
        count++;
 
    // Cannot generate 3 permutations
    if (count < k)
    {
      Console.Write("-1");
      return;
    }
 
    for (int i = 0; i < k - 1; i++)
    {
 
      // Print the first permutation
      printIndices(n, arr);
 
      // Find an index to swap and create
      // second permutation
      for (int j = next_pos; j < n; j++)
      {
        if (arr[j].first == arr[j - 1].first)
        {
          pair t = arr[j];
          arr[j] = arr[j - 1];
          arr[j - 1] = t;
 
          next_pos = j + 1;
          break;
        }
      }
    }
 
    // Print the last permutation
    printIndices(n, arr);
  }
 
  // Driver code
  public static void Main(string []args)
  {
    int []a = { 1, 3, 3, 1 };
    int n = a.Length;
 
    int k = 3;
 
    // Function call
    printPermutations(n, a, k);
  }
}
 
// This code is contributed by rutvik_56.

<script>
 
// Javascript implementation of the approach
 
var next_pos = 1;
// Utility function to print the original indices
// of the elements of the array
function printIndices(n, a)
{
    for (var i = 0; i < n; i++)
        document.write( a[i][1] + " ");
    document.write("<br>");
}
 
// Function to print the required permutations
function printPermutations(n, a, k)
{
 
    // To keep track of original indices
    var arr = Array.from(Array(n), ()=>Array(2));
    for (var i = 0; i < n; i++)
    {
        arr[i][0] = a[i];
        arr[i][1] = i;
    }
 
    // Sort the array
    arr.sort();
 
    // Count the number of swaps that can
    // be made
    var count = 1;
    for (var i = 1; i < n; i++)
        if (arr[i][0] == arr[i - 1][0])
            count++;
 
    // Cannot generate 3 permutations
    if (count < k) {
        document.write( "-1");
        return;
    }
 
    for (var i = 0; i < k - 1; i++)
    {
        // Print the first permutation
        printIndices(n, arr);
 
        // Find an index to swap and create
        // second permutation
        for (var j = next_pos; j < n; j++)
        {
            if (arr[j][0] == arr[j - 1][0])
            {
                [arr[j], arr[j - 1]] = [arr[j - 1], arr[j]];
                next_pos = j + 1;
                break;
            }
        }
    }
 
    // Print the last permutation
    printIndices(n, arr);
}
 
// Driver code
var a = [1, 3, 3, 1];
var n = a.length;
var k = 3;
 
// Function call
printPermutations(n, a, k);
 
// This code is contributed by famously.
</script>

0 3 1 2 
3 0 1 2 
3 0 2 1 

Complejidad temporal: O(N log N + KN)