Выходной массив одновременно возможных уникальных комбинаций элементов

Я думаю, что для получения вывода требуется несколько функций.

а) Функция, которая говорит: при наличии необходимых компонентов (для предмета) существуют ли запасы для изготовления предмета?

// are required components (req) a subset of inventory (inv) ?
const canMakeItem = (req, inv) => req.every(r => inv.indexOf(r) > -1);

b) Функция «n select k» для возврата массива комбинаций элементов, которые следует рассматривать как «одновременно создаваемые». Я использовал вот этот:

// choose k items from array
const chooseCombos = (arr, k, prefix=[]) => {
  if (k == 0) return [prefix];
  return arr.flatMap((v, i) =>
    chooseCombos(arr.slice(i+1), k-1, [...prefix, v])
  );
}

В вашем примере вывода мы видим пары элементов, потому что это то, что позволяют примеры входных данных каталога элементов и списка компонентов. Учитывая больший каталог элементов и больший список компонентов, вывод будет больше, чем «пары» - я попытаюсь решить это позже в ответе. Использование функции «n select k» в конечном итоге позволит протестировать комбинации из 3, 4 и т. д. элементов из каталога.

c) Тестируется функция, которая может принимать разницу двух массивов (сохраняя дубликаты) для отслеживания оставшихся компонентов, поскольку набор элементов «одновременно создается». Я использовал вот этот:

// array difference with dupes
const remainingComponents = (a, b) => {
  return a.filter(function(v) {
    return !this.get(v) || !this.set(v, this.get(v) - 1);
  }, b.reduce( (acc, v) => acc.set(v, (acc.get(v) || 0) + 1), new Map() ));
}

г) Моя версия buildSimultaneousItems:

// eliminate combos (arrs[n]) with insufficient inventory (inv) for all items in combo
const createableCombos = (arrs, inv) => { 
  return arrs.filter(arr => {
    // we know arr[0] is possible so remove components
    let currentComponents = remainingComponents(myComponents, itemCatalog[arr[0]].components);
    // check subsequent array items
    for (let i=1; i<arr.length; i++) {
      let requiredComponents = itemCatalog[arr[i]].components;
      if (!canMakeItem(requiredComponents, currentComponents)) {
        // this combo cannot be made from available components
        return false
      } else {
        // remove components from inventory for this item
        currentComponents = remainingComponents(currentComponents, requiredComponents);
      }
    }
    // we can make all the items in this combo!
    return true;
  });
}

Начальная точка здесь, например.

[
  [violin, guitar],
  [guitar, trumpet],
  [violin, trumpet]
]

В том, что все элементы массива должны быть проверены, но не все возможны, например. струны, используемые на скрипке и недоступные для гитары. Функция chooseCombos должна устранять дубликаты, например. [trumpet, violin].

Для каждого массива предположим, что первый элемент можно создать, и удалите необходимые компоненты из инвентаря. Для остальных элементов повторите тест на возможность создания и удалите компоненты. Если в какой-то момент элемент не может быть создан, верните false для этого массива, и он будет отфильтрован из результата.

д) Собираем все вместе:

// eliminate single items not able to be made
// in the example all items can be created
let createableSingleItems = Object.keys(itemCatalog)
    .filter(k => canMakeItem(itemCatalog[k].components, myComponents) );

// candidate pairs - pairs is n choose _2_
let candidatePairs = chooseCombos(createableSingleItems, 2, []);
let createablePairs = createableCombos (candidatePairs, myComponents)

// candidate triples - n choose _3_
let candidateTriples = chooseCombos(createableSingleItems, 3, []);
let createableTriples = createableCombos (candidateTriples, myComponents);

Массив createableSingleItems в качестве начальной точки позже уменьшит избыточную обработку и позволит createableCombos «узнать», что arr[0] можно «создать».

Итак, выбираем пары из каталога предметов (где известно, что каждую пару можно создать отдельно):

