抽獎 Fisher-Yates Shuffle(費雪-耶茲洗牌演算法)
引言
問
答
using System;
using System.Collections.Generic;
using System.Security.Cryptography;
namespace LotterySystem
{
public class FisherYatesLottery : IDisposable
{
private readonly Random _random;
private readonly RandomNumberGenerator _cryptoRandom;
private bool _disposed = false;
public FisherYatesLottery()
{
// 使用系統時間作為種子
_random = new Random();
// 使用密碼學安全的隨機數產生器（更適合重要抽獎）
_cryptoRandom = RandomNumberGenerator.Create();
}
/// <summary>
/// Fisher-Yates Shuffle 標準實作
/// </summary>
/// <typeparam name="T">陣列元素類型</typeparam>
/// <param name="array">要洗牌的陣列</param>
public void Shuffle<T>(T[] array)
{
if (array == null || array.Length <= 1)
return;
// 從最後一個元素開始，向前遍歷
for (int i = array.Length - 1; i > 0; i--)
{
// 在 0 到 i（包含）之間選擇隨機索引
int j = _random.Next(i + 1);
// 交換元素
(array[i], array[j]) = (array[j], array[i]);
}
}
/// <summary>
/// 使用密碼學安全隨機數的 Fisher-Yates Shuffle
/// 適用於需要高安全性的抽獎
/// </summary>
/// <typeparam name="T">陣列元素類型</typeparam>
/// <param name="array">要洗牌的陣列</param>
public void SecureShuffle<T>(T[] array)
{
ObjectDisposedException.ThrowIf(_disposed, this);
if (array == null || array.Length <= 1)
return;
for (int i = array.Length - 1; i > 0; i--)
{
int j = GetSecureRandomInt(i + 1);
(array[i], array[j]) = (array[j], array[i]);
}
}
/// <summary>
/// 產生密碼學安全的隨機整數
/// </summary>
/// <param name="maxValue">最大值（不包含）</param>
/// <returns>0 到 maxValue-1 之間的隨機整數</returns>
private int GetSecureRandomInt(int maxValue)
{
ObjectDisposedException.ThrowIf(_disposed, this);
if (maxValue <= 1) return 0;
byte[] bytes = new byte[4];
int result;
do
{
_cryptoRandom.GetBytes(bytes);
result = Math.Abs(BitConverter.ToInt32(bytes, 0));
} while (result >= int.MaxValue - (int.MaxValue % maxValue));
return result % maxValue;
}
/// <summary>
/// 進行抽獎，返回指定數量的中獎者
/// </summary>
/// <typeparam name="T">參與者類型</typeparam>
/// <param name="participants">參與者列表</param>
/// <param name="winnerCount">中獎人數</param>
/// <param name="useSecureRandom">是否使用密碼學安全隨機數</param>
/// <returns>中獎者陣列</returns>
public T[] DrawLottery<T>(IEnumerable<T> participants, int winnerCount, bool useSecureRandom = false)
{
var participantArray = participants.ToArray();
if (participantArray.Length == 0)
return Array.Empty<T>();
if (winnerCount >= participantArray.Length)
return participantArray;
// 洗牌
if (useSecureRandom)
SecureShuffle(participantArray);
else
Shuffle(participantArray);
// 取前 winnerCount 個作為中獎者
var winners = new T[winnerCount];
Array.Copy(participantArray, winners, winnerCount);
return winners;
}
public void Dispose()
{
Dispose(true);
GC.SuppressFinalize(this);
}
protected virtual void Dispose(bool disposing)
{
if (!_disposed && disposing)
{
_cryptoRandom?.Dispose();
_disposed = true;
}
}
/// <summary>
/// 檢查物件是否已釋放
/// </summary>
protected void ThrowIfDisposed()
{
ObjectDisposedException.ThrowIf(_disposed, this);
}
}
// 示範用的參與者類別
public record Participant(int Id, string Name, string Email);
// 主程式示範
public class Program
{
public static void Main(string[] args)
{
var lottery = new FisherYatesLottery();
try
{
// 示範 1: 基本洗牌
Console.WriteLine("=== 基本 Fisher-Yates Shuffle 示範 ===");
int[] numbers = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
Console.WriteLine($"原始順序: [{string.Join(", ", numbers)}]");
lottery.Shuffle(numbers);
Console.WriteLine($"洗牌後: [{string.Join(", ", numbers)}]");
// 示範 2: 參與者抽獎
Console.WriteLine("\n=== 抽獎示範 ===");
var participants = new List<Participant>
{
new(1, "張三", "zhang@example.com"),
new(2, "李四", "li@example.com"),
new(3, "王五", "wang@example.com"),
new(4, "趙六", "zhao@example.com"),
new(5, "孫七", "sun@example.com"),
new(6, "周八", "zhou@example.com"),
new(7, "吳九", "wu@example.com"),
new(8, "鄭十", "zheng@example.com")
};
Console.WriteLine("參與者名單:");
foreach (var p in participants)
{
Console.WriteLine($" {p.Id}. {p.Name} ({p.Email})");
}
// 抽出 3 名中獎者
var winners = lottery.DrawLottery(participants, 3, useSecureRandom: false);
Console.WriteLine("\n🎉 中獎者公布 🎉");
for (int i = 0; i < winners.Length; i++)
{
Console.WriteLine($"第 {i + 1} 名: {winners[i].Name} ({winners[i].Email})");
}
// 示範 3: 安全抽獎（適用於重要場合）
Console.WriteLine("\n=== 高安全性抽獎示範 ===");
var secureWinners = lottery.DrawLottery(participants, 2, useSecureRandom: true);
Console.WriteLine("使用密碼學安全隨機數抽獎結果:");
for (int i = 0; i < secureWinners.Length; i++)
{
Console.WriteLine($"第 {i + 1} 名: {secureWinners[i].Name}");
}
// 示範 4: 多次洗牌驗證隨機性
Console.WriteLine("\n=== 隨機性驗證 ===");
int[] testArray = { 1, 2, 3, 4, 5 };
Console.WriteLine("連續 5 次洗牌結果:");
for (int round = 1; round <= 5; round++)
{
int[] temp = (int[])testArray.Clone();
lottery.Shuffle(temp);
Console.WriteLine($"第 {round} 次: [{string.Join(", ", temp)}]");
}
}
finally
{
// 確保資源被正確釋放
lottery.Dispose();
}
Console.WriteLine("\n按任意鍵結束...");
Console.ReadKey();
}
}
} 演算法核心概念
主要功能
適用場景
演算法優勢
編譯執行結果
比較真實的應用：先洗牌再抽獎
完整程式碼
Last updated