DisjointSubset.scala

// A solution for disjoint subset problem (P27)
// which is described in 99 Scala problem http://aperiodic.net/phil/scala/s-99/

package kata

object Kata {
  def group3(names: Set[String]): List[List[Set[String]]] =
    group(List(2, 3, 4), names)

  def group(groupSizes: List[Int], names: Set[String]): List[List[Set[String]]] =
    groupHelper(groupSizes, names, List())

  private def groupHelper: (List[Int], Set[String], List[Set[String]]) => List[List[Set[String]]] = {
    case (groupSizes, _, currentStack) if groupSizes.isEmpty  => List(currentStack)
    case (_, availableItems, _) if availableItems.isEmpty => List()
    case (groupSizes, availableItems, currentStack) =>
      for { currentGroup <- combinations(groupSizes.head, availableItems)
          solution <- groupHelper(groupSizes.tail, availableItems -- currentGroup, currentStack :+ currentGroup) }
        yield solution
  }

  def combinations(k: Int, items: Set[String]) =
    combinationHelper(k, items, Set())

  private def combinationHelper: (Int, Set[String], Set[String]) => List[Set[String]] = {
    case (0, _, currentStack) => List(currentStack)
    case (_, availableItems, _) if availableItems.isEmpty => List()
    case (itemLeft, availableItems, currentStack) =>
      combinationHelper(itemLeft - 1, availableItems.tail, currentStack + availableItems.head) :::
      combinationHelper(itemLeft, availableItems.tail, currentStack)
  }
}