使用Fisher–Yates洗牌算法洗牌给定数组-yiteyi-C++库

给定一个数组，编写一个程序来生成数组元素的随机排列。这个问题也被称为“洗牌”或“随机化给定的数组”。这里，shuffle意味着数组元素的每一个排列都应该具有相同的可能性。

null

shuffle-array

让给定的数组 arr[] .一个简单的解决方案是创建一个辅助数组 温度[] 它最初是 arr[] .从中随机选择一个元素 温度[] ，将随机选择的元素复制到 arr[0] 并从中删除选定的元素 温度[] .重复相同的过程n次，并将元素复制到 arr[1]，arr[2]。 此解决方案的时间复杂度为O（n^2）。 Fisher-Yates洗牌算法在O（n）时间复杂度下工作。这里的假设是，我们得到了一个函数rand（），它在O（1）时间内生成随机数。其想法是从最后一个元素开始，将其与整个数组（包括最后一个）中随机选择的元素交换。现在考虑数组从0到n-2（大小减少了1），并重复这个过程直到我们碰到第一个元素。下面是详细的算法

To shuffle an array a of n elements (indices 0..n-1):  for i from n - 1 downto 1 do       j = random integer with 0 <= j <= i       exchange a[j] and a[i]

下面是该算法的实现。

C++

                         // C++ Program to shuffle a given array                       
                         #include<bits/stdc++.h>                       
                         #include <stdlib.h>                       
                         #include <time.h>                       
                         using                                     namespace                                     std;                       
           
                         // A utility function to swap to integers                       
                         void                                     swap (                                     int                                     *a,                                     int                                     *b)                       
                         {                       
                                                 int                                     temp = *a;                       
                                                 *a = *b;                       
                                                 *b = temp;                       
                         }                       
           
                         // A utility function to print an array                       
                         void                                     printArray (                                     int                                     arr[],                                     int                                     n)                       
                         {                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 cout << arr[i] <<                                     " "                                     ;                       
                                                 cout <<                                     ""                                     ;                       
                         }                       
           
                         // A function to generate a random                       
                         // permutation of arr[]                       
                         void                                     randomize (                                     int                                     arr[],                                     int                                     n)                       
                         {                       
                                                 // Use a different seed value so that                       
                                                 // we don't get same result each time                       
                                                 // we run this program                       
                                                 srand                                     (                                     time                                     (NULL));                       
           
                                                 // Start from the last element and swap                       
                                                 // one by one. We don't need to run for                       
                                                 // the first element that's why i > 0                       
                                                 for                                     (                                     int                                     i = n - 1; i > 0; i--)                       
                                                 {                       
                                                 // Pick a random index from 0 to i                       
                                                 int                                     j =                                     rand                                     () % (i + 1);                       
           
                                                 // Swap arr[i] with the element                       
                                                 // at random index                       
                                                 swap(&arr[i], &arr[j]);                       
                                                 }                       
                         }                       
           
                         // Driver Code                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = {1, 2, 3, 4, 5, 6, 7, 8};                       
                                                 int                                     n =                                     sizeof                                     (arr) /                                     sizeof                                     (arr[0]);                       
                                                 randomize (arr, n);                       
                                                 printArray(arr, n);                       
           
                                                 return                                     0;                       
                         }                       
           
                         // This code is contributed by                       
                         // rathbhupendra                       

