两个数组，其中数组 x 中的项可以在数组 y 中，反之亦然，测试所有排列 [英] Two arrays, where items in array x can be in array y but not vice versa, test all permutations

问题描述

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

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

抱歉解释太长，提前致谢！

解决方案

使用它来创建 power set<x 的/a>:

function power(x, y) {var r = [y ||[]],//一个空集/数组作为后备l = 1;for (var i=0; i<x.length; l=1<<++i)//好吧，l 只是 r[i].length，但这看起来更好 :)for (var j=0; j

用法:

>功率([0,2]，[5,6])[[5,6,0,2], [5,6,2], [5,6,0], [5,6]]

<小时><块引用>

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

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

i 二进制包含在集合中-----------------------------0 00 { }1 01 { b }2 10 { 一个 }3 11 { a, b }

我们可以在 JS 中使用 按位运算符最多包含 31 个项目的数组(应该足够了).

function power(x, y) {var l = Math.pow(2, x.length),r = 新数组(l)；for (var i=0; i<l; i++) {变量子 = y ?y.slice(0) : [];for (var j=0; j

A small application that I have written allows a user to add various items to two arrays. Some logic calculates a figure from the contents of each array.

Any items in array x can be placed into array y, and back again. Items belonging in array y can never be moved (unless they were moved from array x).

The user can move these items around in two lists using a simple javascript ui. To make things simpler, I originally made a naive script which:

1. Moved an item from a to y.
2. Performed some logic using this 'possibility'
3. If the result was less than before, leave x in y.
4. If not, then x remains in x.
5. Move on to next item in x and repeat.

I knew that this was ineffective. I have read around and 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.

If anyone would be able to explain (pseudo code is fine) what would be the best way to achieve the following I would be very grateful.

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

With these two arrays, for each value from x, push every combination of that value and all the other values from x into array y. For each one I will perform some logic (i.e. test result and store this 'permutation' in an array (an object of two arrays representing x and y). I foresee this as being quite expensive with large arrays, likely to repeat a lot of combinations. I feel like I'm almost there, but lost at this last stage.

Sorry for the long explanation, and thanks in advance!

解决方案

Use this for creating the power set of 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;
}

Usage:

> 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.

It would be iterating to 2ⁿ (for an array of length n), using single bits to determine whether an item should be included in the subset. Example for an array [a,b]:

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

We can use bitwise operators in JS for arrays with up to 31 items (which should be enough).

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;
}

这篇关于两个数组，其中数组 x 中的项可以在数组 y 中，反之亦然，测试所有排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！