4

セット S の 2 つの要素に対して関数を計算する必要がある Cuda アプリケーションを作成していますが、ペアの順序は何の違いもありませんf(a,b)。f(b,a)

そのため、セット間で要素のペアを複製することなく、最大サイズ K の S のすべてのサブセットを生成したいと考えています。

言い換えれば、任意の 2 つのサブセットが与えられた場合、それらの共通部分が 1 つの要素よりも大きくなりたくないということです。(このようにして、これらの 2 つの要素の関数を複数回計算することを避けることができます)

例：

と が与えられるS={1,2,3,4,5,6,7,8,9}とK=3、出力は次のようになります。

{ {1,2,3}, {1,4,5}, {1,6,7}, {1,8,9}, {2,4,6}, {2,5,7}, {2,8}, {2,7,9}, {3,4,7},
  {3,5,8}, {3,6,9}, {4,5,9} }

ただし、出力は次のようにはなりません。

{ {1,2,3}, {1,4,5}, {1,6,7}, {1,8,9}, {2,4,6}, {2,5,7}, {2,6,8}, {2,7,9}, {3,4,7},
  {3,5,8}, {3,6,9}, {4,5,9} }

{2,4,6}との交点{2,6,8}は です{2,6}。

4

3 に答える 3

0

あなたはこれを行うことができます ：

    P := {1, 2, 3, 4, 5, 6}; setpartition(P, 3);
   {{{1, 2, 3}, {4, 5, 6}}, {{1, 2, 4}, {3, 5, 6}}, 

     {{1, 2, 5}, {3, 4, 6}}, {{1, 2, 6}, {3, 4, 5}}, 

     {{1, 3, 4}, {2, 5, 6}}, {{1, 3, 5}, {2, 4, 6}}, 

     {{1, 3, 6}, {2, 4, 5}}, {{1, 4, 5}, {2, 3, 6}}, 

     {{1, 4, 6}, {2, 3, 5}}, {{1, 5, 6}, {2, 3, 4}}}
于 2012-05-16T08:00:09.710 に答える
0 
>>> from itertools import combinations, chain
>>> s = {1,2,3,4,5,6,7,8,9}
>>> k = 3
>>> seen = set()
>>> subset_sizes = reversed(range(2,k+1)) # [3,2] for this example. Reversed since you favor the sets with larger values of K
>>> for item in chain.from_iterable(combinations(s,i) for i in subset_sizes):
        pairs = set(combinations(item,2))
        if not pairs.intersection(seen):
            seen.update(pairs)
            print item


(1, 2, 3)
(1, 4, 5)
(1, 6, 7)
(1, 8, 9)
(2, 4, 6)
(2, 5, 7)
(3, 4, 7)
(3, 5, 6)
(2, 8)
(2, 9)
(3, 8)
(3, 9)
(4, 8)
(4, 9)
(5, 8)
(5, 9)
(6, 8)
(6, 9)
(7, 8)
(7, 9)
于 2012-04-28T21:11:22.517 に答える