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

Reply via email to