[Python] 순열, 중복순열, 조합 구현하기 (no itertools)

파이썬에는 자체적으로 내장된 itertools 패키지의 combinations 모듈과 permutations 모듈을 이용해 간단히 순열과 조합을 구할 수 있다. 그러나 우리는 이러한 모듈을 이용하지 않고 직접 구현을 해보자.

 

#순열

입력 예시

3 2
1 2 3

출력 예시

[[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]]

Solution

 

n, r = map(int, input().split())
graph = list(map(int, input().split()))

def perm(arr, r):
    result = []

    if r == 1:
        for i in arr:
            result.append([i])
    elif r > 1:
        for i in range(len(arr)):
            ans = [i for i in arr]
            ans.remove(arr[i])
            for j in perm(ans, r-1):
                result.append([arr[i]] + j)

    print(perm(graph, r))
    return result

 

리스트의 인덱스를 하나씩 순회하면서 그 인덱스를 제외한 나머지 원소들로만 이루어진 새로운 리스트를 ans 로 만들었다. 이 ans 리스트에서 r-1 개의 원소를 선택하는 순열의 값을 구하도록 재귀함수를 호출해주었으며 최종적으로 return 된 리스트의 원소가 j의 자리에 들어간다. 따라서 다음의 코드에 의해 현재 인덱스에 해당하는 원소와 짝을 이루어  j의 값이 하나씩 추가 될 것이다. 

 

result.append([arr[i]] + j)

 

 

#조합

입력 예시

3 2
1 2 3

출력 예시

[[1, 2], [1, 3], [2, 3]]

Solution

n, r = map(int, input().split())
graph = list(map(int, input().split()))

def comb(arr, r):
    result = []

    if r == 1:
        for i in arr:
            result.append([i])

    elif r > 1:
        for i in range(len(arr) - r + 1):
            for j in comb(arr[i + 1:], r - 1):
                result.append([arr[i]] + j)

    return result

print(comb(graph, r))

 

순열과 비슷한 논리다. 입력 예시로 코드를 해석해보면 이해하기 쉽다.

 

#중복 순열

입력 예시

3 2
1 2 3

출력 예시

[(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)]

 

Solution

 

from itertools import combinations


def permute(n, m):
    ans = []
    permutes = [0] * m

    def dfs(r):
        if r == m:
            ans.append(tuple(permutes))
        else:
            for num in n:
                permutes[r] = num
                dfs(r + 1)
    dfs(0)
    return ans


def combinate(n, m):
    ans = []
    tmp = [0] * m

    def dfs(s, r):
        """
        :param r: nCr에서 r을 나타냄.
        :return:  조합을 리스트에 담아 반환
        """
        if s == m:
            ans.append(tuple(tmp))
        else:
            for i in range(r, len(n)):
                tmp[s] = n[i]
                dfs(s + 1, i + 1)

    dfs(0, 0)
    return ans


if __name__ == '__main__':
    pass