// candidate pairs - pairs is n choose _2_
let candidatePairs = chooseCombos(createableSingleItems, 2, []);
let createablePairs = createableCombos (candidatePairs, myComponents)

Производит этот вывод:

[
    ["bramble_vest", "hextech_gunblade"],
    ["bramble_vest", "morellonomicon"],
    ["bramble_vest", "zekes_herald"],
    ["guardian_angel", "locket_of_the_iron_solari"],
    ["guardian_angel", "morellonomicon"],
    ["guardian_angel", "sunfire_cape"],
    ["hextech_gunblade", "sunfire_cape"],
    ["locket_of_the_iron_solari", "sunfire_cape"],
    ["locket_of_the_iron_solari", "zekes_herald"]
]

Для вывода named, например.

createablePairs.map(a => a.map(b => itemCatalog[b].name));

Дает:

[
    ["Bramble Vest", "Hextech Gunblade"],
    ["Bramble Vest", "Morellonomicon"],
    ["Bramble Vest", "Zeke's Herald"],
    ["Guardian Angel", "Locket of the Iron Solari"],
    ["Guardian Angel", "Morellonomicon"],
    ["Guardian Angel", "Sunfire Cape"],
    ["Hextech Gunblade", "Sunfire Cape"],
    ["Locket of the Iron Solari", "Sunfire Cape"],
    ["Locket of the Iron Solari", "Zeke's Herald"]
]

Выбор троек (n выберите 3) из каталога предметов дает [], потому что у нас недостаточно инвентаря...

Максимальный выбор для n choose k — k == n == max(catalog). Для очень большого каталога и очень большого запаса может потребоваться оптимизация для этого метода. Для очень большого каталога и относительно небольшого запаса может быть достаточно подготовительного шага createableSingleItems.

const itemCatalog = {
    "bramble_vest" : {
        "components" : [ "Chain Vest", "Chain Vest" ],
        "name" : "Bramble Vest"
    },
    "guardian_angel" : {
        "components" : [ "B.F. Sword", "Chain Vest" ],
        "name" : "Guardian Angel"
    },
    "hextech_gunblade" : {
        "components" : [ "B.F. Sword", "Needlessly Large Rod" ],
        "name" : "Hextech Gunblade"
    },
    "locket_of_the_iron_solari" : {
        "components" : [ "Chain Vest", "Needlessly Large Rod" ],
        "name" : "Locket of the Iron Solari"
    },
    "morellonomicon" : {
        "components" : [ "Giant's Belt", "Needlessly Large Rod" ],
        "name" : "Morellonomicon"
    },
    "sunfire_cape" : {
        "components" : [ "Chain Vest", "Giant's Belt" ],
        "name" : "Sunfire Cape"
    },
    "zekes_herald" : {
        "components" : [ "B.F. Sword", "Giant's Belt" ],
        "name" : "Zeke's Herald"
    }
}

let myComponents = [
    "B.F. Sword",
    "Chain Vest",
    "Giant's Belt",
    "Chain Vest",
    "Needlessly Large Rod"
]

// are required components (req) a subset of inventory (inv) ?
const canMakeItem = (req, inv) => req.every(r => inv.indexOf(r) > -1);

// https://stackoverflow.com/questions/64414816/can-you-return-n-choose-k-combinations-in-javascript-using-array-flatmap
// choose k items from array
const chooseCombos = (arr, k, prefix=[]) => {
  if (k == 0) return [prefix];
  return arr.flatMap((v, i) =>
    chooseCombos(arr.slice(i+1), k-1, [...prefix, v])
  );
}

// https://stackoverflow.com/questions/39810641/get-difference-between-two-arrays-including-duplicates
// array difference with dupes
const remainingComponents = (a, b) => {
  return a.filter(function(v) {
    return !this.get(v) || !this.set(v, this.get(v) - 1);
  }, b.reduce( (acc, v) => acc.set(v, (acc.get(v) || 0) + 1), new Map() ));
}

