javascript - Two arrays, where items in array x can be in array y but not vice versa, test all permutations

Question

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!

Answer 1

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