Given a range [L, R] where L ? R, the task is to generate a random permutation of the sequence [L, L + 1, L + 2, …, R].
Examples:
Input: L = 5, R = 15
Output: 11 9 6 5 8 7 10 12 13 15 14
Input: L = 10, R = 20
Output: 16 14 11 10 13 12 15 17 18 20 19
Approach: We will use Divide and Conquer algorithm for our solution. We will create a global vector that will store random numbers generated by our recursive function generate_random_permutation().
We will pass two arguments L (start) and R (end) to our recursive function. Inside the function it will call another function give_random_number that will return a number between X and Y. Lets call it N. We will store this random number in our vector and then we will call generate_random_permutation() function recursively for range [L, N – 1] and then for range [N + 1, R].
If L becomes greater than R then we will return from the function without performing any task, as this is our base condition.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // To store the random permutation vector< int > permutation; // Utility function to print // the generated permutation void printPermutation() { for ( auto i : permutation) cout << i << " " ; } // Function to return a random // number between x and y int give_random_number( int l, int r) { int x = rand () % (r - l + 1) + l; return x; } // Recursive function to generate // the random permutation void generate_random_permutation( int l, int r) { // Base condition if (l > r) return ; // Random number returned from the function int n = give_random_number(l, r); // Inserting random number in vector permutation.push_back(n); // Recursion call for [l, n - 1] generate_random_permutation(l, n - 1); // Recursion call for [n + 1, r] generate_random_permutation(n + 1, r); } // Driver code int main() { int l = 5; int r = 15; // Generate permutation generate_random_permutation(l, r); // Print the generated permutation printPermutation(); return 0; } |
Java
// Java implementation of the approach import java.util.Vector; class GFG { // To store the random permutation static Vector<Integer> permutation = new Vector<>(); // Utility function to print // the generated permutation static void printPermutation() { permutation.stream().forEach((i) -> { System.out.print(i+ " " ); }); } // Function to return a random // number between x and y static int give_random_number( int l, int r) { int x = ( int ) (Math.random()% (r - l + 1 ) + l); return x; } // Recursive function to generate // the random permutation static void generate_random_permutation( int l, int r) { // Base condition if (l > r) return ; // Random number returned from the function int n = give_random_number(l, r); // Inserting random number in vector permutation.add(n); // Recursion call for [l, n - 1] generate_random_permutation(l, n - 1 ); // Recursion call for [n + 1, r] generate_random_permutation(n + 1 , r); } // Driver code public static void main(String[] args) { int l = 5 ; int r = 15 ; // Generate permutation generate_random_permutation(l, r); // Print the generated permutation printPermutation(); } } // This code has been contributed by 29AjayKumar |
Python3
# Python3 implementation of the approach import random # To store the random permutation permutation = [] # Utility function to print # the generated permutation def printPermutation() : for i in permutation: print (i, end = " " ) # Function to return a random # number between x and y def give_random_number(l, r) : x = random.randint(l, r) return x # Recursive function to generate # the random permutation def generate_random_permutation(l, r) : # Base condition if (l > r) : return # Random number returned from the function n = give_random_number(l, r) # Inserting random number in vector permutation.append(n) # Recursion call for [l, n - 1] generate_random_permutation(l, n - 1 ) # Recursion call for [n + 1, r] generate_random_permutation(n + 1 , r) # Driver code l = 5 r = 15 # Generate permutation generate_random_permutation(l, r) # Print the generated permutation printPermutation() # This code is contributed by ihritik |
C#
// C# implementation of the approach using System; using System.Collections.Generic; class GFG { // To store the random permutation static List< int > permutation = new List< int >(); // Utility function to print // the generated permutation static void printPermutation() { foreach ( int i in permutation) Console.Write(i+ " " ); } // Function to return a random // number between x and y static int give_random_number( int l, int r) { Random rnd = new Random(); int num = rnd.Next(l, r); int x = ( int ) (num % (r - l + 1) + l); return x; } // Recursive function to generate // the random permutation static void generate_random_permutation( int l, int r) { // Base condition if (l > r) return ; // Random number returned from the function int n = give_random_number(l, r); // Inserting random number in vector permutation.Add(n); // Recursion call for [l, n - 1] generate_random_permutation(l, n - 1); // Recursion call for [n + 1, r] generate_random_permutation(n + 1, r); } // Driver code public static void Main(String[] args) { int l = 5; int r = 15; // Generate permutation generate_random_permutation(l, r); // Print the generated permutation printPermutation(); } } /* This code contributed by PrinciRaj1992 */ |
PHP
<?php // PHP implementation of the approach // To store the random permutation $permutation = array (); // Utility function to print // the generated permutation function printPermutation() { global $permutation ; foreach ( $permutation as $i ) echo $i . " " ; } // Function to return a random // number between x and y function give_random_number( $l , $r ) { $x = rand() % ( $r - $l + 1) + $l ; return $x ; } // Recursive function to generate // the random permutation function generate_random_permutation( $l , $r ) { global $permutation ; // Base condition if ( $l > $r ) return ; // Random number returned from the function $n = give_random_number( $l , $r ); // Inserting random number in vector array_push ( $permutation , $n ); // Recursion call for [l, n - 1] generate_random_permutation( $l , $n - 1); // Recursion call for [n + 1, r] generate_random_permutation( $n + 1, $r ); } // Driver code $l = 5; $r = 15; // Generate permutation generate_random_permutation( $l , $r ); // Print the generated permutation printPermutation(); // This code is contributed by mits ?> |
Javascript
<script> // Javascript implementation of the approach // To store the random permutation var permutation = []; // Utility function to print // the generated permutation function printPermutation() { for ( var i of permutation) document.write(i + " " ); } // Function to return a random // number between x and y function give_random_number(l, r) { var x = Math.floor(Math.random() * l + r) % (r - l + 1) + l; return x; } // Recursive function to generate // the random permutation function generate_random_permutation(l, r) { // Base condition if (l > r) return ; // Random number returned from the function var n = give_random_number(l, r); // Inserting random number in vector permutation.push(n); // Recursion call for [l, n - 1] generate_random_permutation(l, n - 1); // Recursion call for [n + 1, r] generate_random_permutation(n + 1, r); } // Driver code var l = 5; var r = 15; // Generate permutation generate_random_permutation(l, r); // Print the generated permutation printPermutation(); // This code is contributed by rrrtnx. </script> |
11 9 6 5 8 7 10 12 13 15 14
Time Complexity: O(n)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!