11. 순열과 조합 Swift로 구현.md

날짜: 2023-05-10 12:59

주제: 순열과 조합 Swift로 구현

---

메모:

Permutation

• nPr = n! / (n-r)!
• 서로 다른 n개 중에 r개를 선택하는 경우의 수 (순서 고려 o)
• 전체에서 중복없이 순서를 고려해 n개를 배열하는 경우의 수
• DFS을 활용한다.

Stack 사용

• array.count를 depth로 활용하면서 최초 1 depth를 구현하고 시작

func permutationStack<T: Comparable>(_ array:[T], _ n: Int) -> [[T]] { 
	var result = [[T]]()
	
	guard array.count >= n else { return result }
	
	// 최초 1깊이 구현 
	var stack: [([T], [Bool])] = array.enumerated().map { 
		var visited = Array(repeating: false, count: array.cont)
		visited[$0.offset] = true
		
		return ([$0.element], visited)
	}
	
	// stack이 빌 때까지 n까지의 반복
	while !stack.isEmpty { 
		let now = stack.removeLast()
		
		let elements = now.0
		var visited = now.1 
		
		// depth가 elements.count
		if elements.count == n { 
			result.append(elements)
			continue
		}
		
		// 기존 원소에 하나씩 추가하고 stack에 push 하기
		for i in 0...array.count - 1 {
			// 체크된것은 skip  
			if !visited[i] { 
				visited[i] = true
				stack.append((elements + [array[i]], visited))
				// 대입 후 다음 경우의 수를 위해 visited 초기화
				visited[i] = false
			}
		}
	}
	return result
}

• depth을 stack의 원소로 직접 대입하면서 0부터 시작

func permutationStack(_ array:[Int], _n: Int) -> [[Int]] { 
	var result = [[Int]]()
	
	guard array.count >= n else { return result }
	
	// depth, 경우의 수 원소 배열, visited 배열
	var stack: [(Int, [Int], [Bool])] = [(0, [], Array(repeating: false, count: array.count))]
	
	while !stack.isEmpty { 
		let (depth, current, used) = stack.removeLast()
		
		// 원하는 경우의 수 깊이를 찾았을 때 
		if depth == n {
			result.append(cuurent)
		} else { 
			for i in 0...array.count - 1 {
				if !used[i] { 
					var newUsed = used
					newUsed[i] = true
					stack.append((depth + 1), current + [array[i]], newUsed)
				}
			}
		}
	}
	return result
}

재귀함수 사용

func permutationRecursive<T: Comparable>(_ array: [T], _ n: Int) -> [[T]] { 
	var result = [[Int]]()
	
	guard array.count >= n else { return result }
	
	var visited = Array(repeating: false, count: array.count)
	
	// 함수 내부 재귀함수 구현
	func cycle(_ now: [T]) { 
		if now.count == n { 
			result.append(now)
			return
		}
		
		for i in 0..<array.count { 
			if visited[i] { 
				continue
			} else { 
			// 방문 true처리 후, cycle다 돈다음에 조건을 확인하고 다 끝났으면 다시 방문을 false로 초기화
				visited[i] = true
				cycle(now + [array[i]])
				visited[i] = false 
			}
		}
	}
	cycle([])
	
	return result
}

Combination

• nCr = n! / (n-r)!r!
• 서로 다른 n개 중에 r개를 선택하는 경우의 수 (순서 고려 x)
• 조합은 전체에서 중복없이 순서를 고려하지 않고 n개를 배열하는 경우의 수이다.
• 해당 특성에 맞게 DFS를 활용한다.

Stack 사용

func combinationStack<T: Comparable>(_ array: [T], _ n: Int) -> [[T]] { 
	var result = [[T]]() 
	
	guard array.count >= n else { return result }
	
	// 원소의 순서가 달라도 동의의 집합으로 견주하기 위한 stack
	var stack = array.enumerated().map { ([$0.element],$0.offset)}
	
	while !stack.isEmpty { 
		let now = stack.removeLast()
		
		let elements = now.0
		let index = now.1
		
		if elements.count == n { 
			result.append(elements.sorted)
			continue
		}
		// index 범위를 벗어나지 않게 하기 위한 선제조건
		guard index + 1 <= array.count - 1 else { return }
		
		// 중복을 피하기 위해 자기 다음 index 부터 append 한다. 
		for i in index+1...array.count - 1 { 
			stack.append((elements + [array[i]], i))
		}
	}
	return result 
}

재귀함수 사용

func combinationRecursive<T: Comparable>(_ array: [T], _ n: Int) -> [[T]] { 
	var result = [[T]]()
	
	guard array.count >= n else { return result }
	
	func cycle(_ index: Int, _ now: [T]) { 
		if now.count == n { 
			result.append(now.sorted)
			return 
		}
		// index가 마지막일 때는 계산 x
		// 다음 함수 재귀적으로 돌면서 원소 하나씩 넣기
		for i in index..<array.count { 
			cycle(i + 1, now + [array[i]])
		}
	}
}

위 코드에서 보여지는 Stack vs 재귀함수차이

• 위의 코드를 잘 보면 stack으로 구현 했을 때는 마지막 원소부터 조건이 완성되는 것을 확인할 수 있고 재귀함수를 활용하면 사전순서대로 조건이 완성되는 것을 확인할 수 있다.
• 그 이유는 stack이 기본적으로 FILO의 특성을 나타내고 있기 때문이다. 하지만 위 코드의 재귀함수는 맨 처음의 조건부터 완료하고 다음 숫자로 넘어가는 형식이라는 것을 확인할 수 있다.
• 또한 스택을 사용한 방법의 장점은 명시적인 반복문을 사용하므로, 함수 호출 스택의 제한에 걸리지 않는 경우가 많다. 이는 재귀 호출의 깊이에 제한이 없으며, 더 큰 규모의 문제에 적용할 수 있다는 것을 의미한다.
• 그러나 스택을 사용한 방법의 코드는 재귀 함수를 사용한 방법보다 약간 더 길고 복잡할 수 있다.
• 재귀 함수를 사용한 방법은 코드가 더 짧고 이해하기 쉽다. 하지만, 깊이가 매우 깊은 재귀 호출의 경우 스택 오버플로우의 위험이 있다. 이 경우, 스택을 사용하는 것이 오히려 더 적합할 수 있다.

출처(참고문헌)

• https://inuplace.tistory.com/1189

연결문서

• [[7. 경우의 수 공식 총정리]]
• [[1. Stack]]
• [[26. Depth-First Search]]

Tag

• #Algorithm/Math/permutation
• #Algorithm/Math/Combination