Calculate all combinations of a series

Question

I have a list of items, and each item has a quantity.

var items = {
    1: 12,   // we have 12 x item1
    2: 1,    // we have 1 x item2
    3: 1,
    4: 7,
    5: 2,
    6: 2
};

Alternatively this could be viewed as:

var items = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
             2, 3, 4, 4, 4, 4, 4, 4, 4, 5, 5, 6, 6];

How would you go about obtaining a list of every combination of these items, keeping in mind that the order is entirely unimportant (and hence [1,2,3] == [3,2,1]), and that not every item has to exist in the result.

I suppose the output could look like this:

[1]
[1, 1]
[1, 2]
[1, 3]
...

or, even better:

{1 : 1}          // 1 x item1
{1 : 2}          // 2 x item1 
{1 : 1, 2 : 1}   // 1 x item1, 1 x item2
{1 : 1, 3 : 1}
....

Answer 1

Just make the normal combinations.

For each basic set that has n numbers with a quantity greater than 1, loop through all quantities: [5,6] -> [5,5,6], [5,6,6], [5,5,6,6].

[]
[1] -> [1,1], [1,1,1] etc
  [1,2] -> [1,1,2], ...
  [1,3] -> [1,1,3]
  [1,4] -> [1,1,4], ...., [1,4,4], -- all combinations of all multi quantity
[2]
[3]
[4] -> [4,4], [4,4,4] etc
[5] -> [5,5]
[6] -> [6,6]

Etc...

Another method (pseudocode):

Combinations: {N -> N} -> [[N]]
Combinations(s) == CombinationsX(s, [])

CombinationsX: {N -> N} X [N] -> [[N]]
Combinationsx(s, g) ==
  if s = {} then return []
  else
    {a -> b} = hd s
    ts = tl s
    res = Combinationsx(ts, g) 
    for q in 1..b do
      g = g + [a]
      res = res ++ Combinationsx(ts, g)
    return res

Answer 2

I assume that quantity of each item is limited.

I'd go with incremental here: Start with empty and add item 1 while possible. When done, remove all 1s and add a 2 and start adding ones again. When ones reach capacity, remove them all, add another 2 and start again. When 2s reach capacity, remove them and add a 3. And so on...

Kinda like numbers work.

---

Ok, let's try to code... Hash with incrementing integer keys is an array ;-) It's easier to assume that first element of the array is the right digit of out 'floating radix' number.

This is javaScript:

var limits = [1, 3, 5, 2];

function out(arr){
  var text = '';
  for (var i=0; i < arr.length; i++){
    text += arr[i] + '.'
  }
  var log = document.getElementById('log');
  var p = document.createElement('p');
  log.appendChild(p);
  p.innerHTML = '<span>' + text + '</span>';
}

function generateNextSet(set){
  for (var i = 0; i < set.length; i++){
    var amount = set[i];
    if (amount + 1 > limits[i]){
      set[i] = 0;
    } else {
      set[i] = amount + 1;
      return set;
    }
  }
  return false;
}

function generateSets(){
  var initial_set = [0, 0, 0, 0]
  var set = generateNextSet(initial_set);
  out(set);
  while (set = generateNextSet(set)) {
    out(set);
  }
};

Add a div with id 'log' to the document and somehow start the generateSets() method to check out the output.

Answer 3

Update: After posting this answer, I noticed that an existing answer had the same approach, but I'll still keep mine around since it's more verbose and even has working code :)

---

If you only had one instance of each item in the original item pool, and your items represented binary digits;

var items {
    1 : 1,
    2 : 1,
    4 : 1,
    8 : 1,
    16: 1,
    32: 1
};

The problem would be simplified to generating a sequence of all numbers that can be represented by these digits:

• 0 ([ ] - no items)
• 1 ([ 1 ])
• 2 ([ 2 ])
• 3 ([ 2, 1 ])
• 4 ([ 4 ])
• etc.

So, your problem can be viewed as simply asking for the sequence of numbers that can be represented by -- not binary -- but a mixed-radix numeral system.

Which means, you could write a counter for this weird numbering system to iterate through values 0 and MAX. So, you'd start with incrementing the least significant digit and carry over to the more significant digit when you've exhausted all the possible values that digit can take.

var items = {
    1: 12,   // we have 12 x item1
    2: 1,    // we have 1 x item2
    3: 1,
    4: 7,
    5: 2,
    6: 2
};

var counter = {
    1: 0,
    2: 0,
    3: 0,
    4: 0,
    5: 0,
    6: 0
};

function increment(digit) {
    if (digit > 6) {
        return false;
    }

    var value = counter[digit] + 1;

    if (value > items[digit]) {
        counter[digit] = 0;
        return increment(digit + 1);
    }

    counter[digit] = value;

    return true;
}

while (increment(1)) {
    var set = [];

    for (var digit in counter) {
        var value = counter[digit];

        for (var i = 0; i < value; i++) {
            set.push(digit);
        }
    }

    document.write("<div>" + set + "</div>");
}

The output looks something like this:

1
1,1
1,1,1

---- snip ----

2
1,2
1,1,2

---- big snip ----

1,1,1,1,1,1,1,1,2,3,4,4,4,4,4,4,4,5,5,6,6
1,1,1,1,1,1,1,1,1,2,3,4,4,4,4,4,4,4,5,5,6,6
1,1,1,1,1,1,1,1,1,1,2,3,4,4,4,4,4,4,4,5,5,6,6
1,1,1,1,1,1,1,1,1,1,1,2,3,4,4,4,4,4,4,4,5,5,6,6
1,1,1,1,1,1,1,1,1,1,1,1,2,3,4,4,4,4,4,4,4,5,5,6,6

Answer 4

A good resource for combination generation is the algorithm described by Kenneth H. Rosen in Discrete Mathematics and Its Applications. Many problems can make use of this general algorithm and it's good to have it in your toolbox.