[443] 순열, 조합, 중복순열, 중복조합 구현하기(파이썬 코드) - itertools 없이

1. 순열

arr = [1, 2, 3]
used = [False] * len(arr)
def perm(arr, r):
    for i in range(len(arr)):
        if not used[i]:
            used[i] = True
            if r == 1:
                yield [arr[i]]
            else:
                for nxt in perm(arr, r-1):
                    yield [arr[i]] + nxt
            used[i] = False
            
print(*perm(arr, 3), sep="\n")
# [1, 2, 3]
# [1, 3, 2]
# [2, 1, 3]
# [2, 3, 1]
# [3, 1, 2]
# [3, 2, 1]

2. 조합

arr = [1, 2, 3]
def combi(arr, r):
    for i in range(len(arr)):
        if r == 1:
            yield [arr[i]]
        else:
            for nxt in combi(arr[i+1:], r-1):
                yield [arr[i]] + nxt
                
print(*combi(arr, 3), sep="\n")
# [1, 2, 3]

3. 중복순열

arr = [1, 2, 3]
def perm_with_repetition(arr, r):
    for i in range(len(arr)):
        if r == 1:
            yield [arr[i]]
        else:
            for nxt in perm_with_repetition(arr, r-1):
                yield [arr[i]] + nxt
                
print(*perm_with_repetition(arr, 3), sep="\n")
# [1, 1, 1]
# [1, 1, 2]
# [1, 1, 3]
# [1, 2, 1]
# [1, 2, 2]
# [1, 2, 3]
# [1, 3, 1]
# [1, 3, 2]
# [1, 3, 3]
# [2, 1, 1]
# [2, 1, 2]
# [2, 1, 3]
# [2, 2, 1]
# [2, 2, 2]
# [2, 2, 3]
# [2, 3, 1]
# [2, 3, 2]
# [2, 3, 3]
# [3, 1, 1]
# [3, 1, 2]
# [3, 1, 3]
# [3, 2, 1]
# [3, 2, 2]
# [3, 2, 3]
# [3, 3, 1]
# [3, 3, 2]
# [3, 3, 3]

4. 중복조합

arr = [1, 2, 3]
def combi_with_repetition(arr, r):
    for i in range(len(arr)):
        if r == 1:
            yield [arr[i]]
        else:
            for nxt in combi_with_repetition(arr[i:], r-1):
                yield [arr[i]] + nxt
                
print(*combi_with_repetition(arr, 3), sep="\n")
# [1, 1, 1]
# [1, 1, 2]
# [1, 1, 3]
# [1, 2, 2]
# [1, 2, 3]
# [1, 3, 3]
# [2, 2, 2]
# [2, 2, 3]
# [2, 3, 3]
# [3, 3, 3]