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 01 ring is produced , and the 2^n
number we get
are just from 0 to 2^n1 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[indexinput+1:index+2],input) not
in set:
if(len(list) >= input ):
set.add(list2int(list[indexinput+1:index+2],input))
ring(index+1,number)
if(flag == 1):
return
if(len(list) >= input ):
set.remove(list2int(list[indexinput+1:index+2],input))
list = list[:index]
list.append(0)
if len(list) < input or list2int(list[indexinput+1:index+2],input) not
in set:
if(len(list) >= input ):
set.add(list2int(list[indexinput+1:index+2],input))
ring(index+1,number)
if(flag == 1):
return
if(len(list) >= input ):
set.remove(list2int(list[indexinput+1:index+2],input))
list = list[:index]
ring(0,number1)
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 ! 5 1289
Bo Yang enlightened us with: I have writen a python program to slove a problem described as below:
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
On 31/05/2006 4:58 PM, Bo Yang wrote: 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 ,
Sorry, I can't understand that. It would be very helpful if you wrote
out (for example, when n == 3) what the "01 ring" looks like.
Do you mean ring as in a circular buffer, or do you mean ring as in
"groups, rings, and fields"?
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 01 ring is produced , and the 2^n number we get are just from 0 to 2^n1 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
Problem! See below. number = 2**input set = set()
Problem!! list = []
Problem!!!
It is a very bad habit to reuse or "shadow" the names of builtin
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()
? def list2int(l , n ):
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.
ret = 0 for x in l : if( n == 0 ):
Please lose the (); they are redundant.
Please read http://www.python.org/dev/peps/pep0008/
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.
break
[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
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
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 01 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^n1 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[indexinput+1:index+2],input) not in integers:
if len(ring) >= input :
integers.add(list2int(ring[indexinput+1:index+2],input))
getring(index+1,range)
if flag == 1:
return
if len(ring) >= input :
integers.remove(list2int(ring[indexinput+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[indexinput+1:index+2],input) not in integers:
if len(ring) >= input :
integers.add(list2int(ring[indexinput+1:index+2],input))
getring(index+1,range)
if flag == 1 :
return
if len(ring) >= input :
integers.remove(list2int(ring[indexinput+1:index+2],input))
ring = ring[:index]
#begin process
getring(0,range1)
#output the result list
print ring
On 31/05/2006 7:20 PM, Bo Yang wrote: 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 !
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.setrecursionlimit. Please take careful note of the warnings in
the documentation:
"""
setrecursionlimit( 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 platformdependent. 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 toohigh limit can lead to a crash.
"""
I tried it with sys.setrecursionlimit(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 nonrecursively?
Best of luck,
John This discussion thread is closed Replies have been disabled for this discussion. Similar topics
6 posts
views
Thread by Jack Smith 
last post: by

16 posts
views
Thread by cody 
last post: by

17 posts
views
Thread by savesdeday 
last post: by

10 posts
views
Thread by bpontius 
last post: by

113 posts
views
Thread by Bonj 
last post: by

4 posts
views
Thread by FBM 
last post: by

2 posts
views
Thread by Sherrie Laraurens 
last post: by

2 posts
views
Thread by Julio C. Hernandez Castro 
last post: by
 
11 posts
views
Thread by Dijkstra 
last post: by
          