作者B9 (葉酸酸)
看板Ajax
標題Re: [問題] 想寫個比對的function
時間Wed Nov 16 23:21:50 2011
我終於看懂你的題目了 = ="
題目是，給定一個數字 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)
1F：推 kiey:謝謝分享...研究一下^^ 感謝... 11/17 18:31