Re: An algorithm problem
- From: Bo Yang <struggleyb@xxxxxxxxx>
- Date: Wed, 31 May 2006 17:20:43 +0800
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(list2int(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(list2int(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
- Follow-Ups:
- Re: An algorithm problem
- From: John Machin
- Re: An algorithm problem
- References:
- An algorithm problem
- From: Bo Yang
- Re: An algorithm problem
- From: Sybren Stuvel
- An algorithm problem
- Prev by Date: Re: An algorithm problem
- Next by Date: Re: summarize text
- Previous by thread: Re: An algorithm problem
- Next by thread: Re: An algorithm problem
- Index(es):
Relevant Pages
|
