javascript - 两个数组，其中数组 x 中的项目可以在数组 y 中但反之亦然，测试所有排列

Question

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

数组 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 的两个数组的对象)。我预见这对于大型数组来说非常昂贵，可能会重复很多组合。我觉得我快到了，但在最后阶段迷路了。

抱歉解释得太长了，提前致谢!

Answer 1

使用它来创建 power set 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]]

---

I have been told do this using bitwise math to remember the possibilities or 'permutations' but I am struggling to get my head around this particular problem at this stage.

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

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

我们可以使用bitwise operators在 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;
}