Python: Depth first search (3)

Abstract: sub-combination with replicates

Give all combinations of 2 characters from the string 'aabcc':

['ab', 'ac', 'aa', 'ba', 'bc', 'ca', 'cb', 'cc']

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,num):

self.pool=list(pool) #string to list

self.num=num

self.out=[]

def DFS(self, arr, tag, step):

n=len(self.pool)

#print step, arr, tag

if step==self.num:

new_str="".join(arr)

if not new_str in self.out:

self.out.append(new_str) #list to string

print "\t", 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]*self.num # 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

#sub-combination if there are replicates.

pool='aabcc'

s=depth_first(pool, 2)

out=s.combination()

print out

#end#