洗牌算法的实现

所谓洗牌, 就是把牌搀和整理，以便继续玩, 要的就是把原来的牌的顺序打乱, 以便游戏的公平公正性.

传统的洗牌算法是将牌一次性洗好, 然后把洗好的牌按顺序取, 这也跟现实中的洗牌比较像.

而本人实现的一个洗牌算法, 是不打乱原来的牌的顺序的, 只是在取牌的时候, 是无序(随机)的, 这也得到的牌也是乱序的, 也能得到洗牌的效果.

例如下图所示:

我们先将牌放到一个列表(list/array)里面, 然后得到列表的大小 size, 通过随机类(Random)得到这个从0~size-1 的元素索引 index

然后将这个index指向的元素返回给调用方, 并将该索引对应的元素删除(remove), 由于插入删除比较频繁, 可以考虑使用LinkedList来实现.

然后这个新的列表又可以继续按同样的方法来取值了, 这也就能得到洗牌的效果.

Java 实现(implementation)如下:

package org.jiacheo.alg;

import java.util.ArrayList;
import java.util.Collection;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;

/**
* 类名：Shuffle
*

* 类描述： 洗牌算法
*

* 创建人：jiacheo
* 创建时间：2011-1-25 下午03:10:36

* @version 2011-1-25
*
*/
public class Shuffle {
private static final Random random = new Random();
private List store = new ArrayList();
private List tokenList = new LinkedList();
private int size = 0;
public void addToken(T obj){
tokenList.add(obj);
store.add(obj);
size++;
}

public Shuffle(){

}

public Shuffle(Collection c){
store.addAll(c);
tokenList.addAll(c);
size = tokenList.size();
}

/**
*

* 方法描述：增加令牌
*

* 创建人：jiacheo
* 创建时间：2011-1-25 下午03:54:32
* @param objs
*/
public void addTokens(T… objs){
for(T t: objs){
tokenList.add(t);
store.add(t);
size++;
}
}

/**
* 增加所有令牌
*/
public void addAll(Collection c){
int lsize = c.size();
tokenList.addAll(c);
store.addAll(c);
this.size = this.size + lsize;
}

/**
*

* 方法描述：增加所有令牌
*

* 创建人：jiacheo
* 创建时间：2011-1-25 下午03:55:09
* @param ts
*/
public void addAll(T[] ts){
addTokens(ts);
}

/**
*

* 方法描述：获取下一张牌
*

* 创建人：jiacheo
* 创建时间：2011-1-25 下午03:55:22
* @return
*/
public T next(){
if(size<1){ return null; } int index = random.nextInt(size); T ret = tokenList.get(index); tokenList.remove(index); size--; return ret; } /** *

* 方法描述：重新洗牌, 会将clear/创建以来的所有牌来进来洗
*

* 创建人：jiacheo
* 创建时间：2011-1-25 下午03:55:36
*/
public void reShuffle(){
tokenList.clear();
tokenList.addAll(store);
size = tokenList.size();
}

/**
*

* 方法描述：把所有牌清除掉.
*

* 创建人：jiacheo
* 创建时间：2011-1-25 下午03:56:20
*/
public void clear(){
tokenList.clear();
size = 0;
store.clear();
}

/**
*

* 方法描述：跳过count张牌
*

* 创建人：jiacheo
* 创建时间：2011-1-25 下午03:56:43
* @param count
*/
public void skip(int count){
if(count<=0){ return; } for(int i=0;i * 方法描述：是否结束
*

* 创建人：jiacheo
* 创建时间：2011-1-25 下午03:57:11
* @return
*/
public boolean isEnd(){
return size<=0; } public static void main(String[] args) { Shuffle shuffle = new Shuffle();
for(int i=0;i<100;i++){ shuffle.addToken(""+i); } shuffle.addTokens("1","2","3","4","5","6","7","8"); shuffle.skip(4); while(!shuffle.isEnd()){ System.out.println(shuffle.next()); } System.out.println("reshuffle..."); shuffle.reShuffle(); while(!shuffle.isEnd()){ System.out.println(shuffle.next()); } } } [/php]