6

作成した一連の数値をデータとして含むリンクされたリストを使用しています。このリストの可能なすべての 2 セット パーティションをテストする方法を見つける必要があります。そのためには、リストを可能なすべての 2 セットの組み合わせに分割する必要があります。順序は重要ではなく、重複があります。 

For instance, for a list of numbers {1 4 3 1}, the possible splits are 

{1} and {4, 3, 1}
{4} and {1, 3, 1}
{3} and {1, 4, 1}
{1} and {1, 4, 3}
{1, 4} and {3, 1}
{1, 3} and {4, 1}
{1, 1} and {4, 3}

4つの数字のリストは難しくありませんが、リストが大きくなるにつれて複雑になり、パターンを見つけるのに苦労しています. このためのアルゴリズムを見つけるのを手伝ってくれる人はいますか?

編集：

質問がわかりませんでした。これは私がこれまでに試したことです。私のループ構造は間違っています。通常の配列を試した後に自分が何をしているのかを理解したら、リンクされたリストに合うようにアルゴリズムを拡張します。

public class TwoSubsets
{
    public static void main(String[] args)
    {
        int[] list = {1, 3, 5, 7, 8};
        int places = 1;

        int[] subsetA = new int[10];
        int[] subsetB = new int[10];


        for (int i = 0; i < list.length; i++)
        {
            subsetA[i] = list[i];       
            for (int current = 0; current < (5 - i ); current++)
            {
                subsetB[current] = list[places];        
                places++;

            }

            System.out.print("subsetA = ");
            for (int j = 0; j < subsetA.length; j++)
            {
                System.out.print(subsetA[j] + " ");
            }

            System.out.println();
            System.out.print("subsetB = ");
            for (int k = 0; k < subsetB.length; k++)
            {
                System.out.print(subsetB[k] + " ");
            }



        }
    }

}
4

3 に答える 3

1

したがって、補完的なものを除いて、特定のセットのすべての（適切な）サブセットを探しています。リストに n 個の要素がある場合、2^n 個のサブセットがあります。しかし、空のサブセットは必要なく、パーティション (A,B) を (B,A) で識別したいので、2^(n-1)-1 パーティションが得られます。

それらを列挙するには、n 桁の 2 進数でパーティションを識別できます。位置 k の数字 0 は、リストの k 番目の要素がパーティションの最初のセットにあることを意味し、1 はそれが 2 番目のセットにあることを意味します。 . 数値をその補数 (セットを他のセットと交換) で識別し、0 (空のサブセット) を除外したい。

したがって、ビット演算を使用できます。XOR 演算子は、補完的な細分化を提供します。したがって、次のようなものが機能するはずです。

int m = (1<<n)-1; // where n is the number of elements, m=111111...11 in binary
for (int i=0;i<m-1;++i) {
    if (i>(m^i)) continue; // this was already considered with 0 and 1 exchanged
    // here the binary digits of i represent the partition
    for (int j=0;j<n;++j) {
       if ((1<<j) & i) {
          // the j-th element of the list goes into the second set of the partition
       } else {
          // the j-th element of the list goes into the first set of the partition
       }
    }
}
于 2013-11-10T16:45:18.377 に答える
0

リンクされたリストを使用してサブセットを保存することは、実際には非常に理想的です。コードは、配列を使用するよりも簡単にまとめられます。

サブセットを構築する再帰関数を書きます。次の引数を取ります。

  • 「入力」リスト
  • 「出力」リスト
  • 結果のベクトル (これが何かを意味する場合、これは「収集パラメーター」になります)

Ruby での大まかなコード スケッチを次に示します。

 # 'input', and 'output' are linked-list nodes
 # we'll assume they have 'value' and 'next' attributes
 # we'll further assume that a new node can be allocated with Node.new(value,next)
 # the lists are null-terminated

 def build_subsets(input, output, results)
   if input.nil?
     results << output
   else
     item = input.value
     input = input.next
     build_subsets(input, Node.new(item, output), results)
     build_subsets(input, output, results)
   end
 end

次のように呼び出します。

 results = []
 build_subsets(list, nil, results)

その後、すべてのサブセットが になりますresults。Java への翻訳が必要なことは承知していますが、Java への翻訳は簡単なはずです。コードがどのように機能するかについてのアイデアを提供しているだけです。

于 2013-11-10T19:59:51.310 に答える