// eliminate combos (arrs[n]) with insufficient inventory (inv) for all items in combo
const createableCombos = (arrs, inv) => { 
  return arrs.filter(arr => {
    // we know arr[0] is possible so remove components
    let currentComponents = remainingComponents(myComponents, itemCatalog[arr[0]].components);
    // check subsequent array items
    for (let i=1; i<arr.length; i++) {
      let requiredComponents = itemCatalog[arr[i]].components;
      if (!canMakeItem(requiredComponents, currentComponents)) {
        // this combo cannot be made from available components
        return false
      } else {
        // remove components from inventory for this item
        currentComponents = remainingComponents(currentComponents, requiredComponents);
      }
    }
    // we can make all the items in this combo!
    return true;
  });
}

// eliminate single items not able to be made
// in the example all items can be created
let createableSingleItems = Object.keys(itemCatalog)
    .filter(k => canMakeItem(itemCatalog[k].components, myComponents) );

// candidate pairs - pairs is n choose _2_
let candidatePairs = chooseCombos(createableSingleItems, 2, []);
let createablePairs = createableCombos (candidatePairs, myComponents)

// candidate triples - n choose _3_
let candidateTriples = chooseCombos(createableSingleItems, 3, []);
let createableTriples = createableCombos (candidateTriples, myComponents);

// test 
console.info("Pairs:");
console.info(createablePairs );
console.info("Triples:");
console.info(createableTriples);

(Примечание: ниже приведена обновленная версия, отвечающая дополнительным требованиям.)

Вот еще один подход, основанный на простом рекурсивном алгоритме: мы смотрим на первый элемент в списке и, если мы можем это сделать, мы объединяем его с каждым из результатов, сформированных путем вызова функции с остатком целей и списком компонентов за вычетом тех, которые необходимы для изготовления этого предмета. Если мы не можем сделать первый элемент, мы просто повторяемся с остальными элементами и полным списком компонентов. Рекурсия достигает дна, когда список элементов пуст. Чтобы использовать это, мы сначала преобразуем ваш каталог в массив с помощью Object.values, так как нам вообще не нужны ваши ключи объектов.

Как только мы нашли наши коллекции, мы удаляем те, которые являются строгими подмножествами других. Это потому, что помимо полных значений, которые вы хотите, функция collect также собирает наборы, которые могут содержать другие. Например, с приведенными выше данными он собирает [["Bramble Vest", "Hextech Gunblade"], ["Bramble Vest", "Morellonomicon"], ["Bramble Vest", "Zeke's Herald"], ["Bramble Vest"], ...] (с еще дюжиной элементов, многие из которых содержат отдельные компоненты). Обратите внимание, что четвертый элемент, ["Bramble Vest"], является строгим подмножеством каждого из трех предыдущих. Используя maximize, мы удаляем такие подмножества из результата.

Эта разбивка полезна, потому что collect сам по себе выражает полезный алгоритм. (Реализация по-прежнему привязана к вашей структуре, используя свойства components и name каждого элемента, но нетрудно сделать ее более общей.) Этот алгоритм использует items, набор наборов компонентов, и components, набор компонентов и возвращает список всех возможных коллекций items, которые могут быть созданы с этим фиксированным списком компонентов. Наложение maximize поверх этого дает нам и вашу цель, и этот несколько более общий алгоритм вместе. Это также более простой алгоритм, насколько я могу судить. Возможно, кто-нибудь может показать мне упрощение, которое делает эти два шага за один.

Вот реализация:

// utility functions
const dropFirst = (x, xs, i = xs .indexOf (x)) =>
  i < 0 ? [... xs] : [... xs .slice (0, i), ... xs .slice (i + 1)]

const dropEach = ([x, ...xs], ys) => 
  x == undefined ? ys : dropEach (xs, dropFirst (x, ys))

