Python下的一些随机化算法，Python随机化算法,# -*- coding

Python下的一些随机化算法，Python随机化算法,# -*- coding

# -*- coding: utf-8 -*-from random import randintdef lcg_random(seed):    """线性同余法生成伪随机数：    实现LCG：http://rosettacode.org/wiki/Linear_congruential_generator#Python    更多RNG：http://en.wikipedia.org/wiki/List_of_random_number_generators    Python默认RNG现为Mersenne Twister。    """    passdef fisher_yates_shuffle(A):    """Fisher–Yates洗牌算法，原地均匀随机排列，伪码如下：    1  &#9655; To shuffle an array a of n elements (indices 0..n-1):    2  for i ← n - 1 downto 1    3    do j ← random(0, i) &#9655; inclusive    4       a[j] &#8596; a[i] &#9655; exchange    参考：http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle    """    for i in reversed(xrange(1, len(A))):        j = randint(0, i)        A[i], A[j] = A[j], A[i]    # random.shuffle()即可，其用的就是该算法。def reservoir_sampling(A, k):    """水塘抽样，从未知大小的样本中随机选取k个，伪码如下：    1  &#9655; To initialize a reservoir with the size k (indices 1..n):    2  for i ← 1 to k    3    do R[i] ← S[i]    4  &#9655; To replace elements with gradually decreasing probability:    5  for i ← k + 1 to n    6    do j = random(1, i) &#9655; inclusive    7       if j <= k    8         do R[j] ← S[i]    参考：http://en.wikipedia.org/wiki/Reservoir_sampling    """    sample = []    for i, a in enumerate(A):        if i < k: # 生成k大小的水塘            sample.append(a)        else: # 递减概率随机替换水塘内元素            r = randint(0, i)            if r < k:                sample[r] = a    return sampledef pi(n = 10 ** 6):    """随机投点计算PI：    设有半圆为r的圆及其外切四边形。向正方形随机投掷n个点，设落入圆中的为k个。    那么，圆与正方形面积比PI/4=k/n，即PI=4k/n。    更多数值概率算法例子：http://blog.csdn.net/zhoudaxia/article/details/5841820    更多随机化算法内容：计算机算法设计与分析 第7章    """    from random import random    k = 0    for i in xrange(0, n):        x = random()        y = random()        if (x * x + y * y) <= 1:            k += 1    return 4. * k / nif __name__ == '__main__':    A = range(1, 20, 2)    fisher_yates_shuffle(A)    print(A)    S = reservoir_sampling(A, 3)    print(S)    print(pi())#该片段来自于http://byrx.net