编写一个方法,洗一副牌。要求做到完美洗牌,换言之,这幅牌52!种排列组合出现的概率相同。假设给定一个完美的随机发生器

原创
2016/11/28 11:21
阅读数 328

解法:假定有个数组,含有n个元素,类似如下:

[1][2][3][4][5]

利用简单构造法,我们不妨先问自己,假定有个方法shuffle(...)对n-1个元素有效,我们可以用它来打乱n个元素的次序吗?当然可以,而且非常容易实现。我们会先打乱前n-1个元素的次序,然后,取出第n个元素,将它和数组中的元素随机交换。就这么简单!递归解法的算法如下:

复制代码

//lower和highter(含)之间的随机数
int rand(int lower,int highter)
{
    return lower+(int)(random()*(highter-lower+1));
}

void shuffleArrayRecursively(int cards[],int i)
{
    if(i==0)
        return;
    shuffleArrayRecursively(cards,i-1);
    int k=rand(0,i);
    int temp=cards[i];
    cards[i]=cards[k];
    cards[k]=temp;
    return;
}

复制代码

以迭代方式实现的话,这个算法又会是什么样?让我们先考虑,我们要做的是遍历整个数组,对每个元素i,将array[i]与0到i(含)之间的随机数交换。

复制代码

void suffleArrayInteratively(int cards[],n)
{
    for(int i=0;i<n;i++)
    {
        int k=rand(0,i);
        int tmp=cards[k];
        cards[k]=cards[i];
        cards[i]=tmp;
    }
}

复制代码

 

洗牌问题(shuffle)就如随机取样(random sample)问题,在《计算机程序设计艺术》(volume 2 chapter 3)中得到了详细的讲解,关于该问题的详细探讨可以翻阅该书相应章节。

洗牌问题,顾名思义,就是给你一把牌,让你把它完全打乱,这可以归结成一个数组问题:

给你一个长度为n的数组,要求你将其完全打乱,数组中元素交换跟下标是一一对应的,所以也就可以表述为给你一个有序序列0—n-1,要你将其完全打乱,要求每个元素在任何一个位置出现的概率均为1/n。

洗牌问题是打乱一个有序序列(比如下标有序)的算法与随机取样颇有渊源,算法也与随机取样问题十分相近,如下:

void shuffle(T* arr, int len)

{

               for(int i=0; i<len; i++)

               {

                               int idx=rand()%(i+1);

                               swap(arr[idx], arr[i]);

               }

}

算法正确性证明也可以用数学归纳法证明:

待证明问题:对于一个长度为n的数组,经过上述算法处理后,会得到一个随机数组,原数组中每一个元素在任何一个位置的概率均为1/n

证明:算法可以分为两部分:前n-1次执行+最后一次执行

1、当n=1时,idx必为0,所以元素arr[0]在任何一个位置的概率为1/1,命题成立。

2、假设当n=k时,命题成立,即n=k时,原数组中任何一个元素在任何一个位置的概率为1/k。

当n=k+1时,当算法执行完k次时,前k个元素在前k个位置的概率均为1/k,执行最后一步时,前k个元素中任何一个元素被替换到第k+1位置的概率:

       (1-(1/k)*(k/k+1)) * (1/k) = 1/k+1

所以,对于前k个元素,它们在k+1的位置上概率为1/k+1,在前面k个位置任何一个位置上的概率为(1-1/(k+1)) * (1/k)=1/(k+1),对于前k个元素,其在整个数组前k+1个位置上的概率均为1/k+1,

对于第k+1个元素,其在原位置的概率为1-(k/k+1)=1/k+1,在前k个位置任何一个位置的概率为:(k/k+1) * (1/k)=1/k+1,所以对于第k+1个元素,其在整个数组前k+1个位置上的概率也均为1/k+1。

命题得证。

能让我理解的随机洗牌问题。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。

问题描述:假设有一个数组,包含n个元素。现在要重新排列这些元素,要求每个元素被放到任何一个位置的概率都相等(即1/n),并且直接在数组上重排(in place),不要生成新的数组。用O(n) 时间、O(1)辅助空间。

算法是非常简单了,当然在给出算法的同时,我们也要证明概率满足题目要求。

先想想如果可以开辟另外一块长度为n的辅助空间时该怎么处理,显然只要对n个元素做n次(不放回的)随机抽取就可以了。先从n个元素中任选一个,放入新空间的第一个位置,然后再从剩下的n-1个元素中任选一个,放入第二个位置,依此类推。

按照同样的方法,但这次不开辟新的存储空间。第一次被选中的元素就要放入这个数组的第一个位置,但这个位置原来已经有别的(也可能就是这个)元素了,这时候只要把原来的元素跟被选中的元素互换一下就可以了。很容易就避免了辅助空间。

