作者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