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

问题描述

这是我写的一个小应用程序允许用户以不同的项目添加到两个数组。一些逻辑计算从每个阵列的内容的图。

在数组x任何物品可以放入量阵列y，然后再返回。在列Y属于项目不能被移动（除非他们是从数组x移动）。

用户可以在左右两个列表使用一个简单的JavaScript界面​​移动这些物品。为了让事情变得更简单，我原来做了一个幼稚脚本：

1. 动了一个项目从为y。


2. 执行使用这种可能性一些逻辑


3. 如果结果是比以前少了，留中X年。


4. 如果不是，那么x仍然以x


5. 将到下一个项目在x和重复。

我知道，这是无效的。我已阅读和周围有人告诉做到这一点使用按位数学要记住的可能性或排列但我挣扎在这个阶段让我解决这个特定问题的头。

如果任何人能解释（伪code是罚款），这将是实现以下我将非常感激的最好方式。

数组x = [100,200,300,400,500]
   数组Y = [50150350900]

使用这两个数组，对于从x中的每个值，按该值和所有其他值的每一种组合，从x转换成量阵列y。对于每一个我将执行一些逻辑（如测试结果和阵列中的存储这个'置换'（两个数组的对象重新presenting x和y）。我预计这为与大型阵列相当昂贵，可能重复了很多的组合。我觉得我几乎没有，但在这个最后阶段失去了。

在此先感谢对不起，长解释，！

解决方案

使用此为创建发电机组的 X ：

 函数power（X，Y）{
    变种R = [Y || []，//一个空的集合/数组作为备用
        L = 1;
    对于（VAR I = 0; I＆LT; x.length，L = 1＆LT;＆LT; ++ I）// OK，L只是 -  [R [I]。长度，但这个看起来更好:)
        为（VAR J = 0; J＆下;升; J ++）{
            r.push（R [J] .slice（0））; //副本
             -  [R [J] .push（X [I]）;
        }
    返回ř;
}
 

用法：

 ＆GT;功率（[0,2]，[5,6]）
[5,6,0,2]，[5,6,2]，[5,6,0]，[5,6]
 

---

  

有人告诉我做到这一点使用按位数学要记住的可能性或排列但我挣扎在这个阶段让我解决这个特定问题的头。

有将被迭代2 ^N （对于长度为n的阵列），使用单位来确定项目是否应该被包括在子集。例如，对于一个数组[A，B]：

 我的二进制列入集
-----------------------------
0 00 {}
1 01 {B}
2 10 {A}
3月11日{A，B}
 

我们可以使用位运算符在JS的与多达31项的阵列（其应该是足够了）。

 函数power（X，Y）{
    变种L = Math.pow（2，x.length），
        R =新的Array（L）;
    对于（VAR I = 0; I＆LT;升;我++）{
        VAR子= Y？ y.slice（0）：[];
        对于（VAR J = 0; J＆LT; x.length; J ++）
            //如果从右侧的第j个比特在i设定
            如果（I和Math.pow（2，j）条）// Math.pow（2，j）的=== 1所述;＆下;Ĵ
                sub.push（X [J]）;
         -  [R [i] =子;
    }
    返回ř;
}
 

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项目可以在阵列年，但反之不然，测试所有排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！