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--
http://mail.python.org/mailman/listinfo/python-list