const canMake = ([c, ...cs], comps) => 
  c == undefined ? true : comps .includes (c) ? canMake (cs, dropFirst (c, comps)) : false

const isSubset = (xs, ys) =>
  xs .every (x => ys .includes (x))

const maximize = (xs) => 
  xs .filter (x => ! (xs .some (y => x !== y && isSubset (x, y))))


// main function
const collect = ([x, ...xs], ys) => 
  x == undefined
    ? [[]]
  : canMake (x.components, ys)
    ? [
        ... collect (xs, dropEach (x .components, ys)) .map (coll => [x .name, ... coll]), 
        ... collect (xs, ys)
      ]
    : collect (xs, ys)


// public function
const simultaneousItems = (catalog, components) => 
  maximize (collect (Object.values(catalog), components))


// sample data
const itemCatalog = { bramble_vest: {components : [ "Chain Vest", "Chain Vest" ], name : "Bramble Vest"}, guardian_angel: {components : [ "B.F. Sword", "Chain Vest" ], name : "Guardian Angel"}, hextech_gunblade: {components : [ "B.F. Sword", "Needlessly Large Rod" ], name : "Hextech Gunblade"}, locket_of_the_iron_solari: {components : [ "Chain Vest", "Needlessly Large Rod" ], name : "Locket of the Iron Solari"}, morellonomicon: {components : [ "Giant's Belt", "Needlessly Large Rod" ], name : "Morellonomicon"}, sunfire_cape: {components : [ "Chain Vest", "Giant's Belt" ], name : "Sunfire Cape"}, zekes_herald: {components : [ "B.F. Sword", "Giant's Belt" ], name : "Zeke's Herald"}}

const myComponents = ["B.F. Sword", "Chain Vest", "Giant's Belt", "Chain Vest", "Needlessly Large Rod"]


// demo
console .log (
  simultaneousItems(itemCatalog, myComponents)
)

.as-console-wrapper {max-height: 100% !important; top: 0}

Начнем с набора служебных функций:

• dropFirst удаляет первое вхождение значения в массиве значений. Например,

  //                          v------------ First 'bar'
  dropFirst ('bar', ['foo', 'bar', 'baz', 'qux', 'bar', 'bar', 'corge']) 
  //=> ["foo", "baz", "qux", "bar", "bar", "corge"]
  //          ^---------------------------- now missing
  

• dropEvery расширяет это, чтобы удалить каждое из списка значений из основного списка, используя dropFirst. Например

  //   will all be removed -----------v------v--------------------v              
  dropEach (['bar', 'foo', 'bar'], ['foo', 'bar', 'baz', 'qux', 'bar', 'bar', 'corge']) 
  //=> ["baz", "qux", "bar", "corge"]
  

• canMake сообщает, можем ли мы составить список компонентов, учитывая имеющиеся компоненты. Например, используя примерный список компонентов,

  canMake (['B.F. Sword', 'Chain Vest']) (myComponents) //=> true
  canMake (['B.F. Sword', 'Chain Vest', 'B.F. Sword']) (myComponents) //=> false
  

  Первый работает, потому что в наших компонентах есть и меч, и жилет. Второй терпит неудачу, потому что у нас есть только один меч.

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

(Примечание: эти первые три функции могли бы быть намного проще, если бы мы реализовали тип MultiSet/Bag как для компонентов предметов, так и для нашего общего списка компонентов. Я не буду пробовать это здесь, но, возможно, это стоит изучить.)

• isSubset просто сообщает, является ли один массив строк подмножеством другого. Здесь мы не заботимся о множественности, так как наши выходные данные не включают много копий любого из наших элементов.

• maximize обсуждалось выше. Он удаляет из списка коллекций те, которые являются подмножествами других в списке.

Затем у нас есть наша центральная функция,

• collect, который определяет, какие подмножества нашего списка предметов можно сделать с помощью наших компонентов. Алгоритм описан выше.

