自留地

题目： 2n个数，一半奇数，一半偶数，设计一个程序让奇数位上的数是奇数，偶数位上的是偶数

要求：时空复杂度尽量低

看到群里发的这个题目，随手写了个一个答案：

def swap(a, i, j): 
    a[i] = a[i] + a[j]
    a[j] = a[i] - a[j]
    a[i] = a[i] - a[j]
        
def Fun():
    the_list = [x for x in range(100)]
    print "orginal:", the_list
    random.shuffle(the_list)
    print "shuffled:", the_list
    i,j = 0,1
    nSwap = 0
    while nSwap < 50 and max(i,j) < 100:
        if the_list[i] % 2 != 0 and the_list[j] % 2 == 0 :
            swap(the_list,i,j)
            i += 2
            j += 2
            nSwap += 1
        elif the_list[i] % 2 == 0 :
            i += 2
        elif the_list[j] % 2 != 0 :
            j += 2
    print "sorted:", the_list

经penny等群友的提醒，优化一下，第二版：

def Fun2():
    the_list = [x for x in range(100)]
    print "orginal:", the_list
    random.shuffle(the_list)
    print "shuffled:", the_list 
    for i,j in zip([pos for pos in range(0,100,2) if (the_list[pos] + pos) % 2 != 0],
                              [pos for pos in range(1,100,2) if (the_list[pos] + pos) % 2 != 0]):
        the_list[i], the_list[j] = the_list[j], the_list[i]
    print "sorted:", the_list

附：penny发了一个点积的优化

A[]={<0,4>,<3,5>,<8,3>}
B[]={<3,5>,<9,3>}

C=A*B = {<3,25>}

for(i=0,j=0;i<lenA&&j<lenB;)
{
	k=0;	
	if(A[i].index == B[j].index)
	{
		C[k].index = A[i].index;
		C[k].value = A[i].value * B[j].value
		k++
	}
	else if(A[i].index < B[j].index)
	{
		i++;
	}
	else if(A[i].index > B[j].index )
	{
		j++;
	}
}

A_I[]={0,3,8}
B_I[]={3,9}
A_V[]={4,5,9}
B_V[]={5,3}
for(i=0,j=0;i<lenA&&j<lenB;)
{
	k=0;
	if(A_I[i] == B_I[j])
	{
		C[k].index = A_I[i];
		C[k].value = A_V[i]*B_V[j];
	}
	else if(A_I[i] < B_I[j])
	{
		i++;
	}
	else
	{
		j++;
	}
}

for(i=0,j=0;i<lenA&&j<lenB;)
{
	k=0;
	i=0;
	j=0;
	bool equal  =  A_I[i] == B_I[j];
	bool smaller=  A_I[i] < B_I[j]; 
	bool bigger =  A_I[i] > B_I[j];
	C[k].index  =  equal*A_I[i];
	C[k].value  =  equal*A_V[i]*B_V[j];
	k+=equal;
	i+=equal;
	j+=equal;
        i+=smaller;
	j+=biger;	
}	

给你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())

Run