조합(Combination)과 순열(Permutation)

조합 (Combination)

 조합은 주어진 집합에서 몇 개의 원소를 선택할 때, 선택 순서를 고려하지 않고 몇 가지 방법으로 선택할 수 있는지를 나타냅니다. 다시 말해, 조합은 "n개 중에서 k개를 선택하는 방법의 수"를 의미합니다. 예를 들어, 'A', 'B', 'C' 세 개의 원소에서 두 개를 선택하는 조합을 생각해 보면, 가능한 조합은 ('A', 'B'), ('A', 'C'), ('B', 'C')로 총 세 가지입니다. 여기서 중요한 점은 순서가 결과에 영향을 주지 않는다는 것입니다. 즉, ('A', 'B')와 ('B', 'A')는 같은 조합으로 간주됩니다.

package main

import (
    "fmt"
)

// combination 함수는 재귀적으로 조합을 생성하고 출력합니다.
func combination(index, start, n, m int, array []int) {
    if index == m {
        for i, val := range array {
            if i > 0 {
                fmt.Print(" ")
            }
            fmt.Print(val)
        }
        fmt.Println()
        return
    }

    for i := start; i <= n; i++ {
        array[index] = i
        combination(index+1, i+1, n, m, array)
    }
}

func main() {
    n := 4
    m := 2
    array := make([]int, m)  // m의 크기만큼의 배열을 만듭니다.

    combination(0, 1, n, m, array)
}

코드 설명

• 함수 선언: Go에서는 combination 함수를 정의하여 JavaScript와 유사하게 작동하도록 합니다. 이 함수는 시작 인덱스, 현재 조합의 시작 점, 전체 원소 수 n, 선택할 원소 수 m, 그리고 현재 조합 상태를 저장하는 array 슬라이스를 매개변수로 받습니다.
• 조합 출력: JavaScript의 console.log 대신 Go에서는 fmt.Println과 fmt.Print을 사용하여 조합을 출력합니다. Go에서 슬라이스의 원소를 출력할 때는 직접 루프를 돌면서 각 원소를 출력합니다.
• 재귀 호출: 각 숫자를 선택할 때마다 combination 함수를 재귀적으로 호출하고, 인덱스와 시작점을 적절히 조정합니다.

실행 방식

이 Go 프로그램은 n과 m을 설정한 후 main 함수에서 combination 함수를 호출하여 실행됩니다. 이때 array 슬라이스는 각 조합을 임시로 저장하는데 사용되며, 조합이 완성될 때마다 출력됩니다. 결과적으로, 이 코드는 주어진 n과 m에 대해 모든 조합을 출력합니다.

 

순열 (Permutation)

 순열은 주어진 집합에서 몇 개의 원소를 선택할 때, 선택 순서를 고려하여 몇 가지 방법으로 선택할 수 있는지를 나타냅니다. "n개 중에서 k개를 선택하되 순서를 고려한 선택 방법의 수"를 의미합니다. 예를 들어, 'A', 'B', 'C' 세 개의 원소에서 두 개를 선택하는 순열을 생각해 보면, 가능한 순열은 ('A', 'B'), ('B', 'A'), ('A', 'C'), ('C', 'A'), ('B', 'C'), ('C', 'B')로 총 여섯 가지입니다. 여기서는 순서가 결과에 영향을 주기 때문에 ('A', 'B')와 ('B', 'A')는 서로 다른 순열로 간주됩니다.

package main

import (
	"fmt"
)

// permutation 함수는 주어진 정수 n에 대해 0부터 n-1까지의 숫자 순열을 생성합니다.
func permutation(n int) {
	arrayList := make([]int, n)
	used := make([]bool, n)

	var dfs func(int)
	dfs = func(depth int) {
		if depth == n {
			for i := 0; i < n; i++ {
				fmt.Print(arrayList[i], " ")
			}
			fmt.Println()
			return
		}

		for i := 0; i < n; i++ {
			if !used[i] {
				used[i] = true
				arrayList[depth] = i
				dfs(depth + 1)
				used[i] = false
			}
		}
	}

	dfs(0)
}

func main() {
	permutation(5)
}

코드 설명

• 배열 초기화: 순열을 저장할 arrayList와 각 숫자의 사용 여부를 추적할 used 배열을 초기화합니다. used는 bool 타입의 슬라이스로, 해당 인덱스의 숫자가 사용 중인지 여부를 나타냅니다.
• DFS 함수: dfs라는 깊이 우선 탐색 함수를 정의하여 순열을 생성합니다. depth는 현재 순열의 깊이(또는 길이)를 나타냅니다.
  • depth가 n에 도달하면 모든 숫자가 선택되었으므로 순열을 출력하고 반환합니다.
  • 순회는 모든 숫자에 대해 실행되며, 사용되지 않은 숫자(i.e., used[i] == false)만 선택됩니다. 선택된 숫자는 used를 true로 설정하고, 순열의 현재 위치에 할당한 다음, 다음 깊이로 재귀 호출을 진행합니다. 재귀 호출 후에는 해당 숫자의 사용 상태를 false로 다시 설정하여 다른 순열 생성에 사용할 수 있도록 합니다.
• 메인 함수: main 함수에서 permutation 함수를 호출하여 순열을 생성하고 출력합니다.

이 코드는 n개의 숫자에 대한 모든 순열을 깊이 우선 탐색 방식으로 생성하고, 콘솔에 출력합니다. Go에서 DFS와 백트래킹을 활용한 순열 생성 방식은 매우 효율적이며, 다양한 알고리즘 문제에서 유용하게 사용될 수 있습니다.

 

비교

조합과 순열

 간단하게 말하면, 조합은 순서를 고려하지 않고 선택하는 방법의 수를 계산하는 반면, 순열은 순서를 고려하여 선택하는 방법의 수를 계산합니다. 따라서 같은 세 개의 원소를 가지고 두 개를 선택하는 경우, 조합은 결과의 순서를 신경 쓰지 않으므로 경우의 수가 더 적고, 순열은 각각의 순서마다 다른 결과로 취급하므로 경우의 수가 더 많습니다.

이 두 개념은 수학뿐만 아니라 컴퓨터 과학에서도 매우 중요하며, 데이터 분석, 암호학, 알고리즘 설계 등 다양한 분야에서 활용됩니다.