随机洗牌算法
2011年11月18日


随机洗牌算法,或者叫“排列组合算法”,或者叫“生成不重复的随机数”,是一种很常用的算法。


先看看肖舸老师的文章:《随机洗牌算法复杂度的比较实例》http://tonyxiaohome.blog.51cto.com/blog/925273/313362

其实我最初想到的也是那3个方法:1判断生成的随机数有没有重复,2.生成一张布尔表,3.双随机数。

下面给出我的算法:(利用C++的vector向量极大的简化了算法)

#include <iostream>
#include <vector>
#include <time.h>
using namespace std;
void RandCard(vector<int>, int);    //函数声明

int main(int argc, char *argv[])
{
    vector<int> nRetCard;
    int nCards=54;
    RandCard(nRetCard, nCards);
    return 0;
}

void RandCard(vector<int> nRetCard, int nCards)
{
    int i, j, temp;
    for(i=0; i<nCards; i++)
    {
        nRetCard.push_back(i+1);  //顺序生成初始值
    }
    srand(time(NULL));
    for(i=0, j=nCards; i<nCards; i++, j--)  //算法时间复杂度为O(n)
    {
        temp=rand()%j;  //从向量中随机取一个
        cout<<nRetCard[temp]<<" ";
        if( !((i+1)%17) ) cout<<endl;  //每隔17个换行
        nRetCard.erase(nRetCard.begin()+temp);  //删除用过的元素
    }
}

其思路很简单,每次从向量中随机取一个数出来,利用vevtor向量的自动调整长度,每次删除一个元素,再用新的向量长度j生成随机数:temp=rand()%j; 显然算法的时间复杂度为O(n)(不考虑vevtor向量API的情况下),即一趟for循环,不存在最坏情况。


但是注意,该方法的写法虽然简单,但是调用了vevtor向量的API,所以其实效率并不是特别高,但一般情况下够用了

 


如果是PHP语言,那么它自带了一个随机洗牌的函数,即shuffle(),它的作用是随机地对数组元素重新排序。其形式为:

void shuffle(array input_array)

考虑一个数组,其中包含扑克牌的值:

$cards = array("jh","js","jd","jc","qh","qs","qd","qc","kh","ks","kd","kc","ah","as","ad","ac");


$positions=shuffle($cards);


print_r($positions);    //输出随机排序后的结果

另外PHP中的array_rand()函数可从数组中随机出一个或多个键,其形式为:

mixed array_rand(array array [, int num_entries] )

如果忽略可选的num_entries参数,则只返回一个随机值。可以通过设置num_entries来调整返回随机值的个数。


 如果是Java语言,可以用我下面这个算法,效率是以上探讨过的方法中最高的,当然这个算法也可以用其他语言来实现,大概思路如下:

从0~size-1中产生一个随机数j,然后将a.[j]放到最末尾去(与最后一个未使用的数交换),

然后再从0~size-2中产生一个随机数k,然后将a.[k]放到倒数第二个位置(与最后一个未使用的数交换),

以此类推……最后,整个序列都被打乱了,而且数字成排列组合状态,不会有数字重复出现。

/**
 * 将原始数组重新随机排序(=洗牌)
 * 
 * @param orgIntArray
 *            例如{ 0, 1, 2, 3, 4, 5, 6, 7 }
 */
public static void shuffle(int[] orgIntArray) {
    int pos, temp;
    Random rand = new Random();
    for (int r = orgIntArray.length - 1; r > 0; r--) {
        // 0 ~ r
        pos = Math.abs(rand.nextInt()) % (r + 1);

        // [pos]已使用,与最后那个未使用的交换
        temp = orgIntArray[pos];
        orgIntArray[pos] = orgIntArray[r];
        orgIntArray[r] = temp;
    }
}

/**
 * 将ArrayList里面的元素随机排序(=洗牌)
 * 
 * @param targetList
 *            需要排序的"ArrayList"
 */
public static void shuffle(ArrayList targetList) {
    Object temp;
    int pos;
    Random rand = new Random();
    for (int r = targetList.size() - 1; r > 0; r--) {
        // 0 ~ r
        pos = Math.abs(rand.nextInt()) % (r + 1);

        // [pos]已使用,与最后那个未使用的交换
        temp = targetList.get(pos);
        targetList.set(pos, targetList.get(r));
        targetList.set(r, temp);
    }
}

public static void main(String[] args) {
    ArrayList<String> pokerCards = new ArrayList<String>(5);
    pokerCards.add("A");
    pokerCards.add("B");
    pokerCards.add("C");
    pokerCards.add("D");
    pokerCards.add("E");

    shuffle(pokerCards);
    printList(pokerCards);

    ArrayList<Exception> excList = new ArrayList<Exception>(5);
    excList.add(new Exception("A"));
    excList.add(new Exception("B"));
    excList.add(new Exception("C"));
    excList.add(new Exception("D"));
    excList.add(new Exception("E"));

    shuffle(excList);
    printList(excList);

    int orgIntArray[] = {0, 1, 2, 3, 4, 5, 6, 7};
    shuffle(orgIntArray);
    printArray(orgIntArray);
}

public static void printArray(final int[] arry) {
    for (int j = 0; j < arry.length; j++) {
        System.out.print(arry[j]);
        if (j != arry.length - 1) {
            System.out.print(",");
        }
    }
    System.out.println();
}

public static void printArray(final String[] arry) {
    for (int j = 0; j < arry.length; j++) {
        System.out.println(j + " => " + arry[j]);
    }
}

public static void printList(final List list) {
    int size = list.size();
    for (int j = 0; j < size; j++) {
        System.out.println(j + " => " + list.get(j));
    }
}