10

これに対する答えがどこにも見つからなかったので、ここに私の解決策があります。

問題は、R の累乗をどのように計算できるかということです。

これは、ライブラリ「sets」のコマンドを使用して実行できます。2^as.set(c(1,2,3,4))これにより、出力が得られます{{}, {1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}, {1, 2, 3, 4}}。ただし、これはかなり遅い再帰アルゴリズムを使用します。

これが私が思いついたアルゴリズムです。

これは非再帰的であるため、他のいくつかのソリューションよりもはるかに高速です (私のマシンでは、「sets」パッケージのアルゴリズムよりも約 100 倍高速です)。速度はまだ O(2^n) です。

このアルゴリズムの概念的な基礎は次のとおりです。

for each element in the set:
    for each subset constructed so far:
        new subset = (subset + element)

Rコードは次のとおりです。

編集:これは、同じ概念のやや高速なバージョンです。私のオリジナルのアルゴリズムは、この投稿への 3 番目のコメントにあります。これは、私のマシンでは長さ 19 のセットで 30% 高速です。

powerset = function(s){
    len = length(s)
    l = vector(mode="list",length=2^len) ; l[[1]]=numeric()
    counter = 1L
    for(x in 1L:length(s)){
        for(subset in 1L:counter){
            counter=counter+1L
            l[[counter]] = c(l[[subset]],s[x])
        }
    }
    return(l)
}

このバージョンでは、最初に最終的な長さでベクトルを開始し、新しいサブセットを保存する位置の「カウンター」変数を追跡することで時間を節約します。分析的に位置を計算することも可能ですが、それは少し遅くなりました。

4

4 に答える 4

4

あなたの関数や他の答えの関数よりも速いと思われる関数powersetがパッケージにあります。HapEstXXR以下を参照してください（関数が呼び出されますyour.powerset）

require('microbenchmark')
require('HapEstXXR')
microbenchmark(powerset(LETTERS[1:10]), f(LETTERS[1:10]), your.powerset(LETTERS[1:10]), times=100)


Unit: microseconds
                         expr      min        lq    median        uq       max neval
      powerset(LETTERS[1:10])  314.845  388.4225  594.2445  686.6455   857.513   100
             f(LETTERS[1:10]) 7144.132 7937.6040 8222.1330 8568.5120 17805.335   100
 your.powerset(LETTERS[1:10]) 5016.981 5564.2880 5841.9810 6025.0690 29138.763   100

powerset非常に高速に見えるため、パッケージ内の関数のコードを確認することをお勧めしますHapEstXXR。

于 2013-09-10T12:48:29.333 に答える