Рассчитать все комбинации серии

Question

У меня есть список предметов, и у каждого предмета есть количество.

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

Как бы вы поступили, получив список каждой комбинации этих предметов, имея в виду, что порядок совершенно не важен (и, следовательно, [1,2,3] == [3,2,1]), и что в результате не должен существовать каждый предмет.

Я полагаю, что результат может выглядеть следующим образом:

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

или, еще лучше:

{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

Я предполагаю, что количество каждого предмета ограничено.

Я бы пошел с инкрементом здесь: Начните с пустого и добавьте элемент 1, пока это возможно. Когда закончите, удалите все 1 и добавьте 2 и начните добавлять снова. Когда один из них достигнет полной емкости, удалите их все, добавьте еще 2 и начните снова. Когда 2s достигнут емкости, удалите их и добавьте 3. И так далее ...

Вроде как числа работают.

---

Хорошо, давайте попробуем закодировать ... Хэш с инкрементными целочисленными ключами - это массив ;-) Проще предположить, что первым элементом массива является правильная цифра из числа «плавающих осей».

Это 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);
  }
};

Добавьте в документ div с идентификатором 'log' и каким-то образом запустите метод generateSets () , чтобы проверить вывод.

Answer 2

Обновление: После публикации этого ответа я заметил, что у существующего ответа был такой же подход, но я все равно буду придерживаться моего, поскольку он более многословен и даже имеет рабочий код :)

---

Если у вас был только один экземпляр каждого элемента в исходном пуле элементов, и ваши элементы представляли двоичные цифры;

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

Задача будет упрощена до генерации последовательности всех чисел, которые могут быть представлены этими цифрами:

• 0 ([] - нет записей)
• 1 ([1])
• 2 ([2])
• 3 ([2, 1])
• 4 ([4])
• и т.д.

Итак, ваша проблема может рассматриваться как простой запрос последовательности чисел, которая может быть представлена ​​- не двоичной - но mixed-radix система счисления.

Это означает, что вы можете написать счетчик для этой странной системы нумерации, чтобы перебирать значения 0 и MAX. Таким образом, вы начинаете с увеличения наименьшей значащей цифры и переходите к более значимой цифре, когда исчерпали все возможные значения, которые может принимать эта цифра.

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

Вывод выглядит примерно так:

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 3

Просто составьте нормальные комбинации.

Для каждого базового набора, который имеет n чисел с количеством больше 1, выполните цикл по всем величинам: [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 ...

Другой метод (псевдокод):

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 4

Хорошим ресурсом для генерации комбинации является алгоритм, описанный Кеннетом Розеном в Дискретная математика и ее приложения . Многие проблемы могут использовать этот общий алгоритм, и хорошо иметь его в своем наборе инструментов.