473,556 Members | 2,502 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

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(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 !

May 31 '06 #1
5 1439
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
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
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/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.
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
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
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
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
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
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.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
May 31 '06 #6

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

6
8872
by: Jack Smith | last post by:
Hello, any help appreciated with following problem. I figured out the algorithm (I think), just having trouble proving it is optimal. Suppose we are given n tasks each of which takes 1 unit time to complete. Suppose further that each task has a deadline by which it is expected to finish. IF a task is not finished by the deadline, a...
16
2639
by: cody | last post by:
I have to write an algorithm with must ensure that objects are put in buckets (which are always 4 in size). The objects have two properties: A and B. It is not allowed that in a bucket are objects with the same A or B value. But there can be more than one object with A = null or B = null in the bucket. Sometimes there is only one valid...
17
6496
by: savesdeday | last post by:
In my beginnning computer science class we were asked to translate a simple interest problem. We are expected to write an algorithm that gets values for the starting account balance B, annual interest rate I, and annual service charge S. Your algorithm would then compute and print out the total amount of interest earned during the year and...
10
4961
by: bpontius | last post by:
The GES Algorithm A Surprisingly Simple Algorithm for Parallel Pattern Matching "Partially because the best algorithms presented in the literature are difficult to understand and to implement, knowledge of fast and practical algorithms is not commonplace." Hume and Sunday, "Fast String Searching", Software - Practice and Experience,...
113
12218
by: Bonj | last post by:
I was in need of an encryption algorithm to the following requirements: 1) Must be capable of encrypting strings to a byte array, and decyrpting back again to the same string 2) Must have the same algorithm work with strings that may or may not be unicode 3) Number of bytes back must either be <= number of _TCHARs in * sizeof(_TCHAR), or the...
4
4271
by: FBM | last post by:
Hi, I am working on a program that simulates one of the elements of ATM. The simulation stores events which occurs every some milliseconds for a certain amount of time. Every time that an event is stored in a double linked list, the whole list is sorted for the next round. My problem appears when subjecting the program to heavy load, that...
2
2139
by: Sherrie Laraurens | last post by:
Hi all, I'm trying to write a generic algorithm routine that will take begin and end iterators of a container, iterate through the range and perform a "calculation" of sorts. The trouble is that the algorithm will behave differently for the two different types. I've considered calling the algorithm foo_A and foo_B, but I don't like that...
2
7269
by: Julio C. Hernandez Castro | last post by:
Dear all, We have just developped a new block cipher called Raiden, following a Feistel Network structure by means of genetic programming. Our intention now consists on getting as much feedback as possible from users, so we encourage you to test the algorithm and send us your opinion. We would also like to receive enhancements and new...
10
2414
by: Sunway | last post by:
hello guys i have a bunsh of questions in java and algorithm most of them i didnt have a problem in them but two i had a diffculty in them could u help me in them please coz its urgent . the questions are: Q1.DVD Sales and Shipping Algorithm Design: You are to design an algorithm to calculate the total cost of a customer order for a...
11
2272
by: Dijkstra | last post by:
Hi folks! First, this is the code I'm using to expose the problem: ------------------------------------------------------------------ #include <functional> #include <string> #include <iostream> using namespace std;
0
7547
by: Hystou | last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it. First, let's disable language...
0
7828
Oralloy
by: Oralloy | last post by:
Hello folks, I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>". The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed. This is as boiled down as I can make it. ...
0
8060
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that...
1
7589
by: Hystou | last post by:
Overview: Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For...
0
7907
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the...
0
6178
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then...
1
5452
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules. He will explain when you may want to use classes...
0
5171
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert...
0
3597
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.