我们先假设一个5维数组:1,2,3,4,5。如果第1次随机取到的数是4, 那么我们希望参与第2次随机选取的只有1,2,3,5。既然4已经不用, 我们可以把它和1交换,第2次就只需要从后面4位(2,3,1,5)中随机选取即可。同理, 第2次随机选取的元素和数组中第2个元素交换,然后再从后面3个元素中随机选取元素, 依次类推。

C++实现:

void RandomShuffle(int a[], int n){
    for(int i=0; i<n; ++i){
        int j = rand() % (n-i) + i;// 产生i到n-1间的随机数,依次从n个元素,n-1个元素,n-2个元素中取得一个元素。
        Swap(a[i], a[j]);
    }

 

 

思路:我们有n张牌,不妨先假设有一个洗牌函数shuffle(....),能完美的洗出n-1张牌 。拿第n张牌来打乱前面n-1的洗牌顺序,从而得到n张牌的最终结果。

举例说明:如果1,2,3三张牌,想完美洗牌,那么先让1,2洗牌洗好,再把3与其中之一(随机选取)进行交换,所以是递归思想,而非循环思想,差别是递归是等洗出n-1张牌再拿第n张牌去交换,如果要循环做,就是第n张牌去换一下n-1张牌其中之一

递归代码:

package main

import (
	"fmt"
	"math/rand"
	"time"
)

func randNum(low, high int) int {
	r := rand.New(rand.NewSource(time.Now().UnixNano()))
	return low + r.Intn(high-low+1)
}

func shuffle(arr []int, n int) {

	if n <= 0 {
		return
	}

	shuffle(arr, n-1)
	rand := randNum(0, n)

	arr[n], arr[rand] = arr[rand], arr[n]

}

func main() {
	cards := []int{
		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, 52}

	cardslen := len(cards)
	cardslen1 := cardslen / 4

	for i := 1; i <= 10; i++ {
		fmt.Printf("\n")
		shuffle(cards, cardslen-1)
		for j := 1; j <= cardslen; j++ {
			fmt.Printf("%d ", cards[j-1])
			if j%cardslen1 == 0 {
				fmt.Printf("\n")
			}
		}
	}
}

java实现随机洗牌算法

 

复制代码

import java.util.Random;

class Card
{
    public String num;
    public String suit;
    Card(String n,String s)
    {
        this.num=n;
        this.suit=s;
    }
    public String toString()
    {
        String ss=suit+":"+num+"  ";
        return ss;
    }
}

class DeskOfCard
{
    Card card[];
    public void initcard()//初始化
    {
        String num[]={"A","2","3","4","5","6","7","8","9","10","J","Q","K"};
        String suit[]={"方块","梅花","红桃","黑桃"};
        card = new Card[52];
        for(int i=0;i<52;i++)
        {
            card[i] = new Card(num[i%13],suit[i/13]);
        }
    }

    public void shufflecard()//洗牌
    {
        Random rd = new Random();
        for(int i=0;i<52;i++)
        {
            int j = rd.nextInt(52);//生成随机数
            Card temp = card[i];//交换
            card[i]=card[j];
            card[j]=temp;
        }
    }


    public void dealcard()//发牌
    {
        for(int i=0;i<52;i++)
        {
            if(i%4==0) System.out.println("\n");
            System.out.print(card[i]);
        }
    }
}

public class TestCard 
{
    public static void main(String[] args) 
    {
        DeskOfCard cc = new DeskOfCard();
        cc.initcard();
        cc.shufflecard();
        cc.dealcard();
    }
}

 

这个算法的要求是这样的:将N个数乱序后输出.由于和扑克牌的洗牌过程比较相似所以我也就称为洗牌算法了.很多地方都不自觉的需要这个算法的支持.也可以将这个算法扩展为从N个数中取出M个不重复的数(0

思路:

有n个数据的数据列,从第一个元素开始,随机取出数据列中元素与之交换,依次进行n次交换,即可得到一个随机排列的数据列

代码实现:

public class ShuffleSortTest {

 public static void main(String[] args) {
  int[] data = new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
  print(data);
  shuffleSort(data);
  System.out.println("排序后的数组:");
  print(data);
 }

 public static void swap(int[] data, int i, int j) {
  if (i == j) {
   return;
  }
  data[i] = data[i] + data[j];
  data[j] = data[i] - data[j];
  data[i] = data[i] - data[j];
 }

 public static void shuffleSort(int[] data) {
  for (int i = 0; i < data.length - 1; i++) {
   int j = (int) (data.length * Math.random());
   swap(data, i, j);
  }
 }

 public static void print(int[] data) {
  for (int i = 0; i < data.length; i++) {
   System.out.print(data[i] + "\t");
  }
  System.out.println();
 }

}
运行结果

0 1 2 3 4 5 6 7 8 9 
排序后的数组:
0 7 4 1 8 6 5 2 9 3
 

 

每次的运行结果都是随机的

 

参考:http://blog.csdn.net/sunnyyoona/article/details/43795243

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
在线直播报名
返回顶部
顶部