Python: Depth first search (2)

Abstract: combination with replicates

Give all combinations of the string 'aabcc':

['aabcc', 'aacbc', 'aaccb', 'abacc', 'abcac', 'abcca', 'acabc', 'acacb', 'acbac', 'acbca', 'accab', 'accba', 'baacc', 'bacac', 'bacca', 'bcaac', 'bcaca', 'bccaa', 'caabc', 'caacb', 'cabac', 'cabca', 'cacab', 'cacba', 'cbaac', 'cbaca', 'cbcaa', 'ccaab', 'ccaba', 'ccbaa']

Here is the script:

# -*- coding: utf-8 -*-

"""

Created on Sun Jun 7 18:44:43 2015

@author: yuan

"""

import numpy as np

#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]==0 and tag[tag[i,1],0]==0: #unselected only

print step, i, arr, tag, 'in'

arr[step]=self.pool[i]

tag[i,0]=1

print step, i, arr, tag

self.DFS(arr, tag, step+1)

tag[i,0]=0

print step, i, arr, tag, 'out'

def combination(self):

arr=[0]*len(self.pool) # store a new combination

#2D list

#judge which one is selected. 1 is selected in the first column

tag=np.zeros((len(self.pool),2) )

#give the first index if replicates present in the second column

D={}

for index, value in enumerate(self.pool):

if not value in D:

D[value]=index

tag[index,1]=D[value]#alway the index which is firstly present

#search

self.DFS(arr, tag, 0)

return self.out

#main programming

#combination if there are replicates.

pool='aabcc'

s=depth_first(pool)

out=s.combination()

print out

#end#