分堆算法

micro@

Thankfully, there are some existing solutions:

<br />
library(partitions)<br />
ff = function(x,n){<br />
  if(n==1)return(matrix(paste(x,collapse='')))<br />
  sp=setparts(restrictedparts(length(unique(x)), n, FALSE));<br />
  apply(sp,2,function(z)tapply(x,z,FUN=paste,collapse=''))<br />
}<br />
ff(letters[1:4],2)<br />
ff(letters[1:5],3)<br />

</p>

dclong

我想说这不就是partition吗？

enthumelon

回复第9楼的 dclong：恰好没有用过那个包。也不知道那是啥，我只知道那个玩意儿的个数是个双脚标递归，哈哈～

笑笑说

回复第4楼的 enthumelon：谢谢！我想了几天没想出来，你一会儿就想出来了！感叹的同时有点沮丧。。[s:19]

笑笑说

回复第8楼的 micro@：谢谢！很方便！能请问下您是怎么找package的么？我找了几天楞是没找到。。

micro@

回复第12楼的笑笑说：The 1st hit when searching on google:

set partition site:r-project.org

</p>

笑笑说

回复第13楼的 micro@：谢谢你！

micro@

我也遇到类似的问题了[s:12]：

把N个个体分成K组，每组n[k]个，k=1..K。这样总共的分法有M种，其中M为

library(gmp)<br />
factorialZ(N)/prod(c(factorialZ(n), factorialZ(table(n))))<br />

</p>

现在如果M非常大，用partitions::setparts(n)枚举难以吃得消；所以只想从M种分法中随机抽取m<<M种(without replacement)，应该怎么抽取好呢[s:16]

many thanks

笑笑说

回复第15楼的 micro@：

能不能对每一个个体1到N，随机生成一个1到K的值？这样遍历一次就是一种分法了。

重复该程序m次，就有m种分法。

但这样不能保证每个组都有个体，而且m种分法中可能有重复的。

teary

回复第16楼的笑笑说：我觉得不重不漏在m大时就不用考虑啦，这也是一种合理的近似

这个不就是多组的permutation test的做法嘛。。应该是有一些性质的保证的。。

micro@

I agree with both discussions above, but my original question remains:

How to sample m out of M partitions without replacement efficiently without requiring enumerating all M non-equivalent paritions (assuming m is large and M is huge)[s:16]

笑笑说

回复第18楼的 micro@：我以为我在16楼的答案可以。您觉得不行么？

micro@

回复第19楼的笑笑说：Maybe I misunderstood something, but it seems to me a sampling "with" replacement scheme.

笑笑说

回复第20楼的 micro@：每次生成一种分法，将结果组织成一个二维表：一列为物品，一列为物品所在的包裹；按物品的id排列。如果某次分法结果的二维表跟以前的任何一个二维表相同，则舍弃这种分法。

就是您在7楼说的dirty post-mortem fix-up 了.

没有更简洁的办法帮到您，不好意思了。

micro@

It seems that some way to uniquely index each partition is needed.

For permutations, we can use factoradic numbers to index everything N! permutations. Given a factoradic nubmer, we can directly generate the corresponding permutation; and vice versa.

Is there any similar indexing scheme available for partitions?