0

S1 の要素の合計 = S2 の要素の合計である集合 S の素集合 S1 と S2 (S1 U S2 は S ではない可能性があります) のペアがいくつ存在するかを計算したいと思います。

考えられるすべての 2^n サブセットのすべてのサブセット合計を計算したとします。合計が等しいばらばらの部分集合の数を調べるにはどうすればよいですか?

合計値 A の場合、これを解くために合計 A/2 を持つサブセットの数を使用できますか?

例として: S ={1,2,3,4}

可能なさまざまな S1 および S2 セットは次のとおりです。

S1 = {1,2} および S2 = {3}

S1 = {1,3} および S2 = {4}

S1 = {1,4} nd S2 = {2,3}

問題へのリンクは次のとおりです 。 http://www.usaco.org/index.php?page=viewproblem2&cpid=139

4

2 に答える 2

0

これがclojureソリューションです。

s を 1, 2, 3, 4 のセットと定義し、all-subsets をサイズ 1 ～ 3 のすべてのセットのリストと定義します。

すべてのサブセットが定義されると、サブセットのすべてのペアが調べられ、等しくなく、元のセットと結合せず、合計が等しいペアのみが選択されます。

(require 'clojure.set)
(use 'clojure.math.combinatorics)

(def s #{1, 2, 3, 4})
(def subsets (mapcat #(combinations s %) (take 3 (iterate inc 1))))

(for [x all-subsets y all-subsets 
          :when (and (= (reduce + x) (reduce + y)) 
                     (not= s (clojure.set/union (set x) (set y))) 
                     (not= x y))] 
      [x y])

以下を生成します。

([(3) (1 2)] [(4) (1 3)] [(1 2) (3)] [(1 3) (4)])
于 2013-10-21T17:33:18.353 に答える