P27 Scala로 만드는 그룹(subsets)

P27 (**) Group the elements of a set into disjoint subsets.

a) In how many ways can a group of 9 people work in 3 disjoint subgroups of 2, 3 and 4 persons? Write a function that generates all the possibilities.

Example:

scala> group3(List("Aldo", "Beat", "Carla", "David", "Evi", "Flip", "Gary", "Hugo", "Ida"))
res0: List[List[List[String]]] = List(List(List(Aldo, Beat), List(Carla, David, Evi), List(Flip, Gary, Hugo, Ida)), ...

b) Generalize the above predicate in a way that we can specify a list of group sizes and the predicate will return a list of groups.

Example:

scala> group(List(2, 2, 5), List("Aldo", "Beat", "Carla", "David", "Evi", "Flip", "Gary", "Hugo", "Ida"))
res0: List[List[List[String]]] = List(List(List(Aldo, Beat), List(Carla, David), List(Evi, Flip, Gary, Hugo, Ida)), ...

26번 문제의 combinations 함수를 응용한 문제.

선택 가능한 리스트와 현재 단계에서 선택한 조합의 차이(diff 메소드)를 재귀호출하면 된다.

a, b 같은 문제. 파라미터로 받아올지 함수 내부에서 구현할지의 차이다.

b)

def group[A](sl: List[Int], lst: List[A]): List[List[List[A]]] = sl match {
  case h::t =>
    lst.combinations(h).map(s =>  // sl의 head 갯수만큼 만든 조합
    s :: group(t, lst.diff(s)).flatten // 조합을 제외한 엘리먼트들로 재귀호출
    ).toList 
  case Nil => Nil
}

추가로 그룹의 수를 입력받아 만들 수 있는 그룹을 모두 출력하는 문제를 생각해 보자.

이 때는 각 그룹이 가지는 엘리먼트의 수가 변할 수 있음을 고려해야 했다.

def group[A](c: Int, lst: List[A]): List[List[List[A]]] = {
  if (c == 1) List(List(lst))
  else {
    val result = for {i <- 1 to lst.size - c + 1  // 엘리먼트로 가질 수 있는 갯수
                      combs <- lst.combinations(i)  // 갯수만큼 조합을 만듦
                      r <- group(c - 1, lst.diff(combs)).map(combs :: _)} yield r 
                      // 나머지 요소로 재귀호출해 결과를 합침
    result.toList
  }
}

scala> val lst = List('A, 'B, 'C, 'D) lst: List[Symbol] = List('A, 'B, 'C, 'D) scala> group(3, lst).foreach(println) List(List('A), List('B), List('C, 'D)) List(List('A), List('C), List('B, 'D)) List(List('A), List('D), List('B, 'C)) List(List('A), List('B, 'C), List('D)) List(List('A), List('B, 'D), List('C)) List(List('A), List('C, 'D), List('B)) List(List('B), List('A), List('C, 'D)) ... List(List('B, 'D), List('C), List('A)) List(List('C, 'D), List('A), List('B)) List(List('C, 'D), List('B), List('A))