Python: Depth first search (1)

Abstract:give the all possible combinations of 'abc' using the algorithm of depth first search (DFS).

Here is the details of DFS

0 0 ['a', 0, 0] [1, 0, 0] #DFS()#0

1 1 ['a', 'b', 0] [1, 1, 0]#enter DFS()#1

2 2 ['a', 'b', 'c'] [1, 1, 1]#enter DFS()#2

3 ['a', 'b', 'c'] [1, 1, 1]#enter DFS()#3 and return

2 2 ['a', 'b', 'c'] [1, 1, 0] out #return to DFS()#2 and leave

1 1 ['a', 'b', 'c'] [1, 0, 0] out #return to DFS()#1

1 2 ['a', 'c', 'c'] [1, 0, 1] #loop in DFS()#1 and then enter DFS()#2

2 1 ['a', 'c', 'b'] [1, 1, 1] #

3 ['a', 'c', 'b'] [1, 1, 1]

2 1 ['a', 'c', 'b'] [1, 0, 1] out

1 2 ['a', 'c', 'b'] [1, 0, 0] out

0 0 ['a', 'c', 'b'] [0, 0, 0] out

0 1 ['b', 'c', 'b'] [0, 1, 0]

1 0 ['b', 'a', 'b'] [1, 1, 0]

2 2 ['b', 'a', 'c'] [1, 1, 1]

3 ['b', 'a', 'c'] [1, 1, 1]

2 2 ['b', 'a', 'c'] [1, 1, 0] out

1 0 ['b', 'a', 'c'] [0, 1, 0] out

1 2 ['b', 'c', 'c'] [0, 1, 1]

2 0 ['b', 'c', 'a'] [1, 1, 1]

3 ['b', 'c', 'a'] [1, 1, 1]

2 0 ['b', 'c', 'a'] [0, 1, 1] out

1 2 ['b', 'c', 'a'] [0, 1, 0] out

0 1 ['b', 'c', 'a'] [0, 0, 0] out

0 2 ['c', 'c', 'a'] [0, 0, 1]

1 0 ['c', 'a', 'a'] [1, 0, 1]

2 1 ['c', 'a', 'b'] [1, 1, 1]

3 ['c', 'a', 'b'] [1, 1, 1]

2 1 ['c', 'a', 'b'] [1, 0, 1] out

1 0 ['c', 'a', 'b'] [0, 0, 1] out

1 1 ['c', 'b', 'b'] [0, 1, 1]

2 0 ['c', 'b', 'a'] [1, 1, 1]

3 ['c', 'b', 'a'] [1, 1, 1]

2 0 ['c', 'b', 'a'] [0, 1, 1] out

1 1 ['c', 'b', 'a'] [0, 0, 1] out

0 2 ['c', 'b', 'a'] [0, 0, 0] out

['abc', 'acb', 'bac', 'bca', 'cab', 'cba']

Here is the code:

# -*- coding: utf-8 -*-
"""
Created on Sun Jun  7 18:44:43 2015

@author: yuan
"""

#depth first search
class depth_first:
   
    def __init__(self,pool):
        self.pool=list(pool) #string to list
        self.out=[]
       
    def DFS(self, arr, tag, step):
        n=len(self.pool)
       
        #print step, arr, tag
        if step==n:
            self.out.append("".join(arr)) #list to string
            print "\t", step, arr, tag
            return
   
        for i in range(0, n): #arrange the pool from head to end always
            #print i,self.pool[i], tag[i]
            if tag[i]==0:  #unselected only
                print step, i, arr, tag, 'in'               
                arr[step]=self.pool[i]
                tag[i]=1
                print step, i, arr, tag               
                self.DFS(arr, tag, step+1)
                tag[i]=0
                print step, i, arr, tag, 'out'
           
    def combination(self):
        arr=[0]*len(self.pool)  # store a new combination
        tag=[0]*len(self.pool) #judge which one is selected. 1 is selected
        #search
        self.DFS(arr, tag, 0)
        return self.out

#main programming
pool='abc'
s=depth_first(pool)
out=s.combination()
print out