C

                         // C Program to shuffle a given array                       
           
                         #include <stdio.h>                       
                         #include <stdlib.h>                       
                         #include <time.h>                       
           
                         // A utility function to swap to integers                       
                         void                                     swap (                                     int                                     *a,                                     int                                     *b)                       
                         {                       
                                                 int                                     temp = *a;                       
                                                 *a = *b;                       
                                                 *b = temp;                       
                         }                       
           
                         // A utility function to print an array                       
                         void                                     printArray (                                     int                                     arr[],                                     int                                     n)                       
                         {                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 printf                                     (                                     "%d "                                     , arr[i]);                       
                                                 printf                                     (                                     ""                                     );                       
                         }                       
           
                         // A function to generate a random permutation of arr[]                       
                         void                                     randomize (                                     int                                     arr[],                                     int                                     n )                       
                         {                       
                                                 // Use a different seed value so that we don't get same                       
                                                 // result each time we run this program                       
                                                 srand                                     (                                     time                                     (NULL) );                       
           
                                                 // Start from the last element and swap one by one. We don't                       
                                                 // need to run for the first element that's why i > 0                       
                                                 for                                     (                                     int                                     i = n-1; i > 0; i--)                       
                                                 {                       
                                                 // Pick a random index from 0 to i                       
                                                 int                                     j =                                     rand                                     () % (i+1);                       
           
                                                 // Swap arr[i] with the element at random index                       
                                                 swap(&arr[i], &arr[j]);                       
                                                 }                       
                         }                       
           
                         // Driver program to test above function.                       
                         int                                     main()                       
                         {                       
                                                 int                                     arr[] = {1, 2, 3, 4, 5, 6, 7, 8};                       
                                                 int                                     n =                                     sizeof                                     (arr)/                                     sizeof                                     (arr[0]);                       
                                                 randomize (arr, n);                       
                                                 printArray(arr, n);                       
           
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java Program to shuffle a given array                       
                         import                                     java.util.Random;                       
                         import                                     java.util.Arrays;                       
                         public                                     class                                     ShuffleRand                       
                         {                       
                                                 // A Function to generate a random permutation of arr[]                       
                                                 static                                     void                                     randomize(                                     int                                     arr[],                                     int                                     n)                       
                                                 {                       
                                                 // Creating a object for Random class                       
                                                 Random r =                                     new                                     Random();                       
                                   
                                                 // Start from the last element and swap one by one. We don't                       
                                                 // need to run for the first element that's why i > 0                       
                                                 for                                     (                                     int                                     i = n-                                     1                                     ; i >                                     0                                     ; i--) {                       
                                   
                                                 // Pick a random index from 0 to i                       
                                                 int                                     j = r.nextInt(i+                                     1                                     );                       
                                   
                                                 // Swap arr[i] with the element at random index                       
                                                 int                                     temp = arr[i];                       
                                                 arr[i] = arr[j];                       
                                                 arr[j] = temp;                       
                                                 }                       
                                                 // Prints the random array                       
                                                 System.out.println(Arrays.toString(arr));                       
                                                 }                       
                                   
                                                 // Driver Program to test above function                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                   
                                                 int                                     [] arr = {                                     1                                     ,                                     2                                     ,                                     3                                     ,                                     4                                     ,                                     5                                     ,                                     6                                     ,                                     7                                     ,                                     8                                     };                       
                                                 int                                     n = arr.length;                       
                                                 randomize (arr, n);                       
                                                 }                       
                         }                       
                         // This code is contributed by Sumit Ghosh                       

Python3

                         # Python Program to shuffle a given array                       
                         from                                     random                                     import                                     randint                       
           
                         # A function to generate a random permutation of arr[]                       
                         def                                     randomize (arr, n):                       
                                                 # Start from the last element and swap one by one. We don't                       
                                                 # need to run for the first element that's why i > 0                       
                                                 for                                     i                                     in                                     range                                     (n                                     -                                     1                                     ,                                     0                                     ,                                     -                                     1                                     ):                       
                                                 # Pick a random index from 0 to i                       
                                                 j                                     =                                     randint(                                     0                                     ,i                                     +                                     1                                     )                       
           
                                                 # Swap arr[i] with the element at random index                       
                                                 arr[i],arr[j]                                     =                                     arr[j],arr[i]                       
                                                 return                                     arr                       
           
                         # Driver program to test above function.                       
                         arr                                     =                                     [                                     1                                     ,                                     2                                     ,                                     3                                     ,                                     4                                     ,                                     5                                     ,                                     6                                     ,                                     7                                     ,                                     8                                     ]                       
                         n                                     =                                     len                                     (arr)                       
                         print                                     (randomize(arr, n))                       
           
           
                         # This code is contributed by Pratik Chhajer                       

C#

                         // C# Code for Number of digits                       
                         // in the product of two numbers                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
                         // A Function to generate a                       
                         // random permutation of arr[]                       
                                                 static                                     void                                     randomize(                                     int                                     []arr,                                     int                                     n)                       
                                                 {                       
                                                 // Creating a object                       
                                                 // for Random class                       
                                                 Random r =                                     new                                     Random();                       
                                   
                                                 // Start from the last element and                       
                                                 // swap one by one. We don't need to                       
                                                 // run for the first element                       
                                                 // that's why i > 0                       
                                                 for                                     (                                     int                                     i = n - 1; i > 0; i--)                       
                                                 {                       
                                   
                                                 // Pick a random index                       
                                                 // from 0 to i                       
                                                 int                                     j = r.Next(0, i+1);                       
                                   
                                                 // Swap arr[i] with the                       
                                                 // element at random index                       
                                                 int                                     temp = arr[i];                       
                                                 arr[i] = arr[j];                       
                                                 arr[j] = temp;                       
                                                 }                       
                                                 // Prints the random array                       
                                                 for                                     (                                     int                                     i = 0; i < n; i++)                       
                                                 Console.Write(arr[i] +                                     " "                                     );                       
                                                 }                       
                                   
                                   
                         // Driver Code                       
                         static                                     void                                     Main()                       
                         {                       
                                                 int                                     [] arr = {1, 2, 3, 4,                       
                                                 5, 6, 7, 8};                       
                                                 int                                     n = arr.Length;                       
                                                 randomize (arr, n);                       
                         }                       
                         }                       
           
                         // This code is contributed by Sam007                       

