首页 > 心得笔记 > Python和C++中洗牌算法Shuffle的实现

Python和C++中洗牌算法Shuffle的实现

2011年6月24日  10,340 views 发表评论 阅读评论

洗牌,就是将有序的集合中的元素以随机的顺序重新排列。

今天本来是想复习一下几种排序算法的……因为没有随机样本,所以才想着要弄洗牌算法的。以前从来就没有想到过这个问题,今天是头一次接触到打乱顺序的算法。

本文的洗牌算法参考了fuqcool的文章

首先是Python

python语言非常高级,它的标准库已经实现了洗牌函数,在Random模块下有个Shuffle函数。
这是在Random.py中的函数原型。

def shuffle(self, x, random=None, int=int):
	"""x, random=random.random -> shuffle list x in place; return None.

	Optional arg random is a 0-argument function returning a random
	float in [0.0, 1.0); by default, the standard random.random.
	"""

	if random is None:
		random = self.random
	for i in reversed(xrange(1, len(x))):
		# pick an element in x[:i+1] with which to exchange x[i]
		j = int(random() * (i+1))
		x[i], x[j] = x[j], x[i]


下面是我写的一段使用代码。source.txt内容为0~99的有序数字,每行一个数。

 

import random
source = open('source.txt')
source_str = source.read()
source_list = source_str.split('\n')

n = len(source_list)

random.shuffle(source_list)

for i in range(0, n):
	print(source_list[i])

输出结果证明确实实现了洗牌的功能。
这里附上源码文件,代码中使用自己抽取的shuffle函数。

  python_shuffle (1.5 KiB, 382 hits)

然后是C++

C++中并没有现成的shuffle函数供大家使用,参考python的shuffle实现,我用c++实现了一份。这里参考了fuqcool的文章。

其实主要的就两个部分,一个是GetRandomNum函数,获取指定范围内的一个随机数。再有就是一段交换代码。

这是shuffle函数的实现过程:

#pragma once
#include "Random.h"

int myShuffle(int* a,int len)
{
	for (int i = len - 1; i > 0; i--)
	{
		// Select a element from index 0 to i;
		int index = GetRandomNum(0, i);
		// exchange a[index] and a[i]
		int c;
		c = a[index];
		a[index] = a[i];
		a[i] = c;
	}

	return 0;
}

这是Random.h的内容,主要是解决了随机数种子的问题,通过一个static对象来设置随机数种子。

#pragma once

#include <iostream>
#include <ctime>

class Rand
{
public:
	Rand(void);
	int GetRand();
};

Rand::Rand(void)
{
	//set rand seed
	srand((unsigned)time(0));
}

int Rand::GetRand()
{
	return rand();
}

int GetRandomNum(int beg, int end)
{
	//static object set seed only once
	static Rand rand;
	int d = end - beg;
	return rand.GetRand() % d + beg;
}

很久不写C++代码了,现在都不怎么会写了,这点代码都写了半天……还有很多不合理的地方,大家凑乎看吧,反正这代码能跑起来就行~

这里也附上C++版本的代码:

  C++_Shuffle_source (1,006 bytes, 328 hits)



声明:未作说明,则本文为代码至上原创。转载务必注明出处
注意:转载须保留全文,如需修改请 联系作者
本文永久地址:http://codeup.org/archives/439


我要分享到:

新浪微博 腾讯微博 人人 Twitter Facebook 网易微博 鲜果 Follow5