浅谈shuffle算法--播放器的另一种随机算法【转】
shuffle算法，我把他叫做洗牌算法，它的目标正好与各种的sort算法相反，即把一个有序(或者无序)的一系列元素打乱，以满足需求。
举个两例子，大家都知道扑克牌，我们每次都需要在摸牌之前把牌洗掉，用来让每个人摸到每张牌的概率尽量相等，增加游戏的随机性和乐趣；还有音频播放器，有一些人不喜欢顺序播放，而喜欢使用随机播放(其实随机播放分为两种,random和shuffle，后文会介绍到)，比如iPod Shuffle的卖点之一就是“你永远不知道你将要听到的下一首歌曲是什么”。至少，如果要模拟扑克牌游戏，或者做音频播放器，都要使用shuffle算法，而二者的shuffle算法却有一些区别，一个是一次性的洗牌，另一个则是每次取一首歌。那么怎么实现他们呢？
扑克牌的shuffle算法：
下面为了方便和容易读懂，我都用扑克牌来作例子：桌上有n张牌，并且对桌子上的牌进行标号，从0直到n-1。我们的目的是洗这些牌。
一个比较容易想到的方法是，桌子上有n张扑克牌，我第i次从桌子上等概率随机取一张扑克牌，作为洗牌后牌堆的第i张扑克牌，那么这个算法实现起来应该是这样的：
伪代码：
for i <- 0 to n - 1
do d <- Random mod (n - i)
shuffle[i] <- deck[d]
deck[d] <- deck[n - i]
其中，deck是洗牌前的序列(0~n-1)，shuffle是洗牌后的序列(0~n-1)，第i次(从0开始数)在剩下的n-i张牌里等概率的取一张牌，把它放到shuffle里。而deck[d] = deck[n - i]这句达到的效果是删除取过的牌。
这个方法的时间复杂度是O(n)，已经可以接受了，但这个方法还不够好，因为我们需要两个长度为n数组。其实可以很容易得得到下面的方法，解决空间的问题：
伪代码：
for i <- 0 to n - 1
do d <- Random mod (n - i)
swap(deck[d], deck[n - i])
这样，这个算法的道理就有些像选择排序了，第i次(从0开始数)确定第n-i个元素的原位置，并且交换两个位置上的元素。它的复杂读仍然是O(n)，而只需要1个额外的空间来储存交换用的临时变量。
这个方法已经是一个比较好的解决方法了(自己认为)，如果你还能写出更好的shuffle算法，请告诉我。
我相信对洗牌这种东西有了解的人都不会用这样的方法来洗牌：另外对每张牌做一个标记，即是否抽过这张牌：然后第i次在n张牌里随机抽一个，如果这张牌曾经被抽过，那么把它放回去，重复抽取，直到抽到一张没被抽过的牌，将这张牌标记为抽取过的牌，然后在纸上的第i个地方记下这张牌。在计算机里这样实现：
伪代码：
for i <- 0 to n - 1
do d <- Random mod n
while did[d] = 1
do d = Random mod n
did[d] <- 1
shuffle[i] <- deck[d]
看了描述，你一定就会觉得这种方法实在是遭透了，不仅麻烦，而且会有一个陷阱，那就是在某次取牌的时候，也许会运气差永远也取不到没有被取过的那张牌，导致程序运行的不确定性。然而，在初学者当中，却有不少是用这种方法实现的shuffle的。个人认为，在设计算法的时候，越简单、越接近生活的模型，就越容易设计出好的算法，而且算法的描述也更接近实际生活。因此，设计算法的时候，如果能往平时生活的方面想， 总是事半功倍的。
附上我自己实现的一个类qsort的shuffle算法
// element_Size is the size of each element
void swap(void const *element1, void const *element2, size_t element_Size)
{
char *temp = new char,
*elem1, *elem2;
elem1 = (char *)element1;
elem2 = (char *)element2;
for(int i = 0; i < element_Size; i++, elem1++, elem2++){
*temp = *elem1;
*elem1 = *elem2;
*elem2 = *temp;
}
delete temp;
}
// array_Size is the size of array,
// element_Size is the size of each element in array
void shuffle(void const *array, size_t array_Size, size_t element_Size)
{
void *element1, *element2;
srand(time(0));
for(int i = 0; i < array_Size / element_Size; i++){
element1 = (char *)array + i * element_Size;
element2 = (char *)array + rand(i * element_Size,
array_Size - element_Size, element_Size);
swap(element1, element2, element_Size);
}
}
播放器的shuffle算法：
前面说过播放器的随机播放有两种，一种叫Random,一种叫Shuffle(我自己理解的......)，下面解释这两种方法的不同。
学过概率的人都该知道有放回的抽取的概念。袋中有n个不同的小球，每次抽取一个小球，然后放回，每一次取的时候概率都是相同的。这正是播放器random算法的原理，这种算法实现起来很简单，一首歌结束以后，只需要随机选取下一首歌就行了。
但是这样做有一些缺点：1，有一定的概率使得连续选取的两首歌是同一首歌，我相信并不是所有人都希望在shuffle模式下连续听同一首歌吧，当然也有解决办法，那就是增加层循环判断，如果选上同一首歌，则重新选，而这样又会重蹈那个很烂的洗牌算法的覆辙。2，当听完一首歌的时候，觉得还想再听一遍，怎么办？按下“上一首”，你会发现这时听到的歌曲已经不是刚才那一首想听歌曲了，因为这种方法只知道当前的状态，而不知道过去的播放状态。怎么办？一种办法是增加一个队列叫做“刚才播放列表”，把播放过的歌曲按照顺序储存在列表里。3，有一定概率在很长的一段时间内，播放器不停的在重复播放两首歌曲A和B或者类似情况，就像这样：...-A-B-A-B-A-B-...。这种情况也是很讨厌的，可是如何避免呢？我能想到的办法是增加判断，看这首歌是不是在列表的最后几项里，如果在就不选这首......
但是这些概率都小的可怜，对于一个播放器的random函数来说，能够考虑到以上的几点，已经能够做到足够random和人性化了。只要能够合理的选择参数，考虑到一些特殊情况(比如极小的播放列表)，以及考虑用户的心理，就能做出一个比较好的random函数。
下面讲我设计的播放器shuffle算法，shuffle算法能够很大程度上避免random算法的缺陷，在空间时间上都很节约，而且能够达到比较理想的随机化效果。它的大体思路是这样的：
我们使用一个隐含的shuffle播放列表(一个循环队列)来储存歌曲的顺序，并用一个指针表示正在播放的歌曲(记作"^")，比如当前的播放列表是这样的：
ABCDEFGHIJKLMN
^
即现在有14首歌，将要播放位置1的歌曲(正在播放位置14的歌曲)，我们认为队列头和尾是相连的，即N后面的元素是A，那么这样够成了一个循环队列。
在播放之前，我们在前7(7=14*0.5，这个比例可以随便选，当然越大随机性越大，但能后退的次数越少)个位置中，随机取一个一首歌，把它和将要播放的那个位置的歌曲交换。假设我们选的是E，则队列变成这样：
EBCDAFGHIJKLMN
^
然后播放E。E播放完了以后(或者选择下一首时)，重复刚才的动作，即在BCDAFGH中随机选一个，交换，比如选到H，则队列变成：
EHCDAFGBIJKLMN
^
然后播放H。这样，一个shuffle算法初步完成了。
比如某一时刻播放器的状态是这样：
EHCDAFGBIJKLMN
^
则我们在LMNEHCD中选择一个，比如选择到H，那么交换并播放，成为：
ELCDAFGBIJKHMN
^
但是如果用户选择上一首怎么办呢?我们可以再记录一个指针指向最新shuffle选择出来的那首歌曲(记作"*")，没有选择过前一首的时候，它与播放指针指向同一个位置。当选择前一首的时候，仅移动指针^，而不移动*，比如上一个例子播放的时候按下前一首以后，成为：
ELCDAFGBIJKHMN
^*
这时候播放的K正好是刚才播放的那一首，当然这达到了我的目的，即可以选到刚才播放的曲目，当然如果再一次选择上一首，就会变成：
ELCDAFGBIJKHMN
^ *
这时候如果按下一首，应该判断^指向的是不是和*指向的相同，如果相同，就按照最早介绍的shuffle算法进行随机选取，不相同就简单的移动^，即成为：
ELCDAFGBIJKHMN
^*
伪代码：
function keypress(key)
if key = NEXT
if p1 = p2
do p1 <- p1 + 1
p2 <- p2 + 1
k = Random mod (length / 2)
swap(p1, (p1 + k) mod length)
play(p2)
else
do p2 <- (p2 + 1) mod length
play(p2)
if key = PREV
do p2 <- (p2 + length - 1) mod length
play(p2)
这个播放器的shuffle算法比较简单实用，而且节约内存开销(这对mp3 walkman之类的东西是十分重要的)，当然也有个小缺点，就是当^前移多次回到*以后，再按下一首，则会重新开始shuffle，但是歌曲数目很多的情况下，这个缺点并不是那么重要。
这个算法在刚开始听的时候，并不是很随机，可是随着听的次数的增多，队列会越来越乱，达到一个shuffle的效果。
当然，也可以在第一次对这个列表播放之前，使用扑克牌的shuffle算法(见本文第一部分)进行一次shuffle，这样，刚开始播放的时候列表就是随机的。
通过原理我们可以看到，对于刚听过的那首歌来说，不经过length / 2次，是不会再一次听到的，因此很大程度上避免了random算法的缺陷。这个length / 2的参数可以按照具体情况选择，可以是常数，也可以是随机数，也可以是和长度有关的一个数。
查了下资料好像苹果使用的就是洗牌算法，机器在计算完之后会生成一个随机的列表，这样保证你在随机播放的时候不会播放到重复的歌曲同时也使随机播放中的上一首及下一首按键真正的发挥作用，不会因为在随机播放中听了一个很喜欢的歌播放完毕之后还想再听一遍点上一首不知道跳到哪儿去的现象。我感觉这种方法真的很不错，不知道除了苹果的播放器其他还有那种品牌的播放器使用类似的随机方法。
举个两例子，大家都知道扑克牌，我们每次都需要在摸牌之前把牌洗掉，用来让每个人摸到每张牌的概率尽量相等，增加游戏的随机性和乐趣；还有音频播放器，有一些人不喜欢顺序播放，而喜欢使用随机播放(其实随机播放分为两种,random和shuffle，后文会介绍到)，比如iPod Shuffle的卖点之一就是“你永远不知道你将要听到的下一首歌曲是什么”。至少，如果要模拟扑克牌游戏，或者做音频播放器，都要使用shuffle算法，而二者的shuffle算法却有一些区别，一个是一次性的洗牌，另一个则是每次取一首歌。那么怎么实现他们呢？
扑克牌的shuffle算法：
下面为了方便和容易读懂，我都用扑克牌来作例子：桌上有n张牌，并且对桌子上的牌进行标号，从0直到n-1。我们的目的是洗这些牌。
一个比较容易想到的方法是，桌子上有n张扑克牌，我第i次从桌子上等概率随机取一张扑克牌，作为洗牌后牌堆的第i张扑克牌，那么这个算法实现起来应该是这样的：
伪代码：
for i <- 0 to n - 1
do d <- Random mod (n - i)
shuffle[i] <- deck[d]
deck[d] <- deck[n - i]
其中，deck是洗牌前的序列(0~n-1)，shuffle是洗牌后的序列(0~n-1)，第i次(从0开始数)在剩下的n-i张牌里等概率的取一张牌，把它放到shuffle里。而deck[d] = deck[n - i]这句达到的效果是删除取过的牌。
这个方法的时间复杂度是O(n)，已经可以接受了，但这个方法还不够好，因为我们需要两个长度为n数组。其实可以很容易得得到下面的方法，解决空间的问题：
伪代码：
for i <- 0 to n - 1
do d <- Random mod (n - i)
swap(deck[d], deck[n - i])
这样，这个算法的道理就有些像选择排序了，第i次(从0开始数)确定第n-i个元素的原位置，并且交换两个位置上的元素。它的复杂读仍然是O(n)，而只需要1个额外的空间来储存交换用的临时变量。
这个方法已经是一个比较好的解决方法了(自己认为)，如果你还能写出更好的shuffle算法，请告诉我。
我相信对洗牌这种东西有了解的人都不会用这样的方法来洗牌：另外对每张牌做一个标记，即是否抽过这张牌：然后第i次在n张牌里随机抽一个，如果这张牌曾经被抽过，那么把它放回去，重复抽取，直到抽到一张没被抽过的牌，将这张牌标记为抽取过的牌，然后在纸上的第i个地方记下这张牌。在计算机里这样实现：
伪代码：
for i <- 0 to n - 1
do d <- Random mod n
while did[d] = 1
do d = Random mod n
did[d] <- 1
shuffle[i] <- deck[d]
看了描述，你一定就会觉得这种方法实在是遭透了，不仅麻烦，而且会有一个陷阱，那就是在某次取牌的时候，也许会运气差永远也取不到没有被取过的那张牌，导致程序运行的不确定性。然而，在初学者当中，却有不少是用这种方法实现的shuffle的。个人认为，在设计算法的时候，越简单、越接近生活的模型，就越容易设计出好的算法，而且算法的描述也更接近实际生活。因此，设计算法的时候，如果能往平时生活的方面想， 总是事半功倍的。
附上我自己实现的一个类qsort的shuffle算法
// element_Size is the size of each element
void swap(void const *element1, void const *element2, size_t element_Size)
{
char *temp = new char,
*elem1, *elem2;
elem1 = (char *)element1;
elem2 = (char *)element2;
for(int i = 0; i < element_Size; i++, elem1++, elem2++){
*temp = *elem1;
*elem1 = *elem2;
*elem2 = *temp;
}
delete temp;
}
// array_Size is the size of array,
// element_Size is the size of each element in array
void shuffle(void const *array, size_t array_Size, size_t element_Size)
{
void *element1, *element2;
srand(time(0));
for(int i = 0; i < array_Size / element_Size; i++){
element1 = (char *)array + i * element_Size;
element2 = (char *)array + rand(i * element_Size,
array_Size - element_Size, element_Size);
swap(element1, element2, element_Size);
}
}
播放器的shuffle算法：
前面说过播放器的随机播放有两种，一种叫Random,一种叫Shuffle(我自己理解的......)，下面解释这两种方法的不同。
学过概率的人都该知道有放回的抽取的概念。袋中有n个不同的小球，每次抽取一个小球，然后放回，每一次取的时候概率都是相同的。这正是播放器random算法的原理，这种算法实现起来很简单，一首歌结束以后，只需要随机选取下一首歌就行了。
但是这样做有一些缺点：1，有一定的概率使得连续选取的两首歌是同一首歌，我相信并不是所有人都希望在shuffle模式下连续听同一首歌吧，当然也有解决办法，那就是增加层循环判断，如果选上同一首歌，则重新选，而这样又会重蹈那个很烂的洗牌算法的覆辙。2，当听完一首歌的时候，觉得还想再听一遍，怎么办？按下“上一首”，你会发现这时听到的歌曲已经不是刚才那一首想听歌曲了，因为这种方法只知道当前的状态，而不知道过去的播放状态。怎么办？一种办法是增加一个队列叫做“刚才播放列表”，把播放过的歌曲按照顺序储存在列表里。3，有一定概率在很长的一段时间内，播放器不停的在重复播放两首歌曲A和B或者类似情况，就像这样：...-A-B-A-B-A-B-...。这种情况也是很讨厌的，可是如何避免呢？我能想到的办法是增加判断，看这首歌是不是在列表的最后几项里，如果在就不选这首......
但是这些概率都小的可怜，对于一个播放器的random函数来说，能够考虑到以上的几点，已经能够做到足够random和人性化了。只要能够合理的选择参数，考虑到一些特殊情况(比如极小的播放列表)，以及考虑用户的心理，就能做出一个比较好的random函数。
下面讲我设计的播放器shuffle算法，shuffle算法能够很大程度上避免random算法的缺陷，在空间时间上都很节约，而且能够达到比较理想的随机化效果。它的大体思路是这样的：
我们使用一个隐含的shuffle播放列表(一个循环队列)来储存歌曲的顺序，并用一个指针表示正在播放的歌曲(记作"^")，比如当前的播放列表是这样的：
ABCDEFGHIJKLMN
^
即现在有14首歌，将要播放位置1的歌曲(正在播放位置14的歌曲)，我们认为队列头和尾是相连的，即N后面的元素是A，那么这样够成了一个循环队列。
在播放之前，我们在前7(7=14*0.5，这个比例可以随便选，当然越大随机性越大，但能后退的次数越少)个位置中，随机取一个一首歌，把它和将要播放的那个位置的歌曲交换。假设我们选的是E，则队列变成这样：
EBCDAFGHIJKLMN
^
然后播放E。E播放完了以后(或者选择下一首时)，重复刚才的动作，即在BCDAFGH中随机选一个，交换，比如选到H，则队列变成：
EHCDAFGBIJKLMN
^
然后播放H。这样，一个shuffle算法初步完成了。
比如某一时刻播放器的状态是这样：
EHCDAFGBIJKLMN
^
则我们在LMNEHCD中选择一个，比如选择到H，那么交换并播放，成为：
ELCDAFGBIJKHMN
^
但是如果用户选择上一首怎么办呢?我们可以再记录一个指针指向最新shuffle选择出来的那首歌曲(记作"*")，没有选择过前一首的时候，它与播放指针指向同一个位置。当选择前一首的时候，仅移动指针^，而不移动*，比如上一个例子播放的时候按下前一首以后，成为：
ELCDAFGBIJKHMN
^*
这时候播放的K正好是刚才播放的那一首，当然这达到了我的目的，即可以选到刚才播放的曲目，当然如果再一次选择上一首，就会变成：
ELCDAFGBIJKHMN
^ *
这时候如果按下一首，应该判断^指向的是不是和*指向的相同，如果相同，就按照最早介绍的shuffle算法进行随机选取，不相同就简单的移动^，即成为：
ELCDAFGBIJKHMN
^*
伪代码：
function keypress(key)
if key = NEXT
if p1 = p2
do p1 <- p1 + 1
p2 <- p2 + 1
k = Random mod (length / 2)
swap(p1, (p1 + k) mod length)
play(p2)
else
do p2 <- (p2 + 1) mod length
play(p2)
if key = PREV
do p2 <- (p2 + length - 1) mod length
play(p2)
这个播放器的shuffle算法比较简单实用，而且节约内存开销(这对mp3 walkman之类的东西是十分重要的)，当然也有个小缺点，就是当^前移多次回到*以后，再按下一首，则会重新开始shuffle，但是歌曲数目很多的情况下，这个缺点并不是那么重要。
这个算法在刚开始听的时候，并不是很随机，可是随着听的次数的增多，队列会越来越乱，达到一个shuffle的效果。
当然，也可以在第一次对这个列表播放之前，使用扑克牌的shuffle算法(见本文第一部分)进行一次shuffle，这样，刚开始播放的时候列表就是随机的。
通过原理我们可以看到，对于刚听过的那首歌来说，不经过length / 2次，是不会再一次听到的，因此很大程度上避免了random算法的缺陷。这个length / 2的参数可以按照具体情况选择，可以是常数，也可以是随机数，也可以是和长度有关的一个数。
查了下资料好像苹果使用的就是洗牌算法，机器在计算完之后会生成一个随机的列表，这样保证你在随机播放的时候不会播放到重复的歌曲同时也使随机播放中的上一首及下一首按键真正的发挥作用，不会因为在随机播放中听了一个很喜欢的歌播放完毕之后还想再听一遍点上一首不知道跳到哪儿去的现象。我感觉这种方法真的很不错，不知道除了苹果的播放器其他还有那种品牌的播放器使用类似的随机方法。
