6

6 個のボール (白 3 個と黒 3 個) が入ったバッグがあるとします。順序を無視して、指定された長さのすべての可能なサブセットを見つけたいです。上記の場合、袋から取り出すことができる 3 つのボールの組み合わせは 4 つだけです。

  • 白 2 個と黒 1 個
  • 黒2つと白1つ
  • 3 白
  • 3黒

選択した言語でまさにこれを行うライブラリを既に見つけましたが、数が多いと遅いことがわかります。たとえば、白が 15 個、黒が 1 個、青が 1 個、赤が 1 個、黄が 1 個、緑が 1 個入っている袋の場合、10 個の玉の組み合わせは 32 通りしかありませんが、結果を出すのに 30 秒かかります。

自分で実装できるすべての組み合わせを見つけることができる効率的なアルゴリズムはありますか? たぶん、この問題は私が最初に思ったほど簡単ではありません...

注: これを表現する適切な技術用語もわかりません。投稿のタイトルを自由に修正してください。

4

2 に答える 2

1

いいえ、すべての可能な選択肢を検索する必要はありません。単純な再帰アルゴリズム (@recursive で指定されたものなど) で答えが得られます。組み合わせの数だけでなく、実際にすべての組み合わせを出力する関数を探している場合は、R で記述されたバージョンを次に示します。どの言語で作業しているかわかりませんが、これを翻訳するのはかなり簡単ですただし、R はこの種の処理が得意なので、コードは長くなる可能性があります。

allCombos<-function(len, ## number of items to sample
                    x,   ## array of quantities of balls, by color
                    names=1:length(x)  ## names of the colors (defaults to "1","2",...)
){
  if(length(x)==0)
    return(c())

  r<-c()
  for(i in max(0,len-sum(x[-1])):min(x[1],len))
      r<-rbind(r,cbind(i,allCombos(len-i,x[-1])))

  colnames(r)<-names
  r
}

出力は次のとおりです。

> allCombos(3,c(3,3),c("white","black"))
     white black
[1,]     0     3
[2,]     1     2
[3,]     2     1
[4,]     3     0
> allCombos(10,c(15,1,1,1,1,1),c("white","black","blue","red","yellow","green"))
      white black blue red yellow green
 [1,]     5     1    1   1      1     1
 [2,]     6     0    1   1      1     1
 [3,]     6     1    0   1      1     1
 [4,]     6     1    1   0      1     1
 [5,]     6     1    1   1      0     1
 [6,]     6     1    1   1      1     0
 [7,]     7     0    0   1      1     1
 [8,]     7     0    1   0      1     1
 [9,]     7     0    1   1      0     1
[10,]     7     0    1   1      1     0
[11,]     7     1    0   0      1     1
[12,]     7     1    0   1      0     1
[13,]     7     1    0   1      1     0
[14,]     7     1    1   0      0     1
[15,]     7     1    1   0      1     0
[16,]     7     1    1   1      0     0
[17,]     8     0    0   0      1     1
[18,]     8     0    0   1      0     1
[19,]     8     0    0   1      1     0
[20,]     8     0    1   0      0     1
[21,]     8     0    1   0      1     0
[22,]     8     0    1   1      0     0
[23,]     8     1    0   0      0     1
[24,]     8     1    0   0      1     0
[25,]     8     1    0   1      0     0
[26,]     8     1    1   0      0     0
[27,]     9     0    0   0      0     1
[28,]     9     0    0   0      1     0
[29,]     9     0    0   1      0     0
[30,]     9     0    1   0      0     0
[31,]     9     1    0   0      0     0
[32,]    10     0    0   0      0     0
>
于 2013-10-03T18:31:56.293 に答える