Generar una permutación aleatoria de 1 a N

Dado un número entero N , la tarea es generar N números aleatorios que no se repiten.

Ejemplos:  

Entrada: N = 5 
Salida: 1 5 2 4 3

Entrada: N = 8 
Salida: 7 2 1 8 3 6 4 5 

Enfoque: cree una array de N elementos e inicialice los elementos como 1, 2, 3, 4, …, N y luego mezcle los elementos de la array utilizando el algoritmo de reproducción aleatoria de Fisher-Yates.

El algoritmo aleatorio de Fisher-Yates funciona en una complejidad de tiempo O(n). La suposición aquí es que se nos da una función rand() que genera un número aleatorio en tiempo O(1). 

La idea es comenzar desde el último elemento, intercambiarlo con un elemento seleccionado al azar de toda la array (incluido el último). Ahora considere la array de 0 a n-2 (tamaño reducido en 1) y repita el proceso hasta que lleguemos al primer elemento. 

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

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the next random number
int getNum(vector<int>& v)
{
 
    // Size of the vector
    int n = v.size();
 
    // Generate a random number
    srand(time(NULL));
 
    // Make sure the number is within
    // the index range
    int index = rand() % n;
 
    // Get random number from the vector
    int num = v[index];
 
    // Remove the number from the vector
    swap(v[index], v[n - 1]);
    v.pop_back();
 
    // Return the removed number
    return num;
}
 
// Function to generate n non-repeating random numbers
void generateRandom(int n)
{
    vector<int> v(n);
 
    // Fill the vector with the values
    // 1, 2, 3, ..., n
    for (int i = 0; i < n; i++)
        v[i] = i + 1;
 
    // While vector has elements
    // get a random number from the vector and print it
    while (v.size()) {
        cout << getNum(v) << " ";
    }
}
 
// Driver code
int main()
{
    int n = 8;
    generateRandom(n);
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
import java.lang.Math;
 
class GfG
{
 
    // Function to return the next random number
    static int getNum(ArrayList<Integer> v)
    {
        // Size of the vector
        int n = v.size();
     
        // Make sure the number is within
        // the index range
        int index = (int)(Math.random() * n);
     
        // Get random number from the vector
        int num = v.get(index);
     
        // Remove the number from the vector
        v.set(index, v.get(n - 1));
        v.remove(n - 1);
     
        // Return the removed number
        return num;
    }
     
    // Function to generate n
    // non-repeating random numbers
    static void generateRandom(int n)
    {
        ArrayList<Integer> v = new ArrayList<>(n);
     
        // Fill the vector with the values
        // 1, 2, 3, ..., n
        for (int i = 0; i < n; i++)
            v.add(i + 1);
     
        // While vector has elements
        // get a random number from the vector and print it
        while (v.size() > 0)
        {
            System.out.print(getNum(v) + " ");
        }
    }
 
    // Driver code
    public static void main(String []args)
    {
         
        int n = 8;
        generateRandom(n);
    }
}
 
// This code is contributed by Rituraj Jain

# Python3 implementation of the approach
 
# import random module
import random
 
# Function to return the next
# random number
def getNum(v) :
 
    # Size of the vector
    n = len(v)
 
    # Generate a random number within
    # the index range
    index = random.randint(0, n - 1)
 
    # Get random number from the vector
    num = v[index]
 
    # Remove the number from the vector
    v[index], v[n - 1] = v[n - 1], v[index]
    v.pop()
 
    # Return the removed number
    return num
 
# Function to generate n non-repeating
# random numbers
def generateRandom(n) :
     
    v = [0] * n
 
    # Fill the vector with the values
    # 1, 2, 3, ..., n
    for i in range(n) :
        v[i] = i + 1
 
    # While vector has elements get a 
    # random number from the vector
    # and print it
    while (len(v)) :
        print(getNum(v), end = " ")
 
# Driver code
if __name__ == "__main__" :
     
    n = 8
    generateRandom(n)
     
# This code is contributed by Ryuga

// C# implementation of the approach
using System;
using System.Collections;
 
class GfG{
  
// Function to return the next random number
static int getNum(ArrayList v)
{
     
    // Size of the vector
    int n = v.Count;
     
    Random rand = new Random();
     
    // Make sure the number is within
    // the index range
    int index = (rand.Next() % n);
  
    // Get random number from the vector
    int num = (int)v[index];
  
    // Remove the number from the vector
    v[index] = (int)v[n - 1];
    v.Remove(v[n - 1]);
  
    // Return the removed number
    return num;
}
  
// Function to generate n
// non-repeating random numbers
static void generateRandom(int n)
{
    ArrayList v = new ArrayList(n);
     
    // Fill the vector with the values
    // 1, 2, 3, ..., n
    for(int i = 0; i < n; i++)
        v.Add(i + 1);
  
    // While vector has elements get a
    // random number from the vector
    // and print it
    while (v.Count > 0)
    {
        Console.Write(getNum(v) + " ");
    }
}
 
// Driver code
public static void Main(string []args)
{
    int n = 8;
     
    generateRandom(n);
}
}
 
// This code is contributed by rutvik_56

<?php
// PHP implementation of the approach
 
// Function to return the next random number
function getNum(&$v)
{
 
    // Size of the vector
    $n = sizeof($v);
 
    // Generate a random number
    srand(time(NULL));
 
    // Make sure the number is within
    // the index range
    $index = rand() % $n;
 
    // Get random number from the vector
    $num = $v[$index];
 
    // Remove the number from the vector
    $t = $v[$index];
    $v[$index] = $v[$n - 1];
    $v[$n - 1] = $t;
    array_pop($v);
 
    // Return the removed number
    return $num;
}
 
// Function to generate n non-repeating
// random numbers
function generateRandom($n)
{
    $v = array(0, $n, NULL);
 
    // Fill the vector with the values
    // 1, 2, 3, ..., n
    for ($i = 0; $i < $n; $i++)
        $v[$i] = $i + 1;
 
    // While vector has elements
    // get a random number from the
    // vector and print it
    while (sizeof($v))
    {
        echo getNum($v) . " ";
    }
}
 
// Driver code
$n = 8;
generateRandom($n);
 
// This code is contributed by ita_c
?>

<script>
// Javascript implementation of the approach
 
// Function to return the next random number
function getNum(v)
{
        // Size of the vector
        let n = v.length;
      
        // Make sure the number is within
        // the index range
        let index = Math.floor(Math.random() % n);
          
        // Get random number from the vector
        let num = v[index];
      
        // Remove the number from the vector
        v[index] = v[n - 1];
        v.splice(n - 1,1);
      
        // Return the removed number
        return num;
}
 
// Function to generate n
// non-repeating random numbers
function generateRandom(n)
{
        let v = [];
      
        // Fill the vector with the values
        // 1, 2, 3, ..., n
        for (let i = 0; i < n; i++)
            v.push(i + 1);
      
        // While vector has elements
        // get a random number from the vector and print it
        while (v.length > 0)
        {
            document.write(getNum(v) + " ");
        }
}
 
// Driver code
let n = 8;
generateRandom(n);
 
 
// This code is contributed by rag2127
</script>

3 4 5 8 6 2 1 7