An algorithm problem

Bo Yang struggleyb at gmail.com
Wed May 31 08:58:39 CEST 2006


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 !




More information about the Python-list mailing list