순열, 중복순열, 조합, 중복조합 구현하기

Konseo·2023년 8월 3일
0

알고리즘

목록 보기
5/21

순열(permutations)

  1. 서로 다른 n개의 원소를 갖고 있는 배열에서 중복을 허용하지 않고(순서 상관 o) r개를 뽑음

  2. 재귀 - 백트래킹

    array = [1, 2, 3, 4, 5]
    k = 2
    used = [False for i in range(len(array))]
    
    def permutations(arr):
        if len(arr) == k:
            print(arr, end="")
            return arr
        for i in range(len(array)):
            if used[i] == False:
                used[i] = True
                permutations(arr + [array[i]])
                used[i] = False
    
    permutations([])

    백트래킹 과정을 그림으로 표현하면 아래와 같다.

    해당 과정을 array 개수만큼 반복할 것이다. (위 그림은 1로 시작하는 경우만 나타냄)

  1. itertools

    from itertools import permutations
    
    for i in permutations([1, 2, 3, 4], 2):
    		print(i, end="")
    
    # 결과 
    # (1,2), (1,3), (1,4), (2,1), (2,3), (2,4), (3,1), (3,2), (3,4), (4,1), (4,2), (4,3), (4,4)

중복 순열(product)

  1. 서로 다른 n개의 원소를 갖고 있는 배열에서 중복을 허용하고(순서 상관 o) r개를 뽑음

  2. 재귀 - 백트래킹

    array = [1, 2, 3]
    k = 2
    used = [False for i in range(len(array))]
    
    def product(arr):
        if len(arr) == k:
            print(arr, end="")
            return arr
        for i in range(len(array)):
            product(arr + [array[i]])
    
    product([])
  3. itertools

    from itertools import product
    
    for i in product([1, 2, 3, 4], 2):
    	print(i, end="")

조합(combinations)

  1. 서로 다른 n개의 원소를 갖고 있는 배열에서 중복을 허용하지 않고(순서 상관 x) r개를 뽑음

  2. 재귀 - 백트래킹

    array = [1, 2, 3]
    k = 2
    used = [False for i in range(len(array))]
    
    def combination(arr, i):
        if len(arr) == k:
            print(arr, end="")
            return arr
        for i in range(i, len(array)):
            combination(arr + [array[i]], i + 1)
    
    combination([], 0)
    
  3. itertools

    from itertools import combinations
    
    for i in combinations([1, 2, 3, 4], 2):
    	print(i, end="")

중복 조합(combinations_with_replacement)

  1. 서로 다른 n개의 원소를 갖고 있는 배열에서 중복을 허용하고(순서 상관 x) r개를 뽑음

  2. 재귀 - 백트래킹

    array = [1, 2, 3]
    k = 2
    used = [False for i in range(len(array))]
    
    def combination_with_replacement(arr, i):
        if len(arr) == k:
            print(arr, end="")
            return arr
        for i in range(i, len(array)):
            combination_with_replacement(arr + [array[i]], i)
    
    combination_with_replacement([], 0)
    print()
  3. itertools

    from itertools import combinations_with_replacement
    
    for i in combinations_with_replacement([1, 2, 3, 4], 2):
    	print(i, end="")
profile
둔한 붓이 총명함을 이긴다

0개의 댓글