1

これは、Michael T Goodrich と Robert Tamassia による Data Structures and Algorithms in Java からの質問です。これを行う方法？どんな助けでも感謝します。

これは私が考えたことです、間違っていたら訂正してください：

要素を Stack に格納します。最初の要素をポップしてキューに格納し、スタック内の残りの要素がサブセットを形成します。スタックを復元し、2 番目の要素をポップし (キューで最初にポップし、キューで 2 番目にポップし、キューからプッシュします)、別のサブセットからスタック内の残りの要素をポップします。同様に、3 番目の要素をポップし、次に 4 番目の要素をポップします。今度は、2 つの要素、次に 3 つの要素で同じことを行う番でしょうか? 質問を誤解して、広げすぎましたか?

4

3 に答える 3

0

ここから盗まれた合理的な解決策があると思います：http://arstechnica.com/civis/viewtopic.php?f=20&t=96354&sid=e74a29103e9297050680afbba6b72f32&start=40

つまり、キューがサブセットを保持し、スタックが元のセットを保持するという考え方です。空のセットはすべてのセットのサブセットであるため、キューを初期化します。次に、スタック上の各要素について、ポップオフします。ここで、Queue の各サブセットについて、そのサブセットをキューから取り出し、2 つのコピーをキューに入れます。難しいのは、スタックの次の要素をいつポップする必要があるか (つまり、現在の要素を使い終わったとき) を追跡することです。これを行う 1 つの方法は、一致するセットのキュー全体をチェックすることです (つまり、構築したこのサブセットを既に追加していることを意味します... 停止します)。しかし、より良い/よりクリーンな方法は、空のセットをマーカーとして使用することです。

基本的に、典型的な再帰的なソリューションがあります：

GenerateSubsets(Set set)
{
    if (set == Set.EmptySet)
        return new List<Set>(set);

    var elem = set.Remove();
    var subsets = GenerateSubsets(set);
    // Add all of thew subsets that contain elem (i.e. partition all subsets
    // by whether they contain elem or do not contain elem)
    subsets.AddRange(subsets.Map(subset => subset.Add(elem));

    return subsets;
}

そして、Queue が反復的に構築subsetsされ、元のセットが Stack に格納されるというまったく同じ考え方を使用します。

GenerateSubsets(Stack originalSetAsStack)
{
    var queue = new Queue { new Set() };
    while (!originalSetAsStack.IsEmpty)
    {
        var elem = originalSetAsStack.Pop();
        while (true)
        {
            var currSubset = queue.Dequeue();
            // This is key. This is how we know when to start
            // the next iteration!
            // This also assumes that any two empty sets are equal...
            if (currSubset == new Set())
            {
                break;
            }

            var subsetWithElem = currSubset.Clone();
            subsetWithElem.Add(elem);
            // Add back in current subset. This has to be first!
            // for our break to work above
            queue.Queue(currSubset);
            queue.Queue(subsetWithElem);
        }
    }

    return queue;
}

この解決策が再帰的な解決策に由来する理由を示すため。観察: サブセットを繰り返し構築します。

-Start with the empty set => ({})
-Take some element from the stack
-Now for each element in the Queue, enqueue two: one with the current
element, and one without => ({}, {elem})
-Now take the next element and do the same => ({}, {elem}, {nextElem}, 
{elem, NextElem})
-Now take the third element and do the same => ({}, {elem}, {nextElem}, 
{elem, nextElem}, {thirdElem}, {thirdElem, elem}, {thirdElem, nextElem}, 
{elem, nextElem, thirdElem})
-...
于 2013-04-12T08:48:21.657 に答える