洗牌算法原理与实现

给定一副扑克牌，我们的任务是将它们打乱。这个问题也是亚马逊面试中出现过的一道题目。

在开始之前，我们需要了解一个基础知识：如何打乱一个给定的数组。

算法思路

1. 首先，按顺序填充数组。
2. 遍历数组，将每个元素与其自身到末尾范围内
   随机选择的一个元素进行交换。

// 元素可能会与自身交换，但这完全没有问题。

下面是具体的代码实现。

#### C++ 实现

// C++ program for shuffling desk of cards.
#include 
using namespace std;

// Function which shuffle and print the array
void shuffle(int card[], int n)
{
    // Initialize seed randomly
    srand(time(0));

    for (int i=0; i<n ;i++)
    {
        // Random for remaining positions.
        int r = i + (rand() % (52 -i));

        swap(card[i], card[r]);
    }
}

// Driver code
int main()
{
    // Array from 0 to 51
    int a[] = {0, 1, 2, 3, 4, 5, 6, 7, 8,
               9, 10, 11, 12, 13, 14, 15,
               16, 17, 18, 19, 20, 21, 22,
               23, 24, 25, 26, 27, 28, 29,
               30, 31, 32, 33, 34, 35, 36,
               37, 38, 39, 40, 41, 42, 43,
               44, 45, 46, 47, 48, 49, 50,
               51};

    shuffle(a, 52);

    // Printing all shuffled elements of cards
    for (int i=0; i<52; i++)
        cout << a[i] << " ";
    cout << endl;

    return 0;
}

#### Java 实现

// Java Code for Shuffle a deck of cards
import java.util.Random;

class GFG {
    
    // Function which shuffle and print the array
    public static void shuffle(int card[], int n)
    {
        
        Random rand = new Random();
        
        for (int i = 0; i < n; i++)
        {
            // Random for remaining positions.
            int r = i + rand.nextInt(52 - i);
            
             //swapping the elements
             int temp = card[r];
             card[r] = card[i];
             card[i] = temp;
             
        }
    }
     
    // Driver code
    public static void main(String[] args) 
    {
        // Array from 0 to 51
        int a[] = {0, 1, 2, 3, 4, 5, 6, 7, 8,
                   9, 10, 11, 12, 13, 14, 15,
                   16, 17, 18, 19, 20, 21, 22,
                   23, 24, 25, 26, 27, 28, 29,
                   30, 31, 32, 33, 34, 35, 36,
                   37, 38, 39, 40, 41, 42, 43,
                   44, 45, 46, 47, 48, 49, 50, 
                   51};
     
        shuffle(a, 52);
     
        // Printing all shuffled elements of cards
        for (int i = 0; i < 52; i ++)
           System.out.print(a[i]+" ");
        
    }
}
// This code is contributed by Arnav Kr. Mandal

#### Python3 实现

# Python3 program for shuffling desk of cards
# Function which shuffle and print the array 

import random
def shuffle(card,n) :
    
    # Initialize seed randomly
    for i in range(n):
        
        # Random for remaining positions.
        r = i + (random.randint(0,55) % (52 -i))
        tmp=card[i]
        card[i]=card[r]
        card[r]=tmp
#Driver code
if __name__==‘__main__‘:
    a=[0, 1, 2, 3, 4, 5, 6, 7, 8,
       9, 10, 11, 12, 13, 14, 15,
       16, 17, 18, 19, 20, 21, 22, 
       23, 24, 25, 26, 27, 28, 29,
       30, 31, 32, 33, 34, 35, 36,
       37, 38, 39, 40, 41, 42, 43, 
       44, 45, 46, 47, 48, 49, 50,
       51]
    shuffle(a,52)
    print(a)
       
#this code is contributed by sahilshelangia

#### C# 实现

// C# Code for Shuffle a deck of cards
using System;

class GFG {
    
    // Function which shuffle and 
    // print the array
    public static void shuffle(int []card, 
                               int n)
    {
        
        Random rand = new Random();
        
        for (int i = 0; i < n; i++)
        {
            
            // Random for remaining positions.
            int r = i + rand.Next(52 - i);
            
            //swapping the elements
            int temp = card[r];
            card[r] = card[i];
            card[i] = temp;
            
        }
    }
    
    // Driver code
    public static void Main() 
    {
        // Array from 0 to 51
        int []a = {0, 1, 2, 3, 4, 5, 6, 7, 8,
                   9, 10, 11, 12, 13, 14, 15,
                   16, 17, 18, 19, 20, 21, 22,
                   23, 24, 25, 26, 27, 28, 29,
                   30, 31, 32, 33, 34, 35, 36,
                   37, 38, 39, 40, 41, 42, 43,
                   44, 45, 46, 47, 48, 49, 50, 
                   51};
    
        shuffle(a, 52);
    
        // Printing all shuffled elements of cards
        for (int i = 0; i < 52; i ++)
        Console.Write(a[i]+" ");
        
    }
}

// This code is contributed by Nitin Mittal.

#### JavaScript 实现

// JavaScript Implementation of the above approach

// Function which shuffle and print the array
function shuffle(card, n)
{
    // Initialize seed randomly
    for (let i = 0; i < n; i++)
    {
        // Random for remaining positions.
        let r = i + Math.floor(Math.random() * (52 - i));
        
        // Swapping elements
        let temp = card[r];
        card[r] = card[i];
        card[i] = temp;
    }
}

// Driver code
let a = [0, 1, 2, 3, 4, 5, 6, 7, 8,
         9, 10, 11, 12, 13, 14, 15,
         16, 17, 18, 19, 20, 21, 22, 
         23, 24, 25, 26, 27, 28, 29,
         30, 31, 32, 33, 34, 35, 36,
         37, 38, 39, 40, 41, 42, 43, 
         44, 45, 46, 47, 48, 49, 50,
         51];

shuffle(a, 52);

// Printing all shuffled elements
console.log(a);

在这个实现中，我们通过随机交换数组中的元素来模拟洗牌的过程，确保每种排列出现的概率相等。