PHP

                         <?php                       
                         // PHP Program to shuffle                       
                         // a given array                       
           
                         // A function to generate                       
                         // a random permutation of arr[]                       
                         function                                     randomize (                                     $arr                                     ,                                     $n                                     )                       
                         {                       
                                                 // Start from the last element                       
                                                 // and swap one by one. We                       
                                                 // don't need to run for the                       
                                                 // first element that's why i > 0                       
                                                 for                                     (                                     $i                                     =                                     $n                                     - 1;                                     $i                                     >= 0;                                     $i                                     --)                       
                                                 {                       
                                                 // Pick a random index                       
                                                 // from 0 to i                       
                                                 $j                                     = rand(0,                                     $i                                     +1);                       
           
                                                 // Swap arr[i] with the                       
                                                 // element at random index                       
                                                 $tmp                                     =                                     $arr                                     [                                     $i                                     ];                       
                                                 $arr                                     [                                     $i                                     ] =                                     $arr                                     [                                     $j                                     ];                       
                                                 $arr                                     [                                     $j                                     ] =                                     $tmp                                     ;                       
                                                 }                       
                                                 for                                     (                                     $i                                     = 0;                                     $i                                     <                                     $n                                     ;                                     $i                                     ++)                       
                                                 echo                                     $arr                                     [                                     $i                                     ].                                     " "                                     ;                       
                         }                       
           
                         // Driver Code                       
                         $arr                                     =                                     array                                     (1, 2, 3, 4,                       
                                                 5, 6, 7, 8);                       
                         $n                                     =                                     count                                     (                                     $arr                                     );                       
                         randomize(                                     $arr                                     ,                                     $n                                     );                       
           
                         // This code is contributed by mits                       
                         ?>                       

Javascript

                         <script>                       
                         // JavaScript Program to shuffle a given array                       
           
                         // A function to print an array                       
                         let printArray = (arr, n)=>                       
                         {                       
                                                 ans =                                     ''                                     ;                       
                                                 for                                     (let i = 0; i < n; i++)                       
                                                 {                       
                                                 ans += arr[i] +                                     " "                                     ;                       
                                                 }                       
                                                 console.log(ans);                       
                         }                       
           
                         // A function to generate a random                       
                         // permutation of arr                       
                         let randomize = (arr, n) =>                       
                         {                       
           
                                                 // Start from the last element and swap                       
                                                 // one by one. We don't need to run for                       
                                                 // the first element that's why i > 0                       
                                                 for                                     (let i = n - 1; i > 0; i--)                       
                                                 {                       
                                   
                                                 // Pick a random index from 0 to i inclusive                       
                                                 let j = Math.floor(Math.random() * (i + 1));                       
           
                                                 // Swap arr[i] with the element                       
                                                 // at random index                       
                                                 [arr[i], arr[j]] = [arr[j], arr[i]];                       
                                                 }                       
                         }                       
           
                         // Driver Code                       
                         let arr = [1, 2, 3, 4, 5, 6, 7, 8];                       
                         let n = arr.length;                       
                         randomize (arr, n);                       
                         printArray(arr, n);                       
           
                         // This code is contributed by rohitsingh07052.                       
                         </script>                       

输出：

7 8 4 6 3 1 2 5

上述函数假设rand（）生成一个随机数。 时间复杂性： O（n），假设函数rand（）需要O（1）个时间。

辅助空间： O（1） 这是怎么回事？ 第i个元素（包括最后一个元素）到达最后一个位置的概率是1/n，因为我们在第一次迭代中随机选取一个元素。通过将第i个元素除以两种情况，可以证明第i个元素到达倒数第二位的概率为1/n。 案例1：i=n-1（最后一个元素的索引） : 最后一个元素进入倒数第二个位置的概率为=（最后一个元素没有停留在其原始位置的概率）x（再次拾取上一步中拾取的索引以便交换最后一个元素的概率）所以概率=（（n-1）/n）x（1/（n-1））=1/n 案例2:0 : 第i个元素进入第二位置的概率=（第i个元素在上一次迭代中未被拾取的概率）x（第i个元素在本次迭代中被拾取的概率）所以概率=（（n-1）/n）x（1/（n-1））=1/n 我们可以很容易地将上述证明推广到任何其他位置。

?list=PLqM7alHXFySEQDk2MDfbwEdjd2svVJH9p 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章