8.7 중복없는 순열

문제

문자열이 주어졌을 때 모든 경우의 순열을 계산하는 메서드를 작성하라. 

단, 문자는 중복되어 나타날 수 없다. 

 

해결법

1. 첫 n-1개 문자의 순열을 이용해서 만들기

P(a1) = a1

P(a1a2) = a1a2, a2a1

P(a1a2a3) = a1a2a3, a1a3a2, a2a1a3, a2a3a1, a3a1a2, a3a2a1

다음 원소를 이전에 만든 순열들에 각 위치에 추가해주면 된다. 

def getPerms(str):
    if len(str) == 0 :
        return [""]
    permutations = []
    first = str[0]
    words = getPerms(str[1:])
    for word in words :
        for i in range(len(word)):
            permutations.append(word[:i] + first + word[i:])
    return permutations

2. 모든 n-1개의 문자의 부분 문자열의 순열을 이용해서 만들기

P(a1) = a1

P(a1a2) = a1a2, a2a1

P(a2a3) = a2a3, a3a2

P(a1a3) = a1a3, a3a1

P(a1a2a3) = (a1 + P(a2a3) )  + (a3 +  P(a1a2) )  + (a2 +   P(a1a3) ) 

이런식으로 n-1문자의 부분 문자열에 하나의 문자를 맨 앞에 추가함으로써 순열을 만들 수 있다.

def getPerms(str):
    len_str = len(str)
    if len_str == 0:
        return [""]
    permutations =[]
    for i in range(len_str):
        patials = getPerms(str[0:i]+ str[i+1:])
        for p in partials:
            permutations.append(str[i]+p)
    return permutations

 

3.순열을 스텍에 남기지 않고 prefix를 스텍 아래로 보내기 

초기사례에 도달하면 prefix는 순열이 만들어졌을 것이다.

def solution(str):
    result = []
    getPerms("", str, result)

def getPerms(prefix, remainder, result):
    len_r = len(remainder)
    if len_r == 0 :
        result.append(prefix)
    for i in range(len_r) :
        getPerms(prefix+remainder[i], remainder[:i] + remainder[i+1:], result)

이 경우는 Time Complextity를 살펴볼 필요가 있다.

- 완성된 prefix가 있는 getPerm은 몇번 호출될까? => 각 자리에 들어갈 문자를 골라야 한다. 그 말은 즉 문자열이 n개일때 n!의 경우의 수가 있다는 것이다.

- 미완성된 prefix의 상태의 getPerm은 몇번 호출될까? => 거대한 호출트리가 있다고 했을때 말단 노드는 n! 개 일 것이며, 루트부터 말단 노드까지가 n단계를 거칠 것이므로 n*n! 보다는 적은 수일 것이다.

- 각 함수 호출을 처리하는데에는 얼마나 걸리는가? 각 문자열을 연결하는 연산을 수행하므로 O(N)의 시간이 소요될 것이다. 

따라서 총 수행시간은 n*n!번 호출되고 한번 호출 될때마다 O(N)의 시간이 걸리므로 n*n!의 상한을 넘지 않을 것이다.