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

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

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

Для каждого базового набора, имеющего 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 2

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

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

Kinda как номера работают.

---

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

Это 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 с идентификатором «войти» в документе, и каким-то образом начать generateSets() метод, чтобы проверить выход.

Answer 3

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

---

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

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 4

Хороший ресурс для combination generation является алгоритм, описанный Кеннет Н. Розена в Discrete Mathematics and Its Applications. Многие проблемы могут использовать этот общий алгоритм, и хорошо иметь его в вашем наборе инструментов.