0

我想确定给定整数列表 {1,...,n} 的所有分区，其中分区的元素在 {1,Nmin,...,Nmax} 中具有特定的基数 k。

例如：给定整数列表 {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中做到这一点......

4

1 回答 1

0 
  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)
  }

The output from detPartSpecSubSize(4, 2, 3) is:

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))
于 2014-03-25T15:20:26.383 回答