2

我正在尝试使用 R 找到将x长度向量n划分为最多m分区的所有可能方法。我知道在小的时候该怎么做n：

library(partitions)
x <- c(10, 20, 30, 40)
n <- length(x)
m <- 3

# In how many ways can we partition n objects into at most m patitions
parts <- restrictedparts(n, m)
sets <- setparts(parts)

在本例中，值为sets：

[1,] 1 1 1 1 2 1 1 1 1 1 1 2 2 2
[2,] 1 1 1 2 1 2 1 2 2 1 2 1 1 3
[3,] 1 2 1 1 1 2 2 1 3 2 1 3 1 1
[4,] 1 1 2 1 1 1 2 2 1 3 3 1 3 1

的每一列都sets告诉我，对于每个独特的排列，x应该将每个项目分配到哪个分区。

大时会出现问题n：

n <- 15
m <- 4
parts <- restrictedparts(n, m)
# This expression will max out your CPU usage and eventually run out of memory.
sets <- setparts(parts)

如何在不耗尽内存的情况下执行此操作？我怀疑是否有一种快速的方法可以做到这一点，所以我怀疑我必须分批完成并写入磁盘。

4

3 回答 3

3

如果像我一样你不是组合学的超级明星，但你相信partitions它是正确的，那么至少你可以利用包的代码来计算最终的分区数。在这里，我破解了这个setparts函数，所以它返回的不是分区本身，而是分区的数量：

num.partitions <- function (x) {
    if (length(x) == 1) {
        if (x < 1) {
            stop("if single value, x must be >= 1")
        }
        else if (x == 1) {
            out <- 1
        }
        else return(Recall(parts(x)))
    }
    if (is.matrix(x)) {
        out <- sum(apply(x, 2, num.partitions))
    }
    else {
        x   <- sort(x[x > 0], decreasing = TRUE)
        out <- factorial(sum(x))/(prod(c(factorial(x), 
                                         factorial(table(x)))))
    }
    return(out)
}

让我们检查该函数是否返回正确的分区数：

num.partitions(restrictedparts(4, 3))
# [1] 14
ncol(setparts(restrictedparts(4, 3)))
# [1] 14

num.partitions(restrictedparts(8, 4))
# [1] 2795
ncol(setparts(restrictedparts(8, 4)))
# [1] 2795

现在让我们看看你的大案子：

num.partitions(restrictedparts(15, 4))
# [1] 44747435

那确实是相当多的分区......无论setparts写得有多好，输出都无法放入单个数组中：

sets <- matrix(1, 15, 44747435)
# Error in matrix(1, 15, 44747435) : 
#  cannot allocate vector of length 671211525

所以是的，你必须编写自己的算法并存储到矩阵列表中，或者如果它对你的记忆来说太多了，如果这确实是你想要做的，那么写入一个文件。否则，考虑到相当多的排列以及你想用它们做什么，回到绘图板......

于 2013-01-13T19:30:08.020 回答
1

如果您想分批计算它们，似乎至少对于某些列来说这可能是可能的。我无法在restrictedparts(15,4)像您这样的机器上完成对几个单独列的计算。直到第 40 列，我一次可以在 5-10 列的批次中获得成功，但在此之上，有几个单列在引发 malloc 错误之前确实报告了许多列。所以你可能只需要一台更大的机器。在我的 Mac 上，构建第 53 列的 32 GB 占用了一半的内存。大机器上的列数估计与 4GB 机器上的报告一致：

> ncol( setparts( restrictedparts(15,4)[,53]))
[1] 6306300
R(317,0xa077a720) malloc: *** mmap(size=378380288) failed (error code=12)
*** error: can't allocate region
*** set a breakpoint in malloc_error_break to debug

（我对这是否是一个明智的项目没有意见。）

于 2013-01-13T18:27:08.923 回答
0

由于我无法安装分区包（缺少库），我想出了这个：

 ## Recursive function to get all partitions of a vector 
 ## Returns a list of logical vectors
 parts <- function(x) { 
   if (length(x) == 1) return(list(FALSE, TRUE))
   do.call(c, lapply(parts(x[-1]), function(y) list(c(FALSE, y), c(TRUE, y))))
 }

这个函数接受一个向量并返回一个相同大小的逻辑向量列表。列表中的向量数是可能的分区数，(2^n)。它无法处理巨大的 n，但在我的电脑上，它在不到一秒的时间内运行 n=19。

如果您只想要非空分区并且没有重复，请使用：

 partitions <- parts(x)
 partitions <- partitions[1:(length(partitions)/2)][-1]
于 2018-01-30T11:26:52.070 回答