改组52张牌. [英] Shuffling a deck of 52 cards.
问题描述
嗨.
我正在编写一个小程序，该程序将绘制某些算法的运行时间.我正在写一些洗牌的方法(在int数组中只有52个整数).
这是我的方法:
//创建一个有排序的int数组.
Hi.
I am writing a small program that will plot the running times of some algorithms. I am writing some methods that shuffle a deck of cards (just 52 integers in an int array).
Here are my methods:
// Creates a sorted int array.
private int[] createNonRandomArray(int size, int startingNumber)
{
int[] array = new int[size];
for (int i = 0; i < size; i++)
{
array[i] = startingNumber;
startingNumber++;
}
return array;
}
//使用Fisher Yates算法对数组进行混洗.
// Shuffles array using Fisher Yates algorithm.
private int[] fisherYatesShuffle(int[] array)
{
Random rnd = new Random();
for (int i = array.Length - 1; i >= 0; i--)
{
int r = rnd.Next(0, i + 1);
int tmp = array[i];
array[i] = array[r];
array[r] = tmp;
}
return array;
}
//检查int数组是否已排序.
// Checks if an int array is sorted.
private bool isInOrder(int[] array)
{
int referance = 0;
foreach (int i in array)
{
if (!(i > referance))
{
return false;
}
referance = i;
}
return true;
}
现在，我实现的代码只是简单地对卡片组进行洗牌，并检查它是否已排序，如果不排序，则重复该操作，直到对其进行排序为止.这是该代码:
Now I implemented code that simply shuffles the deck and checks if it is sorted, if it is not then repeat until it is sorted. Here is that code:
private void backgroundWorkerAlgorithm_DoWork(object sender, DoWorkEventArgs e)
{
int[] array = createNonRandomArray(5,1);
int y = 0;
foreach (int i in array)
{
Console.WriteLine(i);
}
array = fisherYatesShuffle(array);
foreach (int i in array)
{
Console.WriteLine(i);
}
int numberofruns = 0;
Stopwatch sw = new Stopwatch();
sw.Start();
while (true)
{
array = fisherYatesShuffle(array);
//array = shuffleArray(array);
if (isInOrder(array))
{
break;
}
if (numberofruns % 10 == 0)
{
Console.WriteLine(numberofruns);
}
numberofruns++;
}
sw.Stop();
Console.WriteLine("Time it took: " + sw.ElapsedMilliseconds+" -- "+sw.Elapsed);
Console.WriteLine("Number of runs: " + numberofruns);
}
现在，如果我没记错的话，一张有五张牌的卡组"中有五张！ (120)可能的布置方式.因此，使用此方法整理"卡片组平均应该需要花费大约数倍的时间.
我的代码通常以4个"numberofruns"的形式给我排序，有时但很少，它需要成千上万个"numberofruns".
有人可以指出我在做什么错吗?
我程序的典型输出:
1
2
3
4
5
4
1
5
3
2
0
花费的时间:0-00:00:00.0000143
运行次数:3
Now if I am not mistaken then a "deck" with five cards has 5! (120) possible ways of being arranged. So it should take somewhere around that many times on average to "sort" the deck using this method.
My code usually gives me a sorted deck in 4 "numberofruns" and sometimes, but rarely, it takes thousands of "numberofruns".
Can someone point out what I am doing wrong?
Typical output of my program:
1
2
3
4
5
4
1
5
3
2
0
Time it took: 0 -- 00:00:00.0000143
Number of runs: 3
推荐答案
我认为我可能已经知道问题出在哪里.
在我的随机播放方法中，每次运行时，我都会创建一个新的Random().当我将其移出方法(程序启动时仅创建一个Random()对象)时，它似乎可以正常工作.
现在，我得到约100个混洗，直到将其与5个整数排序为止，该整数比以前应该更接近.
有谁知道为什么会这样吗?我想不出为什么这么重要.
I think I might have figured out what the problem was.
In my shuffle methods I create a new Random() every time I run it. When I moved that out of the method (just created one Random() object when the program starts) then it seems to work as it should.
Now I get around 100 shuffles until it is sorted with 5 integers which is much closer to what it should be than previously.
Is there someone that knows why this happens? I can''t think of why this matters so much.
您应该明确阅读这篇文章:
C#中排序算法的可视化和比较 [
You should definatly read this article:
Visualization and comparison of sorting algorithms in C#[^]
这篇关于改组52张牌.的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
