Python: Breadth-First Search (3) combinations

Abstract: all combinations using BFS

The result:
[['a', 'c', 'b', 'e', 'd', 'f'], ['a', 'c', 'b', 'e', 'd', 'f'], ['a', 'c', 'b', 'e', 'd', 'f'], ['a', 'c', 'b', 'e', 'd', 'f'], ['a', 'c', 'b', 'e', 'd', 'f'], ['a', 'c', 'b', 'e', 'd', 'f'], ['a', 'c', 'b', 'e', 'd', 'f'], ['a', 'c', 'b', 'e', 'd', 'f'], ['a', 'c', 'b', 'e', 'd', 'f'], ['a', 'c', 'b', 'e', 'd', 'f'], ['a', 'c', 'b', 'e', 'd', 'f'], ['c', 'b', 'e', 'd', 'f', 'f'], ['c', 'b', 'e', 'd', 'f', 'f'], ['c', 'b', 'e', 'd', 'f', 'f'], ['c', 'b', 'e', 'd', 'f', 'f'], ['c', 'b', 'e', 'd', 'f', 'f'], ['c', 'b', 'e', 'd', 'f', 'f'], ['b', 'e', 'd', 'f', 'f', 'd'], ['b', 'e', 'd', 'f', 'f', 'd'], ['b', 'e', 'd', 'f', 'f', 'd']]

The script:
# -*- coding: utf-8 -*-
"""
Created on Tue Jul 21 10:21:31 2015

@author: yuan
"""

import numpy as np
# search all possible combinations with some given characters

#record a queue using circling list
class queue:
   
    def __init__(self,arr, q_len=1):
        self.size=len(arr)
        if q_len==1 or q_len<self.size:       
            self.q=[None]*self.size
            self.q_len=self.size
        else:
            self.q=[None]*q_len
            self.q_len=q_len
        self.q[0]=0
        self.q[1:self.size]=arr
        self.head=1       #skip the index 0
        self.tail=len(arr)+1 #the index of next element of arr
        #print 'Initiate queue:', self.q
       
    def q_size(self):
        #print 'Size of the queue:', self.size
        return self.size
       
    def isFull(self):
        return self.tail==(self.q_len+1)
       
    def export_arr(self):
        if self.tail>self.head:
            arr=self.q[self.head:self.tail]
        elif self.tail==self.head:
            arr=[]
        else:
            arr=self.q[self.head:(self.q_len+1)] + self.q[1:self.tail]
        return arr
   
    def enqueue(self, value):
        if self.size<self.q_len:
            #increase size
            self.size +=1
            #increase tail
            if self.tail==(self.q_len+1):
                self.tail=1
            #add value
            self.q[self.tail]=value
            self.tail += 1
        else:
            print "queue is full, fail to adding", value
        #print '##', self.q, self.head,self.tail
        #return self.export_arr()
       
    def dequeue(self):
        #increase head
        value='NA'
        #print self.head, self.tail
        if self.size>0:
            value=self.q[self.head]
            if self.head==self.q_len:
                self.head=1
            else:
                self.head +=1
                #decrease size
            self.size -= 1
            #print 'remove', value, self.export_arr()
        return value

##################
class breadth_first_search(queue):
   
    def __init__(self, pool):
        self.pool=pool
        self.out=[]
        print self.pool

    def recrusive(self,q,book):
        #print q_book.export_arr(), q.export_arr()
        if q.isFull():
            self.out.append( q.export_arr() )
            return
           
        for c in book.keys():
            if book[c]==0:
                q.enqueue(c)
                book[c]=1
                self.recrusive(q,book)
                book[c]=0
        return
       

    def search_combination(self):
        book=dict(zip(self.pool, [0]*len(self.pool)))
        for first in book.keys():
            q=queue([first], len(self.pool))
            book[first]=1
            #           
            self.recrusive(q,book)       
        return self.out
           

#main
if __name__ == "__main__":
    chars='abcdef'   
   
    #coordinate of the end point
    s=breadth_first_search(chars)
    out=s.search_combination()
    print out
    print 'ok'