Расчет разделов набора с определенными размерами подмножества в Scala

Я хотел бы определить все разделы данного списка целых чисел {1, ..., n}, где элементы разделов обладают определенной мощностью k в {1, Nmin, ..., Nmax}.

Например: для списка целых чисел {1,2,3,4} должны быть определены все разделы, для которых элементы разделов имеют мощность в {1, Nmin = 2, ..., Nmax = 3}, т.е. P1 = {{1,2}, {3,4}}, P2 = {{1,3}, {2,4}}, P3 = {{2,3}, {1,4}}, P4 = {{1}, {2,3,4}}, P5 = {{2}, {1,3,4}}, P6 = {{3}, {1,2,3}}, P7 = { {4}, {1,2,3}}, P8 = {{1,2}, {3}, {4}}, P9 = {{2,3}, {1}, {4}}, P10 = {{3,4}, {1}, {2}}, P11 = {{1,4}, {2}, {3}}.

Функция должна выглядеть так:

def detPartSpecSubSize(n: Int,Nmin: Int,Nmax:int) : List[List[List[Int]]] {
... 
}

В приведенном выше примере n = 4, Nmin = 2 и Nmax = 3, а выход P = {P1, P2, ..., P11}.

Я бы хотел сделать это на Scala рекурсивно ...


scala partition combinatorics
person user1537137    schedule 25.03.2014    source источник
comment
Все вопросы, на которые вы проявляете старание, отвечая на них самостоятельно, более чем приветствуются. Вот что приносит пользу вам и сообществу. Публикация только вопроса делает вид, что кто-то слишком ленив, чтобы даже сделать заглушку кода.   -  person Haris Osmanagić    schedule 25.03.2014

Ответы (1)


arrow_upward
0
arrow_downward 

  def detPartSpecSubSize(n: Int, Nmin: Int, Nmax: Int): List[List[List[Int]]] = {
    val all = (1 to n).toList
    val cardinalityList = (Nmin to Nmax).toSet + 1

    def _detPartSpecSubSize(elements: Set[Int]): Set[Set[List[Int]]] = {
      def subsets(card: Int): List[List[Int]] = {
        def _subsets(elements_ : Set[Int], n: Int): Set[Set[Int]] = {
          if (n == 0 || elements_.size < n) Set(Set())
          else {
            for {
              elem <- elements_
              moreElem <- _subsets(elements_ - elem, n - 1)
              if (1 + moreElem.size == n)
            } yield (moreElem + elem)
          }

        }

        _subsets(elements, card).toList.map(_.toList)
      }

      if (elements.size == 0) Set(Set())
      else {
        for {
          c <- cardinalityList
          part <- subsets(c)
          if (part.length == c)
          rest = elements -- part.toSet
          more <- _detPartSpecSubSize(rest.toSet)

        } yield more + part
      }
    }

    _detPartSpecSubSize(all.toSet).toList.map(_.toList)
  }

Вывод detPartSpecSubSize (4, 2, 3):

List(List(4), List(3, 2, 1))
List(List(2), List(4, 3, 1))
List(List(4), List(3), List(2, 1))
List(List(3), List(1), List(4, 2))
List(List(3), List(2), List(4, 1))
List(List(4), List(1), List(3, 2))
List(List(1), List(4, 3, 2))
List(List(4), List(3), List(2), List(1))
List(List(4, 3), List(2, 1))
List(List(4, 1), List(3, 2))
List(List(4, 2), List(3, 1))
List(List(2), List(1), List(4, 3))
List(List(3), List(4, 2, 1))
List(List(4), List(2), List(3, 1))
person atretkow    schedule 25.03.2014