469,936 Members | 2,466 Online

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:
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 ):
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 ):
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 ?

May 31 '06 #1
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

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
May 31 '06 #2
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 "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"?
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 Problem! See below. number = 2**input
set = set() Problem!! list = [] 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

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.

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
May 31 '06 #3
I am sorry , and thanks for your friendliness .
I have change my source code for more meaningful variable name and more
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
May 31 '06 #4
I am sorry , and thanks for your friendliness .
I have change my source code for more meaningful variable name and more
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:
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 :
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 :
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
May 31 '06 #5
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
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 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.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 non-recursively?

Best of luck,
John
May 31 '06 #6

 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 10 posts views Thread by Sunway | last post: by 11 posts views Thread by Dijkstra | last post: by reply views Thread by eddparker01 | last post: by reply views Thread by lanliddd | last post: by reply views Thread by isladogs | last post: by 1 post views Thread by isladogs | last post: by reply views Thread by Trystan | last post: by reply views Thread by Trystan | last post: by reply views Thread by Romlus | last post: by 1 post views Thread by MikeCant | last post: by 2 posts views Thread by Usman55 | last post: by