2

xR を使用して、長nさのベクトルを最大でpartitionに分割するすべての可能な方法を見つけようとしています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 エラーをスローする前にいくつかの列を報告する単一の列がいくつかありました。そのため、より大きなマシンが必要になる場合があります。53 番目の列を構築する 32 GB の私の Mac では、メモリの半分が消費されました。大きなマシンの列数の見積もりは、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 に答える