И наша публичная функция-обертка,

• simultaneousItems, который вызывает Object.values на вашем входе, чтобы преобразовать его в полезный формат для collect, передает это и список компонентов в collect, а затем вызывает maximize по результатам. Эта функция дает ввод, который, я думаю, вам нужен.

Это вывод из предоставленных данных:

[
  ["Bramble Vest", "Hextech Gunblade"],
  ["Bramble Vest", "Morellonomicon"],
  ["Bramble Vest", "Zeke's Herald"],
  ["Guardian Angel", "Locket of the Iron Solari"],
  ["Guardian Angel", "Morellonomicon"],
  ["Guardian Angel", "Sunfire Cape"],
  ["Hextech Gunblade", "Sunfire Cape"],
  ["Locket of the Iron Solari", "Sunfire Cape"], 
  ["Locket of the Iron Solari", "Zeke's Herald"]
]

Если мы добавим второй «B.F. Sword» в наш список компонентов, мы получим этот список:

[
  ["Bramble Vest", "Hextech Gunblade", "Zeke's Herald"],
  ["Bramble Vest", "Morellonomicon"],
  ["Guardian Angel", "Hextech Gunblade", "Sunfire Cape"],
  ["Guardian Angel", "Locket of the Iron Solari", "Zeke's Herald"],
  ["Guardian Angel", "Morellonomicon"],
  ["Locket of the Iron Solari", "Sunfire Cape"]
]

Было бы интересно превратить collect в более общую функцию, которую было бы легко использовать для определения makeSimultaneous. Я также не удивлюсь, если эта общая проблема будет хорошо известной проблемой с некоторыми оптимизированными алгоритмами для нее. Мне также было бы любопытно узнать об алгоритмической производительности. Но все это в другой день.

Также есть разумный аргумент в пользу превращения вашего вывода в набор наборов, а не в массив массивов. Порядок массивов не имеет значения, и в любом случае Set является более логичной структурой данных. Я, вероятно, не стал бы этого делать, как бы это ни было логично, поскольку мне все еще легче работать с массивами. Но это стоит учитывать.

Обновлять

В комментарии от OP описано дополнительное требование, которое не соответствует вышеизложенному: предметы, которые мы собираем, могут встречаться несколько раз. Это может быть понятно тому, кто знаком с рассматриваемой игрой, но приведенный выше код не справляется с этим.

Более того, это не простое решение. Дизайн collect выше заключался в том, чтобы выбрать, собирать ли первый предоставленный предмет (если возможно) или нет, а затем повторять оставшиеся предметы и компоненты, оставшиеся после использования необходимых для предмета. Я не видел простого способа изменить это, чтобы разрешить несколько копий.

Итак, вот переписывание collect со смесью существующих вспомогательных функций и новых для его поддержки:

// utility functions
const dropFirst = (x, xs, i = xs .indexOf (x)) =>
  i < 0 ? [... xs] : [... xs .slice (0, i), ... xs .slice (i + 1)]

const dropEach = ([x, ...xs], ys) => 
  x == undefined ? ys : dropEach (xs, dropFirst (x, ys))

const dropEachRepeatedly = (n, xs, ys) =>
  n == 0 ? ys : dropEach(xs, dropEachRepeatedly(n - 1, xs, ys))

const canMake = ([c, ...cs], comps) => 
  c == undefined ? true : comps .includes (c) ? canMake (cs, dropFirst (c, comps)) : false

const howMany = (xs, ys) => 
  canMake (xs, ys)
    ? 1 + howMany (xs, dropEach(xs, ys))
    : 0

const range = (lo, hi) => Array .from ({length: hi - lo + 1}, (_, i) => i + lo)

const count = (xs) => 
  xs .reduce ((a, x) => ((a[x] = (a[x] || 0) + 1), a), {})

const isMultiSubset = (xs, ys, cx = count (xs), cy = count (ys)) =>
  Object .keys (cx) .every (x => cx [x] <= (cy [x] || 0))

