在Scala中计算具有特定子集大小的集合分区

我想确定给定的整数列表{1，...，n}的所有分区，其中分区的元素具有{1，无机氮，...，Nmax个}。在Scala中计算具有特定子集大小的集合分区

例如：给定一个整数列表{1,2,3,4}应该确定所有分区，为此，分区的元素在{1，Nmin = 2，...，Nmax中具有基数= {1,2}，{3,4}}，P2 = {{1,3}，{2,4}}，P3 = {{2,3}，{ P4 = {{1}，{2,3,4}}，P5 = {{2}，{1,3,4}}，P6 = {{3}，{1,2,3} P8 = {{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的例子中，无机氮= 2和Nmax个= 3和输出P = {P1，P2，...，P11}。

我想做到这一点在Scala中以递归的方式...

来源

2014-03-25 user1537137

所有的问题，你表明你自己回答他们的努力是值得欢迎的。这就是你和社区的好处。只发布问题使得它看起来像某人甚至懒得制作代码存根。 –

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

来源

2014-03-25 15:20:26 atretkow

在Scala中计算具有特定子集大小的集合分区

回答

相关问题