[Python] 파이썬 순열/중복순열/조합/중복조합 구현 코드 (Backtracking 활용)

1) 순열

def permutations(arr, k):
    cases = []
    visited = [False]*(len(arr))

    def dfs(elements):
        
        if len(elements) == k:
            cases.append(elements)
            return
        
        for i in range(len(arr)):
            if not visited[i]:
                visited[i] = True
                dfs(elements + [arr[i]])
                visited[i] = False
    
    dfs([])

    return cases

print(permutations([1,2,3],2)) # [[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]]

2) 중복순열

def permutation_with_repet(arr, k):
    
    cases = []

    def dfs(elements):
        
        if len(elements) == k:
            cases.append(elements)
            return
        
        for i in range(len(arr)):
            dfs(elements + [arr[i]])
    
    dfs([])

    return cases

print(permutation_with_repet([1,2,3],2)) # [[1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3], [3, 1], [3, 2], [3, 3]]

3) 조합

def combinations(arr, k):

    cases = []

    def dfs(elements,index):

        if len(elements) == k:
            cases.append(elements)
            return

        for i in range(index+1,len(arr)):
            dfs(elements + [arr[i]],i)

    dfs([],-1)

    return cases   

print(combinations([1, 2, 3], 2)) # [[1, 2], [1, 3], [2, 3]]

4) 중복조합

def combinations_with_repet(arr, k):

    cases = []
    
    def dfs(elements,index):
        
        if len(elements) == k:
            cases.append(elements)
            return
        
        for i in range(index,len(arr)):
            dfs(elements + [arr[i]],i)

    dfs([],0)

    return cases

print(combinations_with_repet([1,2,3],2)) # [[1, 1], [1, 2], [1, 3], [2, 2], [2, 3], [3, 3]]