P26 Scala로 만드는 조합(Combination)

P26 (**) Generate the combinations of K distinct objects chosen from the N elements of a list.

In how many ways can a committee of 3 be chosen from a group of 12 people? We all know that there are C(12,3) = 220 possibilities (C(N,K) denotes the well-known binomial coefficient). For pure mathematicians, this result may be great. But we want to really generate all the possibilities.

Example:

scala> combinations(3, List('a, 'b, 'c, 'd, 'e, 'f))
res0: List[List[Symbol]] = List(List('a, 'b, 'c), List('a, 'b, 'd), List('a, 'b, 'e), ...

주어진 수와 리스트를 이용해 중복이 없는 '조합'들을 만드는 문제.

def solution(n: Int, lst:List[Int]): Iterator[List[Int]] = lst.combinations(n)

이와 같이 API를 활용하여 풀어낼 수 있는 방법도 있다.

하지만 재귀를 이용해 함수형스럽게(?) 풀어내 보자.

1. 먼저 엘리먼트 A, B, C, D를 가진 리스트에서 엘리먼트의 수가 2개인 조합을 생각해 보자.

val lst = List('A', 'B', 'C', 'D')

이 때, 우리는 아주 쉽게 엘리먼트 2개로 이루어진 조합을 생각해 낼 수 있다.

엘리먼트가 'A'로 시작하는 ('A', 'B'), ('A', 'C'), ('A', 'D'), 

엘리먼트가 'B'로 시작하는 ('B', 'C'), ('B', 'D'), 

엘리먼트가 'C'로 시작하는 ('C', 'D') 

이렇게 총 6가지다. 이 때, 각 요소를 보면

엘리먼트가 'A'로 시작하는 조합은 엘리먼트 A를 제외한, 

즉 lst.tail의 각 요소에 'A'를 붙인 결과임을 알 수 있다. 이를 map을 통해 적어보면

val combinationA = lst.tail.map(List('A', _))

라고 표현할 수 있다.

이 결과를 이용해 엘리먼트의 수가 2개인 전체 결과를 구해보자면,

def combination2(lst: List[Char]): List[List[Char]] = lst match {
  case h::t =>
    t.map(List(h, _)) ::: combination2(t)
  case Nil => Nil
}

이렇게 구할 수 있다. 파라미터로 받는 Char List의 tail이 재귀호출되면서 리스트의 가장 첫 번째 엘리먼트로 구성된 2개의 조합을 구해낸다.

2. 이번엔 엘리먼트 A, B, C, D를 가진 리스트에서 엘리먼트 3개로 이루어진 조합들을 생각해 보자.

엘리먼트가 'A'로 시작하는 ('A', 'B', 'C'), ('A', 'B', 'D'), ('A', 'C', 'D'), 

엘리먼트가 'B'로 시작하는 ('B', 'C', 'D')

이렇게 네 가지임을 알 수 있다.

이렇게 얻은 이 결과들을 조금 더 살펴 보면,

엘리먼트가 'A'로 시작하는 경우는 나머지 엘리먼트가 ('B', 'C'), ('B', 'D'), ('C', D') 이다.

이 결과는 리스트에서 'A'를 제외한, 리스트의 테일로 만든 엘리먼트 2개 조합이다.

마찬가지로 엘리먼트가 'B'로 시작하는 경우는 나머지 엘리먼트가 ('C', 'D'),

이 결과는 'A', 'B'를 제외한 리스트에서 엘리먼트 2개로 만들어진 조합이다.

앞서 작성한 combination2 함수를 이용해 정리하자면, 

def combination3(lst: List[Char]): List[List[Char]] = lst match {
  case h :: t =>
    combination2(t).map(h :: _) ::: combination3(t)
  case Nil => Nil
}

이렇게 표현할 수 있다. 

마찬가지로 조합의 갯수가 늘어나더라도 계속 같은 방식으로 구할 수 있을 것임을 충분히 추측할 수 있다. 반대로, 1개의 조합인 경우는 각 요소를 리스트로 만들면 된다.

이런 사실들을 모두 고려한다면 조합으로 만들어야 하는 엘리먼트의 갯수를 파라미터로 받고, 그 값을 이용해 조합을 구할 수 있다.

결과적으로 조합들을 만드는 함수는

def combinations[A](n: Int, lst: List[A]): List[List[A]] = {
  if (n == 1) lst.map(List(_))
  else lst match {
    case h :: t =>
      combinations(n - 1, t).map(h :: _) ::: combinations(n, t)
    case _ => Nil 
  }
}

이렇게 만들 수 있다.