Hi , I have writen a python program to slove a problem described as below: (Forgive my poor English !)
Put the 2^n 0 or 1 to form a ring , and we can select any continuous n ones from the ring to constitute a binary number . And obviously we can get 2^n selections , so the question is : Given a number n and you must Povide an algorithm by which the 0-1 ring is produced , and the 2^n number we get are just from 0 to 2^n-1 uniquely and entirely . So I write the following program to slove the question , and it works well for the n below 10 flag = 0 input = 10 number = 2**input set = set() list = [] def list2int(l , n ): ret = 0 for x in l : if( n == 0 ): break if x : ret = ( ret << 1 ) | 1 else : ret = ( ret << 1 ) | 0 n = n - 1 return ret def ring( index , number ): global list , set temp = [] if( number < index ): #the range overflow #detect whether the remain of the list is ok ? for x in xrange(1,input): begin = number - input + 1 + x l = list[begin:] + list[0:x] i = list2int(l , input ) if i in set: for i in temp: set.remove(i) return else: set.add(i) temp.append(i) #index = index + 1 global flag flag = 1 return list.append(1) if len(list) < input or list2int(list[index-input+1:index+2],input) not in set: if(len(list) >= input ): set.add(list2int(list[index-input+1:index+2],input)) ring(index+1,number) if(flag == 1): return if(len(list) >= input ): set.remove(list2int(list[index-input+1:index+2],input)) list = list[:index] list.append(0) if len(list) < input or list2int(list[index-input+1:index+2],input) not in set: if(len(list) >= input ): set.add(list2int(list[index-input+1:index+2],input)) ring(index+1,number) if(flag == 1): return if(len(list) >= input ): set.remove(list2int(list[index-input+1:index+2],input)) list = list[:index] ring(0,number-1) print list But when the n reach 10 , Python report the stack is exhausted : RuntimeError: maximum recursion depth exceeded And my question is , where can I put some optimization to make the code can work more smoothly with more greater n ? Thanks in advance !
-- http://mail.python.org/mailman/listinfo/python-list
