알고리즘 문제를 풀다보면 순열과 조합을 이용해야 하는 경우가 자주 나온다. 여러가지 구현 방식을
포스팅해보려 한다.

내장 함수

순열

list에서 n개를 순서대로 뽑는 모든 경우를 리스트로 반환

from itertools import permutations

def(listA, n):
	permutations(listA, n) 

조합

list에서 n개를 뽑는 모든 경우를 리스트로 반환

from itertools import combinations

def(listA, n):
	combinations(listA, n) 

직접 구현

def generate_combination(arr, n):
    if n==0:
        return [[]]
    result = []

    for i in range(0,len(arr)):
        elem = arr[i]
        rest = arr[i+1:]
        for C in generate_combination(rest, n-1):
            result.append([elem]+C)
    return result



print(generate_combination([1,2,3,4,5], 3))
    

def permutation(arr, r):
    used = [0 for _ in range(len(arr))]

    def generate(chosen, used):
        #chosen : 선택된 숫자의 배열
        #used : 선택됐는지 여부
        if len(chosen) == r:
            print(chosen)
            return

        for i in range(len(arr)):
            if not used[i]:
                chosen.append(arr[i])
                used[i] = 1
                generate(chosen, used)
                used[i] = 0
                chosen.pop()
    
    generate([], used)

permutation([1,2,3,4,5], 3)

def makeCombinations(str1, str2):
    if str1 != "":
        if isPrime(int(str1)):
            primeSet.add(int(str1))

    for i in range(len(str2)):
        makeCombinations(str1 + str2[i], str2[:i] + str2[i + 1:])