[Python] 순열, 조합 직접 구현

순열, 조합 직접 구현

• 직접 구현 시에는 함수 밖으로 따로 불러오지말고 (불러오면 combinations 쓰는거랑 동일)
• 기저조건 안에서 다른 함수 파라미터 안에 result를 넣거나 
• 기저조건 아래에서 전부 실행하기

순열

def permutation(arr, r):
    result = []
    
    def backtrack(temp, used):
        if len(temp) == r:
            result.append(temp[:])
            return
        
        for i in range(len(arr)):
            if not used[i]:
                used[i] = True
                temp.append(arr[i])
                backtrack(temp, used)
                temp.pop()
                used[i] = False

    backtrack([], [False] * len(arr))
    return result

# 예제 실행
data = [1, 2, 3]
print(permutation(data, 2))  
# 출력: [[1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]]

N = 5
R = 3
results = [0] * R
isSelected = [False] * N  # 중복 방지

def perm(cnt):
    if cnt == R:
        print(results)
        return

    for i in range(N):
        if not isSelected[i]:  # 중복 방지 체크
            isSelected[i] = True
            results[cnt] = i
            perm(cnt + 1)
            isSelected[i] = False

perm(0)

 

---

중복순열

def product(arr, r):
    result = []
    
    def backtrack(temp):
        if len(temp) == r:
            result.append(temp[:])
            return
        
        for i in range(len(arr)):
            temp.append(arr[i])
            backtrack(temp)
            temp.pop()

    backtrack([])
    return result

# 예제 실행
data = [1, 2, 3]
print(product(data, 2))  
# 출력: [[1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 3], [3, 1], [3, 2], [3, 3]]

N = 5
R = 3
results = [0] * R

def perm_dup(cnt):
    if cnt == R:
        print(results)
        return

    for i in range(N):
        results[cnt] = i
        perm_dup(cnt + 1)

perm_dup(0)

---

조합

def combination(arr, r):
    result = []
    
    def backtrack(temp, start):
        if len(temp) == r:
            result.append(temp[:])
            return
        
        for i in range(start, len(arr)):
            temp.append(arr[i])
            backtrack(temp, i + 1)
            temp.pop()

    backtrack([], 0)
    return result

# 예제 실행
data = [1, 2, 3]
print(combination(data, 2))  
# 출력: [[1, 2], [1, 3], [2, 3]]

N = 5
R = 3
results = [0] * R

def comb(cnt, start):
    if cnt == R:
        print(results)
        return

    for i in range(start, N):
        results[cnt] = i
        comb(cnt + 1, i + 1)

comb(0, 0)

---

중복조합

def combination_with_replacement(arr, r):
    result = []
    
    def backtrack(temp, start):
        if len(temp) == r:
            result.append(temp[:])
            return
        
        for i in range(start, len(arr)):
            temp.append(arr[i])
            backtrack(temp, i)  # 같은 요소를 여러 번 선택 가능
            temp.pop()

    backtrack([], 0)
    return result

# 예제 실행
data = [1, 2, 3]
print(combination_with_replacement(data, 2))  
# 출력: [[1, 1], [

N = 5
R = 3
results = [0] * R

def comb_dup(cnt, start):
    if cnt == R:
        print(results)
        return

    for i in range(start, N):
        results[cnt] = i
        comb_dup(cnt + 1, i)  # 중복 허용 (i + 1 → i)

comb_dup(0, 0)