[Jungle][TIL] 240326 순열/조합 재귀함수로 구현 해보기

파이썬에서 순열/조합 사용하기

itertools

from itertools import combinations
from itertools import permutations 

combinations(iterable, r): iterable에서 원소 개수가 r개인거 뽑기

# for i in range(1, N+1):
#     com = list(combinations(num_lst, i ))
#     for c in com:
#         if sum(c) == S:
#             cnt +=1
#

조합

def combination(arr, n):
    result = []
    if n > len(arr):
        return result

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

    elif n > 1:
        #조합 생성의 범위 len(arr) - n + 1
        for i in range(len(arr) -n +1):
            for j in combination(arr[i+1:], n-1):
                result.append([arr[i]] + j)

    return result

arr = [1,2,3]
for i in range(len(arr)):
    print(combination(arr, i))

nums = [1,2,3,4,5]

answer_list = []

#ans: 현재까지 선택된 요소들의 리스트
def combi(n, ans):
    if n == len(nums):
        temp  = [i for i in ans]
        answer_list.append(temp)
        return
    ans.append(nums[n])
    combi(n+1, ans)
    #더 이상 선택할 요소가 없다면 이전 단계 - pop()로 돌아가서
    #마지막으로 선택한 요소 제거하고 그 다음 요소 선택하게 된다. 
    ans.pop()
    combi(n+1, ans)

combi(0, [])
print(answer_list)

순열

test = [1,2,3]
N = 2 #뽑을 순열의 개수
visit = [0] * len(test)
arr = [0] * N #현재 순열을 담을 배열
arr_list = []  #모든 순열을 담을 배열 
def permutation(level):
    if level >= N:
        arr_list.append(arr[:])
        print(arr_list)
        return
    else:
        for i in range(len(test)):
            if visit[i]:
                continue
            visit[i] = 1
            arr[level] = test[i]
            permutation(level + 1)
            visit[i] = 0

permutation(0)
print(arr_list)