Re: [問題] 想寫個比對的function

[B9 (葉酸酸)]

我終於看懂你的題目了 = ="

題目是，給定一個數字 n，集合 s 為 0 到 n - 1 之間的任意整數。

求集合 s 的冪集（power set）中，元素個數介於 2 與 n - 1 之間的所有集合。

冪集 http://zh.wikipedia.org/wiki/%E5%86%AA%E9%9B%86

> -------------------------------------------------------------------------- <

這問題分四個步驟：

 1. 從數字 n 產生集合 s，這很簡單。
 2. 從集合 s 產生冪集 p，這要找 power set 的 algorithm
    http://www.google.com/search?q=power+set+algorithm
 3. 從 p 中過濾掉元素個數不合的集合，這也很簡單。
 4. 從 model 產生 view，這很簡單，for 跟 join 就可以解決了。
    這部份我沒 implement。

implementation：http://jsbin.com/ejefiw/edit#javascript,live


> -------------------------------------------------------------------------- <

source code:

(function()
{
    "use strict";

    // generate a set containing integers between 0 and n - 1. //
    function numberToSet(n)
    {
        var cx, set;
        for (cx = 0, set = []; cx < n; cx++)
            set.push(cx);
        return set;
    }

    // create a copy of set. //
    function cloneSet(set)
    {
        var cx, stack;
        for (cx = 0, stack = []; cx < set.length; cx++)
            stack[cx] = set[cx];
        return stack;
    }

    // find the combination of the element with every element in the set. //
    function addToSet(set, element)
    {
        var cx, length, clone;
        for (cx = 0, length = set.length; cx < length; cx++)
        {
            clone = cloneSet(set[cx]);
            clone.push(element);
            set.push(clone);
        }
        return set;
    }

    // find the power set of the set. //
    function powerSet(set)
    {
        var subset, element, power;

        // see wiki. //
        if (set.length)
        {
            element = set.pop();
            power = powerSet(set);
            return addToSet(power, element);
        }
        else
        {
            return [ [] ];
        }
    }

    function filterSet(set, isWanted)
    {
        var cx;
        for (cx = set.length - 1; cx >= 0; cx--)
            if ( !isWanted(set[cx]) )
                set.splice(cx, 1);
        return set;
    }

    function isWanted(set)
    {
        if (set.length < 3)
            return false;
        if (set.length >= n)
            return false;
        return true;
    }

    function view(set)
    {
        document.write("<pre>");
        document.write( JSON.stringify(set, null, 4) );
        document.write("</pre>");
        console.log(set);
    }

    var set, n = 4;
    set = numberToSet(n);
    set = powerSet(set);
    set = filterSet(set, isWanted);
    view(set);
})();

--

Oni devas ami animalojn. Ili estas tiel bongustaj.

One should love animals. They are so tasty.

每個人都應該愛動物，他們是如此美味。

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 175.180.52.7
※ 編輯: B9              來自: 175.180.52.7         (11/16 23:25)
推 kiey:謝謝分享...研究一下^^ 感謝...