An algorithm problem

[Bo Yang]

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(list2in t(list[index-input+1:index+2],input))
ring(index+1,nu mber)
if(flag == 1):
return
if(len(list) >= input ):
set.remove(list 2int(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(list2in t(list[index-input+1:index+2],input))
ring(index+1,nu mber)
if(flag == 1):
return
if(len(list) >= input ):
set.remove(list 2int(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 !

[Sybren Stuvel]

Re: An algorithm problem

Bo Yang enlightened us with:[color=blue]
> I have writen a python program to slove a problem described as
> below:[/color]

Please post again, but then leaving indentation intact, since this is
unreadable.

Sybren
--
The problem with the world is stupidity. Not saying there should be a
capital punishment for stupidity, but why don't we just take the
safety labels off of everything and let the problem solve itself?
Frank Zappa

[John Machin]

Re: An algorithm problem

On 31/05/2006 4:58 PM, Bo Yang wrote:[color=blue]
> 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 ,[/color]

Sorry, I can't understand that. It would be very helpful if you wrote
out (for example, when n == 3) what the "0-1 ring" looks like.

Do you mean ring as in a circular buffer, or do you mean ring as in
"groups, rings, and fields"?
[color=blue]
> 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[/color]
Problem! See below.[color=blue]
> number = 2**input
> set = set()[/color]
Problem!![color=blue]
> list = [][/color]
Problem!!!

It is a very bad habit to re-use or "shadow" the names of built-in
functions (input, set, list). Please stop now. Try to think of
meaningful names for your input number, your set and your list.

What do you think would happen if your code needed a second set and you
wrote:
set2 = set()
?
[color=blue]
>
> def list2int(l , n ):[/color]

Please don't use "l" (that's "L".lower() ) as an identifier. It is far
too easily confused with the digit "1" in many fonts.
[color=blue]
> ret = 0
> for x in l :
> if( n == 0 ):[/color]
Please lose the (); they are redundant.

Please read http://www.python.org/dev/peps/pep-0008/
in particular the section on whitespace.
(Please forgive my exceedingly poor putonghua!) Dui bu qi, women shi
laowai -- we can't read our characters easily without the customary spacing.
[color=blue]
> break[/color]

[snip]

Your code appears without any indentation in the two newsreaders that I
tried. As a result, I (and I presume others interested in helping you)
can't read your code without a lot of guesswork, and certainly can't run
it. Try changing leading tabs to spaces, and sending it again.
Alternatively attach it as a file.

Regards,
John

[Bo Yang]

Re: An algorithm problem

I am sorry , and thanks for your friendliness .
I have change my source code for more meaningful variable name and more
comments follow the instructions
John has writen . I think that is useful for you to look my code .

And this time I put the code in the attachment . Indeed , I write that
in the Eclipse Pydev , I don't know why
it lose its idention in the mailing list .

Also , I forget an example for the question , and I compensate for it :

Given the integer 2 for instance :
what we exapct from the algorithm is a list of 0 or 1 , for this
instance it is 1 1 0 0 .
We can take it as a ring , and fetch any continuous 2 numbers from it ,
finally get four combinations :
11 , 10 , 00 , 01
and they are 3 , 2 , 0 , 1 .


I hope this time it is clear for all to understand what problem confront
me .
And again I am sorry for the trouble , thanks for you again !

Best Regard
Bo Yang

[Bo Yang]

Re: An algorithm problem

I am sorry , and thanks for your friendliness .
I have change my source code for more meaningful variable name and more
comments follow the instructions
John has writen . I think that is useful for you to look my code .

And this time I put the code in the attachment . Indeed , I write that
in the Eclipse Pydev , I don't know why
it lose its idention in the mailing list .

Also , I forget an example for the question , and I compensate for it :

Given the integer 2 for instance :
what we exapct from the algorithm is a list of 0 or 1 , for this
instance it is 1 1 0 0 .
We can take it as a ring , and fetch any continuous 2 numbers from it ,
finally get four combinations :
11 , 10 , 00 , 01
and they are 3 , 2 , 0 , 1 .


I hope this time it is clear for all to understand what problem confront
me .
And again I am sorry for the trouble , thanks for you again !

Best Regard
Bo Yang

#This is the file for the solution of the 0-1 ring problem
#in the csdn algorithm forum
#The input to this program is a integer n ,
#The ouuput of the algorithm is the a list of 2^n elements
#in which every number in the range of 0~2^n-1 just appear
#once exactly .

flag = 0 # whether we found the ring
input = 2 # the input n
range = 2**input #2^n
integers = set() #the set of the numbers we have in the ring now
ring = [] # the ring

def list2int(list , n ): #convert a list contains only 0 or 1 to a integer
ret = 0
for x in list :
if n == 0 :
break
if x :
ret = ( ret << 1 ) | 1
else :
ret = ( ret << 1 ) | 0
n = n - 1
return ret


def getring( index , range ): #the main function for the problem
global ring , integers
temp = []
if range < index : #the range overflow
#detect whether the remain of the list contains the remain integers
for x in xrange(1,input) :
begin = range - input + 1 + x
l = ring[begin:] + ring[0:x]
i = list2int(l , input )
if i in integers:
for i in temp:
integers.remove (i)
return
else:
integers.add(i)
temp.append(i)
#index = index + 1
#if we reach here , it indicat that we succeed
global flag
flag = 1
return

#test whether 1 in the position is ok?
ring.append(1)
if len(ring) < input or list2int(ring[index-input+1:index+2],input) not in integers:
if len(ring) >= input :
integers.add(li st2int(ring[index-input+1:index+2],input))
getring(index+1 ,range)
if flag == 1:
return
if len(ring) >= input :
integers.remove (list2int(ring[index-input+1:index+2],input))

#test whether 0 in this position is ok?
ring = ring[:index]
ring.append(0)
if len(ring) < input or list2int(ring[index-input+1:index+2],input) not in integers:
if len(ring) >= input :
integers.add(li st2int(ring[index-input+1:index+2],input))
getring(index+1 ,range)
if flag == 1 :
return
if len(ring) >= input :
integers.remove (list2int(ring[index-input+1:index+2],input))

ring = ring[:index]

#begin process
getring(0,range-1)

#output the result list
print ring

[John Machin]

Re: An algorithm problem

On 31/05/2006 7:20 PM, Bo Yang wrote:[color=blue]
> I am sorry , and thanks for your friendliness .
> I have change my source code for more meaningful variable name and more
> comments follow the instructions
> John has writen . I think that is useful for you to look my code .
>
> And this time I put the code in the attachment . Indeed , I write that
> in the Eclipse Pydev , I don't know why
> it lose its idention in the mailing list .
>
> Also , I forget an example for the question , and I compensate for it :
>
> Given the integer 2 for instance :
> what we exapct from the algorithm is a list of 0 or 1 , for this
> instance it is 1 1 0 0 .
> We can take it as a ring , and fetch any continuous 2 numbers from it ,
> finally get four combinations :
> 11 , 10 , 00 , 01
> and they are 3 , 2 , 0 , 1 .
>
>
> I hope this time it is clear for all to understand what problem confront
> me .
> And again I am sorry for the trouble , thanks for you again !
>[/color]

OK, it was able to be run this time. The algorithm is recursive. For
input == n, it needs stack of depth 2**n. The default limit is 1000, and
2**9 < 1000 < 2**10 -- so it fails when n >= 10. You can change this
with sys.setrecursio nlimit. Please take careful note of the warnings in
the documentation:

"""
setrecursionlim it( limit)

Set the maximum depth of the Python interpreter stack to limit. This
limit prevents infinite recursion from causing an overflow of the C
stack and crashing Python.
The highest possible limit is platform-dependent. A user may need to set
the limit higher when she has a program that requires deep recursion and
a platform that supports a higher limit. This should be done with care,
because a too-high limit can lead to a crash.
"""

I tried it with sys.setrecursio nlimit(2**n+10) -- that worked up to 13
on my Windows XP box, throwing a MemoryError (and a long stack trace!)
for n == 14. Be careful; yours may crash more horribly than that.

Can your algorithm be expressed non-recursively?

Best of luck,
John