An algorithm problem

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 !

.

Relevant Pages

  • Re: An algorithm problem
    ... I have writen a python program to slove a problem described as below: ... (Forgive my poor English!) ... Do you mean ring as in a circular buffer, or do you mean ring as in ...
    (comp.lang.python)
  • Re: An algorithm problem
    ... what we exapct from the algorithm is a list of 0 or 1, ... We can take it as a ring, and fetch any continuous 2 numbers from it, finally get four combinations: ... for i in temp: ... global flag ...
    (comp.lang.python)
  • Re: What Is It?
    ... smokes: ... smoking said 'gar but cn't seem to ... larger ring, but this thing is not bad! ... Happy Flag Day also - and agree w/ the AG thoughts.... ...
    (alt.smokers.cigars)
  • Re: What Is It?
    ... smokes: ... ring, EMS wrapper that has a red & white band that says ... smoking said 'gar but cn't seem to ... Happy Flag Day also - and agree w/ the AG thoughts.... ...
    (alt.smokers.cigars)
  • Re: isdnlog: Programm erst nach n-ten Klingeln starten
    ... sondern erst nach einer bestimmten ... | With connect or ring flag you can specify an interval, ...
    (de.comp.os.unix.linux.isdn)