8.8 중복있는 순열

문제

 문자열이 주어졌을 때 모든 경우의 순열을 계산하는 메서드를 작성하라. 문자는 중복되어 나타날 수 있지만, 나열된 순열은 서로 중복 되면 안된다. 

 

접근법

 

가장 간단한 방법은 현재 순열이 이미 만들어 졌는지를 확인하고 만들어진 적이 없다면 리스트에 더해주는 것이다. 해시테이블을 사용하면 되지만, 최악의 경우에 n!의 시간이 걸린다. 

 

따라서 모든 순열을 만들어서 중복된 경우를 제거하는 것 보다는 중복되지 않은 순열만을 나열하는 것이 더 효율적일 것이다.

문자열 aabbcccc가 있다고 할때 a->2 b->2 c->4 개가 존재한다.

그럴때 해시테이블을 이용하여 문자열 순열을 나열하는 방법을 생각해보자. 

P (a ->2, b->2, c->4) ={a + P (a ->2, b->2, c->4) } + {b + P (a ->2, b->1, c->4) } + {c + P (a ->2, b->2, c->3) }

이런식으로 만들 수 있을 것이다.

def getPerm(prefix,reminder, table, result) :
    if reminder== 0 :
        result.append(prefix)
    for c in table:
        if table[c] >0 :
            table[c] = table[c] -1
            getPerm(c + prefix, reminder-1, table, result)
            table[c] = table[c] +1

def getTable(s,table):
    for c in s :
        table[c] = table.get[c] +1

def Soloution(s):
    FreqTable = {}
    FreqTable = getTable(s, FreqTable)
    result = []
    getPerm("", len(s),FreqTable,result)
    return result