본문 바로가기
Algorithm/Tips

순열, 조합, 중복순열, 중복조합

by 컴돈AI 2024. 4. 10.

목차

    순열(Permutations)

    • 순열은 주어진 원소들로 만들 수 있는 모든 가능한 순서 있는 배열입니다. (순서가 중요한 경우)
    • 시간복잡도 : O(nPr)
    • 예시

    itertools 라이브러리 이용

    • 코드
      • from itertools import permutations
        
        print(list(permutations([1, 2, 3, 4, 5], 3)))

    직접구현

    • 코드
      • def permutations(arr, r):
            def generate(arr, prefix=[]):
                if len(prefix) == r:
                    result.append(prefix)
                    return
                for i in range(len(arr)):
                    generate(arr[:i] + arr[i + 1 :], prefix + [arr[i]])
        
            result = []
            generate(arr, [])
            return result
        
        
        print(permutations([1, 2, 3, 4, 5], 3))

    조합(Combinations)

    • 조합은 주어진 원소들로 만들 수 있는 모든 가능한 순서 없는 집합입니다. (순서가 중요하지 않은 경우)
    • 시간복잡도 : O(nCr)
    • 예시

    itertools 라이브러리 이용

    • 코드
      • from itertools import combinations
        
        print(list(combinations([1, 2, 3, 4, 5], 3)))

    직접구현

    • 코드
      • def combinations(arr, r):
            def generate(start, prefix=[]):
                if len(prefix) == r:
                    result.append(prefix)
                    return
                for i in range(start, len(arr)):
                    generate(i + 1, prefix + [arr[i]])
        
            result = []
            generate(0)
            return result
        
        
        print(combinations([1, 2, 3, 4, 5], 3))

    중복순열(Product)

    • 중복순열은 주어진 집합에서 원소를 중복해서 선택하여 만들 수 있는 모든 가능한 순서 있는 배열입니다.
    • 시간복잡도 : O(n^r)
    • 예시

    itertools 라이브러리 이용

    • 코드
      • from itertools import product
        
        print(list(product([1, 2, 3], repeat=5)))
      • [(1, 1, 1, 1, 1), (1, 1, 1, 1, 2), (1, 1, 1, 1, 3), (1, 1, 1, 2, 1), (1, 1, 1, 2, 2),
        (1, 1, 1, 2, 3), (1, 1, 1, 3, 1), (1, 1, 1, 3, 2), (1, 1, 1, 3, 3), (1, 1, 2, 1, 1),
        (1, 1, 2, 1, 2), (1, 1, 2, 1, 3), (1, 1, 2, 2, 1), (1, 1, 2, 2, 2), (1, 1, 2, 2, 3),
        (1, 1, 2, 3, 1), (1, 1, 2, 3, 2), (1, 1, 2, 3, 3), (1, 1, 3, 1, 1), (1, 1, 3, 1, 2),
        (1, 1, 3, 1, 3), (1, 1, 3, 2, 1), (1, 1, 3, 2, 2), (1, 1, 3, 2, 3), (1, 1, 3, 3, 1),
        (1, 1, 3, 3, 2), (1, 1, 3, 3, 3), (1, 2, 1, 1, 1), (1, 2, 1, 1, 2), (1, 2, 1, 1, 3),
        ...
        (3, 3, 1, 1, 1), (3, 3, 1, 1, 2), (3, 3, 1, 1, 3), (3, 3, 1, 2, 1), (3, 3, 1, 2, 2),
        (3, 3, 1, 2, 3), (3, 3, 1, 3, 1), (3, 3, 1, 3, 2), (3, 3, 1, 3, 3), (3, 3, 2, 1, 1),
        (3, 3, 2, 1, 2), (3, 3, 2, 1, 3), (3, 3, 2, 2, 1), (3, 3, 2, 2, 2), (3, 3, 2, 2, 3),
        (3, 3, 2, 3, 1), (3, 3, 2, 3, 2), (3, 3, 2, 3, 3), (3, 3, 3, 1, 1), (3, 3, 3, 1, 2),
        (3, 3, 3, 1, 3), (3, 3, 3, 2, 1), (3, 3, 3, 2, 2), (3, 3, 3, 2, 3), (3, 3, 3, 3, 1),
        (3, 3, 3, 3, 2), (3, 3, 3, 3, 3)]

    직접구현

    • 코드
      • def product(arr, r):
            def generate(prefix=[]):
                if len(prefix) == r:
                    result.append(prefix)
                    return
                for i in range(len(arr)):
                    generate(prefix + [arr[i]])
        
            result = []
            generate()
            return result
        
        
        print(product([1, 2, 3], 5))
      • [[1, 1, 1, 1, 1], [1, 1, 1, 1, 2], [1, 1, 1, 1, 3], [1, 1, 1, 2, 1], [1, 1, 1, 2, 2],
        [1, 1, 1, 2, 3], [1, 1, 1, 3, 1], [1, 1, 1, 3, 2], [1, 1, 1, 3, 3], [1, 1, 2, 1, 1],
        [1, 1, 2, 1, 2], [1, 1, 2, 1, 3], [1, 1, 2, 2, 1], [1, 1, 2, 2, 2], [1, 1, 2, 2, 3],
        [1, 1, 2, 3, 1], [1, 1, 2, 3, 2], [1, 1, 2, 3, 3], [1, 1, 3, 1, 1], [1, 1, 3, 1, 2],
        [1, 1, 3, 1, 3], [1, 1, 3, 2, 1], [1, 1, 3, 2, 2], [1, 1, 3, 2, 3], [1, 1, 3, 3, 1],
        [1, 1, 3, 3, 2], [1, 1, 3, 3, 3], [1, 2, 1, 1, 1], [1, 2, 1, 1, 2], [1, 2, 1, 1, 3],
        ......
        [3, 2, 3, 1, 3], [3, 2, 3, 2, 1], [3, 2, 3, 2, 2], [3, 2, 3, 2, 3], [3, 2, 3, 3, 1],
        [3, 2, 3, 3, 2], [3, 2, 3, 3, 3], [3, 3, 1, 1, 1], [3, 3, 1, 1, 2], [3, 3, 1, 1, 3],
        [3, 3, 1, 2, 1], [3, 3, 1, 2, 2], [3, 3, 1, 2, 3], [3, 3, 1, 3, 1], [3, 3, 1, 3, 2],
        [3, 3, 1, 3, 3], [3, 3, 2, 1, 1], [3, 3, 2, 1, 2], [3, 3, 2, 1, 3], [3, 3, 2, 2, 1],
        [3, 3, 2, 2, 2], [3, 3, 2, 2, 3], [3, 3, 2, 3, 1], [3, 3, 2, 3, 2], [3, 3, 2, 3, 3],
        [3, 3, 3, 1, 1], [3, 3, 3, 1, 2], [3, 3, 3, 1, 3], [3, 3, 3, 2, 1], [3, 3, 3, 2, 2],
        [3, 3, 3, 2, 3], [3, 3, 3, 3, 1], [3, 3, 3, 3, 2], [3, 3, 3, 3, 3]]

    중복조합(Combinations with Replacement)

    • 중복조합은 주어진 집합에서 원소를 중복해서 선택하여 만들 수 있는 모든 가능한 순서 없는 집합입니다.
    • 시간복잡도 : O(r+(n-1)Cr)
    • 예시

    itertools 라이브러리 이용

    • 코드
      • from itertools import combinations_with_replacement
        
        print(list(combinations_with_replacement([1, 2, 3], 5)))

    직접구현

    • 코드
      • def combintations_with_replacement(arr, r):
            def generate(start, prefix=[]):
                if len(prefix) == r:
                    result.append(prefix)
                    return
                for i in range(start, len(arr)):
                    generate(i, prefix + [arr[i]])
        
            result = []
            generate(0)
            return result
        
        
        print(combintations_with_replacement([1, 2, 3], 5))

     

    'Algorithm > Tips' 카테고리의 다른 글

    빅오(big-O) (시간복잡도)  (1) 2024.04.07
    그래프(Graph) vs 트리(Tree)  (0) 2023.10.16