算法导论——python实践（5.概率分析和随机算法）5.1 雇用问题5.3随机算法（随机排列数组）

68 阅读 0 评论 45 点赞

我是靠谱客的博主欣慰爆米花，最近开发中收集的这篇文章主要介绍算法导论——python实践（5.概率分析和随机算法）5.1 雇用问题5.3随机算法（随机排列数组），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

5.1 雇用问题

问题描述：

假设你要雇佣一个新的办公室助理，雇佣代理每天想你推荐一个应聘者（连续推荐n个），你面试这个人，如果这个应聘者比目前的办公室助理更优秀，你就会辞掉当前的办公室助理，然后聘用这个新的。面试一个人需付给雇佣代理一笔费用，聘用办公助理也需要费用。

假设面试费用为Ci，雇佣的费用为Ch，假设整个过程中雇佣了m次，于是总的费用是 nCi+mCh。由于n是固定值，总费用的变化取决于m值。这个场景用来当做一般计算范式的模型，通常情况下我们需要检查队列中的每个成员，并且维护一个目前的获胜者，来找出序列中的最大或最小值。雇佣问题是对哪一个成员当前获胜的更新频繁程度建立模型。

这里伪代码就不给出了，编写较为简单。雇用问题着重要理解一个随机算法的概念。

部分习题很有意思，下面给出5.1-2和5.1-3的个人解答

5.1-2 假设Random(a,b)以相同概率返回a到b之间的任何一个数字，描述Random(a,b)过程的一种实现，它只调用现有实现Random（0，1）。作为a和b的函数，你的程序的期望运行时间是多少？假设Ramdom（0，1）的运行时间是常数。

import random
def random_self(a,b):
    x2=bin(b).replace('0b','')
    while(1):
        r='0b'
        for i in range(len(x2)):
            m=random.randint(0,1)
            r=r+str(m)
        final=eval(r)
        if final>=a and final<=b:
            return final
for i in range(20):
    print(random_self(1,8))

具体思路：将输入参数的最大值看成二进制数，每次调用一个random.randint(0,1)函数，产生0或者1的数，
在b的长度范围内，能产生len(b)位的二进制数，进行是否在a,b范围内的判断，如果是，则返回，如果不是，
则循环进行操作。例如在0,10范围内随机产生，能产生出0000~1111的二进制数，每个数产生的概率相同，
在进行if判断后输出，所以产生0,10范围内的整数概率也相同。
缺点：if判断后可能存在多次执行while循环的结果。

最后看了一下解答，发现与自己的想法不谋而合，也相当于是理解成二进制，下面贴出答案

import random
from math import *
def random_self(a,b):
    run=ceil(log(b-a,2))
    if (b-a)==pow(2,run):
        run+=1
    while True:
        power=1
        sum=0
        for i in range(0,run):
            sum+=random.randint(0,1)*power
            power*=2
        if sum<=(b-a):
            return (a+sum)
for i in range(20):
    print(random_self(0,4))

5.1-3假设你希望以各1/2的概率输出0和1。你可以自由使用一个输出0或1的过程 BIASED-RANDOM。它以概率p输出1，以概率1-p输出0，其中0<p<1，但是你并不知道p的值。给出一个利用BIASED- RANDOM作为子程序的算法，返回一个无偏向的结果。你的算法的期望运行时间是多少？

import random
def biased_random():
    a=random.randint(0,1)
    b=random.randint(0,1)
    if a!=b:
        return a

这个相对简单一些，直接利用对称性即可。

5.3随机算法（随机排列数组）

在许多情况下，我们对输入分布知识知之甚少；即使知道关于输入分布的某些信息，也无法对这种分布建立模型。然而通过使一个算法中的某些部分的行为随机化，就常常可以利用概率和随机性作为算法设计和分析的工具。比如在雇佣问题中，如果雇佣代理给我们一份应聘者的名单，每天我们随机地挑选一个应聘者进行面试，从而确保了应聘序列的随机性。更一般地，如果一个算法的行为不只有输入决定，同时也由随机数生成器所产生的数值决定，则称这个算法是随机的。

python中随机排列数组可以利用自带函数shuffle.

import random
list1=[1,2,3,4,5,6,7,8,9,10]
random.shuffle(list1)#对列表进行随机排序
print(list1)

利用优先算法排序：先随机产生一个相同长度的数组，n**3是为了尽量不使得随机数组内的元素相同，再对随机数组进行排序，排序的同时对原数组进行相应的位置交换。类似加权的概念。有一个缺陷是不能保证随机产生的数组的元素互不相同，如果出现相同的元素，对原数组的随机排列并非是真正随机的

def permute_by_sorting(a):
    permute_list=[]
    n=len(a)
    for i in range(0,n):
        permute_list.append(random.randint(1,n**3))
    print(permute_list)
    for i in range(0,n):
        for j in range(i+1,n):
                if permute_list[j]<permute_list[i]:
                    permute_list[i],permute_list[j]=permute_list[j],permute_list[i]
                    a[i],a[j]=a[j],a[i]

使用原址排列给定数组：

import random
def randomize_in_place(a):
    n = len(a)
    for i in range(n):
        j = random.randint(i,n-1) #j=random.randint(1,n-1)是错误的
        a[i],a[j]=a[j],a[i]
    return a

为什么注释部分是错误的？参照为何对称的算法是错误的。实际上也很好理解，如果randint(1,n)的话，在每个位置上，都会有n种可能，意味着 $n*n*n...*n$ ,总计n个位置，因此有n^n种可能的结果，但是n个排列自由n!种情况，即使要出现重复的情况，重复的次数也应该相等，但是n^n并不能整除n!，因此这种算法是错误的