const maximize = (xs) => 
  xs .filter (x => ! (xs .some (y => x !== y && isMultiSubset (x, y))))


// main function
const collect = ([x, ...xs], ys) => 
  x == undefined
    ? [[]]
    : range (0, howMany (x.components, ys)) .reverse() .flatMap(
        (n) => collect(xs, dropEachRepeatedly(n, x.components, ys)) .map (
          coll =>  [...Array(n).fill(x.name), ...coll]
        )
      )


// public function
const simultaneousItems = (catalog, components) => 
  maximize (collect (Object .values (catalog), components))


// sample data
const itemCatalog = { bramble_vest: {components : [ "Chain Vest", "Chain Vest" ], name : "Bramble Vest"}, guardian_angel: {components : [ "B.F. Sword", "Chain Vest" ], name : "Guardian Angel"}, hextech_gunblade: {components : [ "B.F. Sword", "Needlessly Large Rod" ], name : "Hextech Gunblade"}, locket_of_the_iron_solari: {components : [ "Chain Vest", "Needlessly Large Rod" ], name : "Locket of the Iron Solari"}, morellonomicon: {components : [ "Giant's Belt", "Needlessly Large Rod" ], name : "Morellonomicon"}, sunfire_cape: {components : [ "Chain Vest", "Giant's Belt" ], name : "Sunfire Cape"}, zekes_herald: {components : [ "B.F. Sword", "Giant's Belt" ], name : "Zeke's Herald"}}

// const myComponents = ["B.F. Sword", "Chain Vest", "Giant's Belt", "Chain Vest", "Needlessly Large Rod"]
const myComponents = ["B.F. Sword", "Chain Vest", "Giant's Belt", "Chain Vest", "Chain Vest", "Needlessly Large Rod", "Chain Vest"]


// demo
console .log (
  simultaneousItems (itemCatalog, myComponents)
)

.as-console-wrapper {max-height: 100% !important; top: 0}

Добавив в наши компоненты еще два «Кольчуги», мы получили следующий результат:

[
    ["Bramble Vest", "Bramble Vest", "Hextech Gunblade"],
    ["Bramble Vest", "Bramble Vest", "Morellonomicon"],
    ["Bramble Vest", "Bramble Vest", "Zeke's Herald"],
    ["Bramble Vest", "Guardian Angel", "Locket of the Iron Solari"],
    ["Bramble Vest", "Guardian Angel", "Morellonomicon"],
    ["Bramble Vest", "Guardian Angel", "Sunfire Cape"],
    ["Bramble Vest", "Hextech Gunblade", "Sunfire Cape"],
    ["Bramble Vest", "Locket of the Iron Solari", "Sunfire Cape"],
    ["Bramble Vest", "Locket of the Iron Solari", "Zeke's Herald"],
    ["Guardian Angel", "Locket of the Iron Solari", "Sunfire Cape"]
]

Как и прежде, collect является нашей основной функцией, а simultaneousItems представляет собой простую оболочку, которая массирует ввод перед вызовом collect, а затем запускает maximize результат.

Многие из вспомогательных функций одинаковы. Изменилось только maximize. Теперь он зависит от isMultiSubset вместо isSubset (который нам больше не нужен). Но у нас также есть несколько дополнительных помощников:

• dropEachRepeatedly удаляет несколько копий одного списка (здесь компоненты предмета) из другого (наши доступные компоненты)

• howMany сообщает, сколько копий одного списка можно сделать из членов другого

• range просто генерирует диапазон целых чисел. Например

  range (3, 12) //=> [3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
  

• count подсчитывает количество вхождений каждого значения в списке. Например

  count (['a', 'b', 'a', 'c', 'b', 'd', 'b'])
  //=> {a: 2, b: 3, c: 1, d: 1}
  

