2

我编写的一个小应用程序允许用户将各种项目添加到两个数组中。一些逻辑根据每个数组的内容计算一个数字。

数组 x 中的任何项目都可以放入数组 y 中，然后再放回去。属于数组 y 的项永远不能移动（除非它们是从数组 x 中移动的）。

用户可以使用简单的 javascript ui 在两个列表中移动这些项目。为了让事情更简单，我最初制作了一个简单的脚本：

  1. 将项目从 a 移动到 y。
  2. 使用这种“可能性”执行了一些逻辑
  3. 如果结果小于以前，则将 x 留在 y 中。
  4. 如果不是，则 x 保留在 x 中。
  5. 移动到 x 中的下一项并重复。

我知道这是无效的。我已经阅读并被告知使用按位数学来记住可能性或“排列”，但在这个阶段我正在努力解决这个特定问题。

如果有人能够解释（伪代码很好）什么是实现以下目标的最佳方法，我将不胜感激。

数组 x = [100,200,300,400,500] 数组 y = [50,150,350,900]

使用这两个数组，对于来自 x 的每个值，将该值和来自 x 的所有其他值的每个组合推入数组 y。对于每一个，我将执行一些逻辑（即测试结果并将这个“排列”存储在一个数组中（一个代表 x 和 y 的两个数组的对象）。我预见这对于大型数组来说非常昂贵，可能会重复很多我觉得我快到了，但在最后阶段迷路了。

抱歉，解释太长了，在此先感谢！

4

1 回答 1

1

使用它来创建 的幂集x：

function power(x, y) {
    var r = [y || []], // an empty set/array as fallback
        l = 1;
    for (var i=0; i<x.length; l=1<<++i) // OK, l is just r[i].length, but this looks nicer :)
        for (var j=0; j<l; j++) {
            r.push(r[j].slice(0)); // copy
            r[j].push(x[i]);
        }
    return r;
}

用法：

> power([0,2], [5,6])
[[5,6,0,2], [5,6,2], [5,6,0], [5,6]]

有人告诉我使用按位数学来记住可能性或“排列”，但在这个阶段我正在努力解决这个特殊问题。

它将迭代到 2 n（对于长度为 n 的数组），使用单个位来确定项目是否应包含在子集中。数组 [a,b] 的示例：

i   binary   included in set
-----------------------------
0   00       {      }
1   01       {    b }
2   10       { a    }
3   11       { a, b }

我们可以在 JS 中对最多包含 31 个项目的数组使用位运算符（这应该足够了）。

function power(x, y) {
    var l = Math.pow(2, x.length),
        r = new Array(l);
    for (var i=0; i<l; i++) {
        var sub = y ? y.slice(0) : [];
        for (var j=0; j<x.length; j++)
            // if the jth bit from the right is set in i
            if (i & Math.pow(2,j)) // Math.pow(2,j) === 1<<j
                sub.push(x[j]);
        r[i] = sub;
    }
    return r;
}
于 2013-03-26T23:59:23.543 回答