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 arrayvoid 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 permutationsvoid 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 codeint 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 approachimport 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 arraydef printIndices(n, a): for i in range(n): print(a[i][1], end=" ") print("\n", end="")# Function to print the required# permutationsdef 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 codeif __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 approachusing 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 approachvar next_pos = 1;// Utility function to print the original indices// of the elements of the arrayfunction printIndices(n, a){ for (var i = 0; i < n; i++) document.write( a[i][1] + " "); document.write("<br>");}// Function to print the required permutationsfunction 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 codevar a = [1, 3, 3, 1];var n = a.length;var k = 3;// Function callprintPermutations(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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
