[原创]生成自描述的序列

duweifu posted @ 2011年3月23日 16:08 in Scrawl with tags 面试题 , 874 阅读

给你10分钟时间,根据上排给出十个数,在其下排填出对应的十个数  
要求下排每个数都是先前上排那十个数在下排出现的次数。  
上排的十个数如下:  
【0,1,2,3,4,5,6,7,8,9】

最省脑细胞的做法自然是盲搜:

def selfDescribableSeqence(arr):
    for guess in range(9*10**len(arr)):
        guess_list = (['0']*(10-len(str(guess))))
        guess_list.extend(list(str(guess)))
        if isOK(arr, guess_list):
            return guess_list   
    
def isOK(top, bottom):
    def freq(val):
        return len(list(filter(lambda x: x == val, bottom)))
    return len(list(filter(lambda x: str(freq(x)) == bottom[int(x)], top))) == len(top)
 

if __name__ == '__main__':
    print(selfDescribableSeqence(list(map(str, list(range(0,10))))))


显然,脑细胞是省下了,CPU就太浪费了,要判断解空间之外的很多分支。改成宽度优先:

def selfDescribableSeqence():
    res = list(range(10))
    while True:
        for pos in range(10):
            adjust(res, pos)
            if isOK(res):
                return res

def freq(arr,val):
    return len(list(filter(lambda x: x == val, arr)))
    
def adjust(arr, pos):
    the_freq = freq(arr, pos)
    if arr[pos] != the_freq:
        arr[pos] = the_freq
        pos = the_freq

def isOK(arr):
    id_and_value = [(id, val) for (id,val) in enumerate(arr)]
    return len(list(filter(lambda x : freq(arr, x[0])==x[1], id_and_value))) == len(id_and_value)

if __name__ == '__main__':
    print(selfDescribableSeqence())

 

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter