Dado un rango [L, R] donde L ≤ R , la tarea es generar una permutación aleatoria de la secuencia [L, L + 1, L + 2, …, R] .
Ejemplos:
Entrada: L = 5, R = 15
Salida: 11 9 6 5 8 7 10 12 13 15 14
Entrada: L = 10, R = 20
Salida: 16 14 11 10 13 12 15 17 18 20 19
Enfoque: Usaremos el algoritmo Divide and Conquer para nuestra solución. Crearemos un vector global que almacenará números aleatorios generados por nuestra función recursiva generate_random_permutation() .
Pasaremos dos argumentos L (inicio) y R (final) a nuestra función recursiva. Dentro de la función llamará a otra función dar_número_aleatorio que devolverá un número entre X e Y. Llamémoslo N. _ Guardaremos este número aleatorio en nuestro vector y luego llamaremos recursivamente a la función generate_random_permutation() para el rango [L, N – 1]y luego para el rango [N + 1, R] .
Si L se vuelve mayor que R , regresaremos de la función sin realizar ninguna tarea, ya que esta es nuestra condición base.
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
11 9 6 5 8 7 10 12 13 15 14
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por saurabh_dtu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA