Print k different sorted permutations of a given array

0 0 6 minutes read

Given an array arr[] containing N integers, the task is to print k different permutations of indices such that the values at those indices form a non-decreasing sequence. Print -1 if it is not possible.

Examples:

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

Approach: Sort the given array and keep track of the original indices of each element. That gives one required permutation. Now if any 2 continuous elements are equal then they can be swapped to get another permutation. Similarly, the third permutation can be generated.

Below is the implementation of the above approach:

C++

// 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

// 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

Python3

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

// 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.

Javascript

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

Output

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

Time Complexity: O(N log N + K N)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!