在python中随机选择,工作异常

提问

我正在尝试实现我刚刚在课堂上学习的rselect算法.但是,似乎无法弄清楚我在实现中出了什么问题.这是我的代码. *编辑*
:我尝试使用David答案中提供的信息,但是我的代码仍然很奇怪.这是修改后的代码:

def rselect(seq,length,i):# i is the i'th order statistic.
    if len(seq)<=1:return seq
    lo,pi,hi,loc_pi= random_partition(seq
    if loc_pi==i:return pi 
    if loc_pi>i:return rselect(lo,loc_pi-1,i) 
    elif loc_pi<i:return rselect(hi,length-loc_pi,i-loc_pi)#
from random import choice  
def random_partition(seq):
    pi =choice(seq)
    #print 'pi',pi
    loc_pi=seq.index(pi)
    print 'Location',loc_pi
    lo=[x for x in seq if x<=pi]
    hi=[x for x in seq if x>pi]
    return lo,pi,hi,len(lo)+1   #--A

def test_rselect(seq,i):
    print 'Sequence',seq
    l=len(seq)
    print 'Statistic', rselect(seq,l,i)

但是,输出在不同时间甚至有时都是不同的!我对算法和python都不熟悉,对我在哪里出错的任何帮助将不胜感激.
编辑:每次运行代码时,我会为ith顺序统计获取不同的值,这是我的问题
例如,下面的代码每次运行都会给出

Revised Output:
/py-scripts$python quicksort.py
Sequence [54, -1, 1000, 565, 64, 2, 5]
Statistic Location 1
-1
@ubuntu:~/py-scripts$python quicksort.py
Sequence [54, -1, 1000, 565, 64, 2, 5]
Statistic Location 5
Location 1
Location 0
-1

预期输出:我期望在这里找到第i个顺序统计信息.

因此

test_rselect([54,-1,1000,565,64,2,5],2)始终应返回5作为统计信息.

我在该实现中出错的任何帮助将是有帮助的.
编辑2:通过尝试分析算法,我相信错误在于我如何返回标记为A的行中的枢轴位置(loc_pi).考虑上述程序的以下事件序列.

test_rselect( [ 55, 900, -1,10, 545, 250], 3) // call to input array 

calls rselect ([ 55, 900, -1,10, 545, 250],6,3)

    1st  call to random_partition:
        pi=545 and loc_pi=4
        lo=[55,-1,10,250,545]
        hi=[900]
    return to rselect function (lo,545,hi,6)
    here loc_pi>i: so rselect(lo,5,3)// and discard the hi part

    2nd recursive call to rselect:
    2nd recursive call to random_partition:
        call random_partition on (lo) // as 'hi' is discarded
        pi=55 loc_pi=0
        lo=[-1,10,55]
        hi=[250,545]
        return to rselect(lo,55,hi,4)
        here loc_pi>i: rselect(lo,3,3)// The pivot element is lost already as it is in 'hi' here!!

为了获得正确的o / p,对如何处理枢轴元素的位置的任何帮助都将有所帮助.设置赏金,以清楚地说明我做错了什么地方以及如何纠正它的答案(欢迎提供很好的提示,因为我希望学习:)).期待很好的答案!

最佳答案

我不认为存在任何主要错误(关于如何返回数据透视图或其他方式),这只是很多(一甚至两个)的混乱,而且我想您的意思是要与i进行比较rselect的第一行,不是1.

这是我的看法,请尽量减少更改:

def rselect(seq,length,i):# i is the i'th order statistic.
    if len(seq)<=i:return seq
    lo,pi,hi,loc_pi= random_partition(seq)
    if loc_pi==i:return pi 
    if loc_pi>i:return rselect(lo,loc_pi,i) 
    elif loc_pi<i:return rselect(hi,length-(loc_pi+1),i-(loc_pi+1))
from random import choice  
def random_partition(seq):
    pi =choice(seq)
    lo=[x for x in seq if x<=pi]
    hi=[x for x in seq if x>pi]
    return lo,pi,hi,len(lo)-1

编辑:这是一个存在重复元素的版本.现在,我不得不进行更多更改,因此我取出了一些令我感到困惑的内容,以使自己更轻松.

def rselect(seq,i):# i is the i'th order statistic.
    if len(seq)<=i:return seq
    lo,pi,hi= random_partition(seq)
    if i < len(lo):return rselect(lo,i) 
    if i < len(seq)-len(hi): return pi 
    return rselect(hi,i-(len(seq)-len(hi)))
from random import choice
def random_partition(seq):
    pi =choice(seq)
    lo=[x for x in seq if x<pi]
    hi=[x for x in seq if x>pi]
    return lo,pi,hi

def test_rselect(seq,i):
    print 'Sequence',seq
    stat=rselect(seq,i)
    print 'Statistic', stat
评论