抽獎 Fisher-Yates Shuffle(費雪-耶茲洗牌演算法)
引言
工作需要洗牌演算法。問了問 AI 回答紀錄。
問
詢問有關軟體演算法。抽獎的演算法 Fisher-Yates Shuffle（費雪-耶茲洗牌演算法)。 用 C# 實作。可在 NET 8 平台執行。
答
Fisher-Yates Shuffle 是一個經典的洗牌演算法，特別適合用於抽獎系統，因為它能產生完全隨機且公平的排列。以下是 C# .NET 8 的實作：
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();
}
}
} 這個實作包含了以下重要特點：
演算法核心概念
Fisher-Yates Shuffle 的工作原理：
從陣列的最後一個元素開始
隨機選擇一個位置（0 到當前位置）
交換當前元素與隨機位置的元素
重複直到處理完所有元素
主要功能
基本洗牌 (
Shuffle): 使用System.Random進行標準洗牌安全洗牌 (
SecureShuffle): 使用密碼學安全的隨機數產生器抽獎功能 (
DrawLottery): 整合洗牌與抽獎邏輯泛型支援: 可以處理任何類型的物件
適用場景
一般抽獎活動: 使用基本洗牌即可
重要商業抽獎: 建議使用安全洗牌
遊戲開發: 卡牌洗牌、道具隨機等
統計採樣: 隨機抽樣研究
演算法優勢
時間複雜度: O(n)，非常高效
空間複雜度: O(1)，原地操作
數學保證: 每種排列的機率完全相等
無偏差: 不像其他洗牌方法可能有統計偏差
這個實作可以直接在 .NET 8 環境中運行，並提供了完整的示範案例。你可以根據需要調整參與者結構或抽獎邏輯。
編譯執行結果
=== 基本 Fisher-Yates Shuffle 示範 ===
原始順序: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
洗牌後: [1, 4, 10, 6, 8, 7, 3, 2, 9, 5]
=== 抽獎示範 ===
參與者名單:
1. 張三 (zhang@example.com)
2. 李四 (li@example.com)
3. 王五 (wang@example.com)
4. 趙六 (zhao@example.com)
5. 孫七 (sun@example.com)
6. 周八 (zhou@example.com)
7. 吳九 (wu@example.com)
8. 鄭十 (zheng@example.com)
?? 中獎者公布 ??
第 1 名: 周八 (zhou@example.com)
第 2 名: 張三 (zhang@example.com)
第 3 名: 鄭十 (zheng@example.com)
=== 高安全性抽獎示範 ===
使用密碼學安全隨機數抽獎結果:
第 1 名: 王五
第 2 名: 周八
=== 隨機性驗證 ===
連續 5 次洗牌結果:
第 1 次: [5, 4, 2, 1, 3]
第 2 次: [3, 4, 1, 5, 2]
第 3 次: [1, 5, 2, 4, 3]
第 4 次: [1, 2, 3, 5, 4]
第 5 次: [4, 5, 1, 2, 3]
按任意鍵結束...比較真實的應用：先洗牌再抽獎
測試程序
/// <summary>
/// 測試洗牌數次後再抽獎。
/// </summary>
public static void TestShuffleAndDraw()
{
// 主程式示範
using var lottery = new FisherYatesLottery();
Console.WriteLine("\n=== 測試洗牌 26 筆 ===");
var strArray = Enumerable.Range(1, 26).Select(c => $"{c:00}").ToArray();
Console.WriteLine($"原始順序: [{string.Join(",", strArray)}]");
Console.WriteLine("連續 5 次洗牌:");
for (int round = 1; round <= 5; round++)
{
lottery.SecureShuffle(strArray);
Console.WriteLine($"第 {round} 次: [{string.Join(",", strArray)}]");
}
Console.WriteLine("再抽取前 3 名中獎者:");
var winnerArray = lottery.DrawLottery(strArray, 3, useSecureRandom: true);
Console.WriteLine($"中獎者: [{string.Join(",", winnerArray)}]");
}執行結果
=== 測試洗牌 26 筆 ===
原始順序: [01,02,03,04,05,06,07,08,09,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26]
連續 5 次洗牌:
第 1 次: [11,26,06,22,13,12,07,17,04,10,19,25,21,03,23,16,20,02,14,01,18,05,24,15,08,09]
第 2 次: [11,26,07,17,03,04,06,05,08,22,16,20,18,25,15,09,02,12,23,10,14,19,01,24,13,21]
第 3 次: [11,06,23,04,05,24,07,25,21,18,20,13,12,19,02,14,15,16,26,09,01,08,10,03,17,22]
第 4 次: [04,11,26,14,06,01,16,12,03,07,18,05,02,13,20,25,22,21,15,09,24,10,17,08,23,19]
第 5 次: [24,25,17,26,19,21,11,07,12,20,08,01,06,15,16,23,22,02,03,04,09,14,10,05,13,18]
再抽取前 3 名中獎者:
中獎者: [04,14,12]
按任意鍵結束...完整程式碼
(EOF)
Last updated