随机洗牌算法,或者叫“排列组合算法”,或者叫“生成不重复的随机数”,是一种很常用的算法。
先看看肖舸老师的文章:《随机洗牌算法复杂度的比较实例》http://tonyxiaohome.blog.51cto.com/blog/925273/313362
其实我最初想到的也是那3个方法:1判断生成的随机数有没有重复,2.生成一张布尔表,3.双随机数。
下面给出我的算法:
#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]放到倒数第二个位置(与最后一个未使用的数交换),
以此类推……最后,整个序列都被打乱了,而且数字成排列组合状态,不会有数字重复出现。
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"); zolltyRandom(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")); zolltyRandom(excList); printList(excList); int orgIntArray[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21 }; int resultArray[] = zolltyRandom(orgIntArray); printArray(resultArray); } /** * 将原始数组重新随机排序(=洗牌) * * @param orgIntArray * 例如{ 0, 1, 2, 3, 4, 5, 6, 7 } * @return 排列后的数组 * @author zollty */ public static int[] zolltyRandom(int[] orgIntArray) { Random rand = new Random(); int pos, temp2; int returnValue[] = new int[orgIntArray.length]; for (int i = 0, r = orgIntArray.length; i < orgIntArray.length - 1; i++, r--) { pos = Math.abs(rand.nextInt()) % r; returnValue[i] = orgIntArray[pos]; // [pos]已使用,与最后那个未使用的交换 temp2 = orgIntArray[pos]; orgIntArray[pos] = orgIntArray[r - 1]; orgIntArray[r - 1] = temp2; } returnValue[orgIntArray.length - 1] = orgIntArray[0]; return returnValue; } /** * 将ArrayList里面的元素随机排序(=洗牌) * * @param targetList * 需要排序的"ArrayList" * @author zollty */ @SuppressWarnings("unchecked") public static void zolltyRandom(ArrayList targetList) { Random rand = new Random(); int pos; int size = targetList.size(); targetList.add(targetList.get(0)); // 即targetList.get(size) 作为temp元素 for (int i = 0, r = size; i < size - 1; i++, r--) { pos = Math.abs(rand.nextInt()) % r; // [pos]已使用,与最后那个未使用的交换 targetList.set(size, targetList.get(pos)); // 将[pos]的值暂时转移到[size]上 targetList.set(pos, targetList.get(r - 1)); targetList.set(r - 1, targetList.get(size)); } targetList.remove(size); // 移除temp元素 } public static void printArray(int[] arry) { for (int j = 0; j < arry.length; j++) { System.out.print(arry[j]); if (j != arry.length - 1) { System.out.print(","); } } } public static void printArray(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)); } }