• isMultiSubset сообщает, является ли одно мультимножество (здесь выражено в виде массива, но порядок не имеет значения) подмножеством другого. Например, ['a' , 'b' , 'a'] не является множественным подмножеством ['a', 'b', 'c', 'd'], поскольку в первом есть два 'a', а во втором — только один. Но это множественное подмножество ['a', 'b', 'c', 'a'], так как 'a's и 'b' достаточно, чтобы их можно было использовать. Поскольку теперь мы допускаем наличие нескольких копий компонентов в каждой выходной конфигурации, нам необходимо использовать это при максимизации.

Наша основная функция collect теперь работает следующим образом: если у нас нет элементов на входе, мы возвращаем массив, содержащий только пустой массив. Если мы это делаем, мы фокусируемся на первом компоненте, подсчитываем, сколько раз он вписывается в наш список компонентов, затем для каждого значения от этого числа до нуля мы выбираем включение такого количества копий элемента и повторяемся для оставшихся. элементы и компоненты, уменьшенные на это количество копий списка компонентов элемента. Мы просто возвращаем сглаженную версию этого результата.

Вполне вероятно, что этот код можно упростить. Я начал с того, что у нас уже было, и изменил оттуда. Часто это не приводит к таким хорошим результатам, как если бы мы планировали это с самого начала. Но часто у нас нет такой роскоши.

принятие желаемого за действительное

Ваш вопрос привлек мое внимание, и я начал решать его с помощью одного из моих любимых приемов программирования. Принятие желаемого за действительное — это способ программирования, при котором вы пишете свою программу и желаете, чтобы она была правдой.

const result =
  make
    ( Object.values(itemCatalog)
    , myComponents
    )

console.info(result)
// ...

Выше я хотел бы вызвать make с items сделать и доступным components. Загаданное желание - это желание, исполненное... тобой! -

const make = (items, components, i = 0, r = []) =>
  i >= items.length
    ? [ r ]
    : make1
        ( items[i]
        , components
        , (remainder, item) =>
            make
              ( drop(items, i)
              , remainder
              , 0
              , [ ...r, item ]
              )
        , _ => []
        )
        .concat(make(items, components, i + 1, r))

По пути мы загадываем больше желаний. Сложность создания набора предметов make отличается от сложности создания одного предмета make1. Желание исполнено -

const make1 = (item, components, ifTrue, ifFalse) =>
  pick
    ( components
    , item.components
    , (remainder, _) => ifTrue(remainder, item.name)
    , ifFalse
    )

Стань жадным сейчас. Пока мы на этом, я бы хотел pick элементы из массива. Желание исполнено -

const pick = (t1, t2, ifTrue, ifFalse, i = 0) =>
  i >= t2.length
    ? ifTrue(t1, t2)
    : pick1
        ( t1
        , t2[i]
        , (r, _) =>
            pick(r, t2, ifTrue, ifFalse, i + 1)
        , ifFalse 
        )

Проси метр, возьми парсек. О, вам нужно выбрать один элемент из массива? Желание исполнено pick1 -

const pick1 = (t, q, ifTrue, ifFalse) =>
  search
    ( t
    , v => v === q
    , (v, i) => ifTrue(drop(t, i), v) 
    , ifFalse
    )

Ты не один из тех хромых джиннов, которые ограничиваются исполнением трех желаний. Если бы я только мог search массив... Желание исполнено! -

const search = (t, f, ifTrue, ifFalse, i = 0) =>
  i >= t.length
  ? ifFalse()
  : Boolean(f(t[i]))
    ? ifTrue(t[i], i)
    : search(t, f, ifTrue, ifFalse, i + 1)

Исполняет желания на дни -

const drop = (t, i, n = 1) =>
  t.slice(0, i).concat(t.slice(i + n))

Когда желания заканчиваются и желания исполняются, ваша программа завершена. Как по волшебству -

// output

