순열과 조합

itertools를 사용하지 않고 순열과 조합을 작성해 보았습니다.

다만 여기선 input을 튜플로 받아 중복을 해소하였습니다.

 

함수안에서 중복을 해소하는 방법도 있겠지만 최대한 간단하게 해결해보려고 했습니다.

 

def permutation(arr, r):

    used = [0]*len(arr)
    per2return=[]

    def generate(item, used):

        if len(item) == r:
            per2return.append(item.copy())
            return

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

    generate([], used)
    return per2return

def combination(arr, r):

    comb_return=[]

    def generate(chosen):
        if len(chosen) == r:
            comb_return.append(chosen.copy())
            return

        start = arr.index(chosen[-1]) + 1 if chosen else 0

        for i in range(start, len(arr)):
            chosen.append(arr[i])
            generate(chosen)
            chosen.pop()

    generate([])
    return comb_return

T=int(input())

array=tuple(map(int,input().split()))

print("permutaion: ",permutation(array,T))

print("combination: ",combination(array,T))