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!

Chagres

You're not really looking for all permutations, do you? Are you looking for the power set which you want to iterate? Or do you even need to solve some kind of knapsack problem? – Heyde

I understand what you mean by the knapsack problem, but I don't think my problem is that complicated. Excuse my terrible mathematical knowledge, but yes, a power set is something along the lines of what I'm trying to achieve, i.e. get all combinations of x in y. x[0,2] + y[5,6] = z[5,6],z[5,6,0],z[5,6,2],z[5,6,2,0],(not)!z[5,6,0,2] – Chagres

So get all possible subsets of y (as arrays, items in the same order as in y) and prepend each of them with x? That's simple :-) – Heyde

Hence, something along the lines of checking if the current sequence of indexes of array has already been used, as tested against a stored bit sequence. Maybe I am going off on a tangent here... – Chagres

I see what you mean, but doesn't that mean you will run into duplicate subsets, i.e. [x,y,z] is not the same as [y,x,z], but for all intents and purposes, I would only need the first, or the latter for that matter, but not both – Chagres

Yes, if we're looking at [x,y,z] and [y,x,z] in terms of sets (which have no order) they would be equal, and therefore the algorithm would only create one of them. – Heyde

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

Heyde