[ [ 'Bramble Vest', 'Hextech Gunblade' ]
, [ 'Bramble Vest', 'Morellonomicon' ]
, [ 'Bramble Vest', "Zeke's Herald" ]
, [ 'Bramble Vest' ]
, [ 'Guardian Angel', 'Locket of the Iron Solari' ]
, [ 'Guardian Angel', 'Morellonomicon' ]
, [ 'Guardian Angel', 'Sunfire Cape' ]
, [ 'Guardian Angel' ]
, [ 'Hextech Gunblade', 'Bramble Vest' ]
, [ 'Hextech Gunblade', 'Sunfire Cape' ]
, [ 'Hextech Gunblade' ]
, [ 'Locket of the Iron Solari', 'Guardian Angel' ]
, [ 'Locket of the Iron Solari', 'Sunfire Cape' ]
, [ 'Locket of the Iron Solari', "Zeke's Herald" ]
, [ 'Locket of the Iron Solari' ]
, [ 'Morellonomicon', 'Bramble Vest' ]
, [ 'Morellonomicon', 'Guardian Angel' ]
, [ 'Morellonomicon' ]
, [ 'Sunfire Cape', 'Guardian Angel' ]
, [ 'Sunfire Cape', 'Hextech Gunblade' ]
, [ 'Sunfire Cape', 'Locket of the Iron Solari' ]
, [ 'Sunfire Cape' ]
, [ "Zeke's Herald", 'Bramble Vest' ]
, [ "Zeke's Herald", 'Locket of the Iron Solari' ]
, [ "Zeke's Herald" ]
, []
]

Вывод для make здесь показывает все возможные варианты покупки. Написание максимальных подмножеств — настоящая головная боль. Сейчас я собираюсь изучить записи Скотта...

писать модули

Организация кода — важное гигиеническое упражнение. Объединение функций в модули способствует повторному использованию кода и дает нам управляемый барьер абстракции.

Многие из написанных нами функций являются универсальными и могут использоваться для любого массива. Давайте поместим их в модуль под названием arr -

// arr.js

const drop = (t, i, n = 1) =>
  t.slice(0, i).concat(t.slice(i + n))

const pick1 = (t, q, ifTrue, ifFalse) =>
  search
    ( t
    , v => v === q
    , (v, i) => ifTrue(drop(t, i), v) 
    , ifFalse
    )

const pick = (t1, t2, ifTrue, ifFalse, i = 0) =>
  i >= t2.length
    ? ifTrue(t1, t2)
    : pick1
        ( t1
        , t2[i]
        , (r, _) =>
            pick(r, t2, ifTrue, ifFalse, i + 1)
        , ifFalse 
        )

const search = (t, f, ifTrue, ifFalse, i = 0) =>
  i >= t.length
  ? ifFalse()
  : Boolean(f(t[i]))
    ? ifTrue(t[i], i)
    : search(t, f, ifTrue, ifFalse, i + 1)

export { drop, pick, pick1, search }

Мы объединим функции создания предметов в модуль под названием craft. Обратите внимание, как этот модуль может зависеть от функций, предоставляемых другим модулем.

// craft.js

import { drop, pick } from "./arr.js"

const make1 = (item, components, ifTrue, ifFalse) =>
  arr.pick
    ( components
    , item.components
    , (remainder, _) => ifTrue(remainder, item.name)
    , ifFalse
    )

const make = (items, components, i = 0, r = []) =>
  i >= items.length
    ? [ r ]
    : make1
        ( items[i]
        , components
        , (remainder, item) =>
            make
              ( arr.drop(items, i)
              , remainder
              , 0
              , [ ...r, item ]
              )
        , _ => []
        )
        .concat(make(items, components, i + 1, r))

export { make, make1 }

Наконец напишите свой модуль main -

// main.js

import { make } from "./craft.js"

const itemCatalog = ...

const myComponents = ...

const result =
  make
    ( Object.values(itemCatalog)
    , myComponents
    )

console.info(result)
// ...