随机数相关

random_selection.py

# -*- coding: utf-8 -*-  
import random
import sys


def random_select(a):
    ret = a[0]
    for i in range(1, len(a)):
        j = random.randint(0, i)
        if j == i:
            ret = a[j]
    return ret


def shuffle(a):
    n = len(a)
    for i in range(n):
        j = random.randint(i, n-1)
        a[i], a[j] = a[j], a[i]


def rand_range(a, b):
    gap = b-a+1
    while True:
        r = random.randrange(sys.maxint)
        if r < sys.maxint / gap * gap:
            return a + r % gap
    return None


def rand_m_n(m, n):
    a, val = 1, 0
    while True:
        val = val * m + rand_range(0, m-1)
        a *= m
        if a > n:
            if val / n * n < n:
                return val % n
            else:
                a = 1
                val = 0


"""
一个Array, 比如说 [1, 2, -4, 5, 1, -6, -3, 5, 5, 2 3]
要return max 的index. 如果有多个max, 随机return一个出来.
"""
# use the idea of random select
# use cnt to mark the occurence of the max val
# iterate through the array
# if a[i] < a[max_idx] : continue
# if a[i] > a[max_idx] : max_val = a[i], cnt = 1
# if a[i] = a[max_idx] : cnt++, r = random(cnt-1), max_idx = i if r == 0
def random_max_idx(a):
    if not a:
        return None
    max_idx, cnt = 0, 1
    for i in range(1, len(a)):
        if a[i] > a[max_idx]:
            max_idx, cnt = i, 1
        elif a[i] == a[max_idx]:
            cnt += 1
            r = rand_range(0, cnt-1)
            if r == 0:
                max_idx = i
    return max_idx


def test_rand_max_idx(a):
    tests = 10000
    m = {}

    for i in range(tests):
        j = random_max_idx(a)
        if j in m:
            m[j] += 1
        else:
            m[j] = 1

    for i, val in m.items():
        print i, val


def test_rand_m_n(a, b):
    tests = 10000
    m = {}

    for i in range(tests):
        j = rand_m_n(a, b)
        if j in m:
            m[j] += 1
        else:
            m[j] = 1

    for i, val in m.items():
        print i, val

a = [0, 3, 1, 3, 2, 3]
# test_rand_m_n(7, 3)
test_rand_max_idx(a)