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

목차

순열(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))

  •