Output Array Of Simultaneously Possible Unique Element Combinations
Solution 1:
(Note: there is an updated version below handling an additional requirement.)
Here's another approach, based on a simple recursive algorithm: We look at the first item in the list and if we can make it, we combine it with each of the results formed by calling the function with the remainder of the targets and the list of components less the ones required to make this item. If we can't make the first item, we just recur with the remainder of the items and the full list of components. The recursion bottoms out when the list of items is empty. To use this, we first convert your catalog to an array with Object.values, since we don't need your object keys at all.
Once we've found our collections, we remove those that are strict subsets of another. That is because as well as the full values you want, the collect function also gathers sets that could still contain others. With your above data, for instance, it collects [["Bramble Vest", "Hextech Gunblade"], ["Bramble Vest", "Morellonomicon"], ["Bramble Vest", "Zeke's Herald"], ["Bramble Vest"], ...] (with a dozen more items, many containing single components.) Note that the fourth item, ["Bramble Vest"], is a strict subset of each of the three earlier ones. Using maximize, we remove such subsets from the result.
This breakdown is useful because collect expresses a useful algorithm on its own. (The implementation is still tied to your structure, using the components and name properties of each item, but it would not be difficult to make more generic.) That algorithm takes items, a collection of collections of components, and components, a collection of components, and returns a list of all possible collections of items that could be made with that fixed list of components. Layering maximize atop this gives us both your goal and this somewhat more general algorithm together. It's also a simpler algorithm, as far as I can tell. Perhaps someone can show me a simplification that does these two steps in one.
Here's an implementation:
// utility functionsconstdropFirst = (x, xs, i = xs .indexOf (x)) =>
i < 0 ? [... xs] : [... xs .slice (0, i), ... xs .slice (i + 1)]
constdropEach = ([x, ...xs], ys) =>
x == undefined ? ys : dropEach (xs, dropFirst (x, ys))
constcanMake = ([c, ...cs], comps) =>
c == undefined ? true : comps .includes (c) ? canMake (cs, dropFirst (c, comps)) : falseconstisSubset = (xs, ys) =>
xs .every (x => ys .includes (x))
constmaximize = (xs) =>
xs .filter (x => ! (xs .some (y => x !== y && isSubset (x, y))))
// main functionconstcollect = ([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 functionconstsimultaneousItems = (catalog, components) =>
maximize (collect (Object.values(catalog), components))
// sample dataconst 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"]
// democonsole .log (
simultaneousItems(itemCatalog, myComponents)
).as-console-wrapper {max-height: 100%!important; top: 0}We start with a collection of utility functions:
dropFirstremoves the first occurrence of a value in an array of values. For instance,// v------------ First 'bar' dropFirst ('bar', ['foo', 'bar', 'baz', 'qux', 'bar', 'bar', 'corge']) //=> ["foo", "baz", "qux", "bar", "bar", "corge"]// ^---------------------------- now missingdropEveryextends this to remove each of a list of values from the main list, usingdropFirst. For instance// will all be removed -----------v------v--------------------v dropEach (['bar', 'foo', 'bar'], ['foo', 'bar', 'baz', 'qux', 'bar', 'bar', 'corge']) //=> ["baz", "qux", "bar", "corge"]canMakereports whether we can make a list of components given the components at hand. For instance, using your sample list of components,canMake (['B.F. Sword', 'Chain Vest']) (myComponents) //=> true canMake (['B.F. Sword', 'Chain Vest', 'B.F. Sword']) (myComponents) //=> falseThe first works because we have both the sword and the vest in our components. The second fails because we have only one sword.
There are numerous other techniques we could use to write this function. The recursive version fit with the rest of these functions, but we could also have compared counts of the relevant strings between the item's components and our available components.
(Note: these first three functions might have been much easier if we implemented a MultiSet/Bag type for both the items' components and our overall list of components. I won't try that here, but it might be worth investigating.)
isSubsetsimply reports if one array of strings is a subset of another. Here we don't care about multiplicities, as our outputs don't include many copies of any one of our items.maximizeis discussed above. It removes from a list of collections those that are subsets of another in the list.
Then we have our central function,
collect, which determines which subsets of our list of items can be made with our components. The algorithm is described above.
And our public wrapper function,
simultaneousItems, which callsObject.valueson your input to put it into a useful format forcollect, passes that and the list of components tocollect, and then callsmaximizeon the results. This function yields the input I think you want.
This is the output from the data supplied:
[
["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"]
]
If we add a second "B.F. Sword" to our list of components, we get this list:
[
["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"]
]
It would be an interesting exercise to turn collect into a more generic function that was still easy to use to define makeSimultaneous. I would also not be surprised if that generic problem was a well-known problem with some optimized algorithms for it. I'd be curious about the algorithmic performance as well. But all that's for another day.
There is also a reasonable argument to be made for turning your output into a Set of Sets rather than an array of arrays. The ordering of the arrays is irrelevant, and in any such case, a Set is a more logical data structure. I probably wouldn't do this, as logical as it is, as I still find arrays easier to work with. But it's worth considering.
Update
A comment from the OP described an additional requirement not met by the above: The items we collect can occur multiple times. This might be clear to someone who knows the underlying game in question, but the code above doesn't handle it.
Moreover, it's not a simple fix. The design of collect above was to choose whether to gather the first item supplied (if possible) or not, and then recur on the remaining items and the components left after using up the necessary ones for the item. I saw no simple way to change that to allow multiple copies.
So here is a rewrite of collect with a mixture of existing helper functions and new ones to support it:
// utility functionsconstdropFirst = (x, xs, i = xs .indexOf (x)) =>
i < 0 ? [... xs] : [... xs .slice (0, i), ... xs .slice (i + 1)]
constdropEach = ([x, ...xs], ys) =>
x == undefined ? ys : dropEach (xs, dropFirst (x, ys))
constdropEachRepeatedly = (n, xs, ys) =>
n == 0 ? ys : dropEach(xs, dropEachRepeatedly(n - 1, xs, ys))
constcanMake = ([c, ...cs], comps) =>
c == undefined ? true : comps .includes (c) ? canMake (cs, dropFirst (c, comps)) : falseconsthowMany = (xs, ys) =>
canMake (xs, ys)
? 1 + howMany (xs, dropEach(xs, ys))
: 0constrange = (lo, hi) => Array .from ({length: hi - lo + 1}, (_, i) => i + lo)
constcount = (xs) =>
xs .reduce ((a, x) => ((a[x] = (a[x] || 0) + 1), a), {})
constisMultiSubset = (xs, ys, cx = count (xs), cy = count (ys)) =>
Object .keys (cx) .every (x => cx [x] <= (cy [x] || 0))
constmaximize = (xs) =>
xs .filter (x => ! (xs .some (y => x !== y && isMultiSubset (x, y))))
// main functionconstcollect = ([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 functionconstsimultaneousItems = (catalog, components) =>
maximize (collect (Object .values (catalog), components))
// sample dataconst 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"]
// democonsole .log (
simultaneousItems (itemCatalog, myComponents)
).as-console-wrapper {max-height: 100%!important; top: 0}Adding two more "Chain Vest"s into our components, we now get this result:
[
["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"]
]
As before, collect is our main function, with simultaneousItems being a simple wrapper that massages the input before calling collect and then running maximize on the result.
Many of the helper functions are the same. Only maximize changed. It now depends on isMultiSubset instead of isSubset (which we no longer need.) But we also have some additional helpers:
dropEachRepeatedlydrops multiple copies of one list (here the item's components) from another (our available components)howManyreports how many copies of one list can be made from the members of anotherrangesimply generates a range of integers. For examplerange (3, 12) //=> [3, 4, 5, 6, 7, 8, 9, 10, 11, 12]countcounts the occurrences of each value in a list. For examplecount (['a', 'b', 'a', 'c', 'b', 'd', 'b']) //=> {a: 2, b: 3, c: 1, d: 1}isMultiSubsetreports whether one multiset (here expressed as an array, but order doesn't matter) is a subset of another one. For example,['a' , 'b' , 'a']is not a multi-subset of['a', 'b', 'c', 'd']since there are two'a's in the first and only one in the second. But it is a multi-subset of['a', 'b', 'c', 'a']since there are enough'a's and'b'to go around. Because we now allow for multiple copies of components in each output configuration, we need to use this when we do our maximizing.
Our main function, collect now works like this: If we have no items in our input, we return an array containing only the empty array. If we do, we focus on the first component, count how many times it fits in our list of components, then for each value from that number down to zero, we choose to include that many copies of the item, and recur on the remaining items and the components reduced by that many copies of item's component list. We just return a flattened version of this result.
It's quite likely that this code can be simplified. I started from what we already had and altered from there. Often that does not lead to results as good as when we plan it from the start. But many times we don't have that luxury.
Solution 2:
wishful thinking
Your question caught my attention and I started hacking away at it with one of my favourite programming techniques. Wishful thinking is a way of programming where write your program and wish it were true -
const result =
make
( Object.values(itemCatalog)
, myComponents
)
console.log(result)
// ...Above I wish I could call make with items to make and the available components. A wish made is a wish granted... by you! -
constmake = (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))
Along the way we make more wishes. The complexity of making a collection of items, make, is separate from the complexity of making a single item, make1. Wish granted -
constmake1 = (item, components, ifTrue, ifFalse) =>
pick
( components
, item.components
, (remainder, _) =>ifTrue(remainder, item.name)
, ifFalse
)
Get greedy now. While we're at it, I wish I could pick elements from an array. Wish granted -
constpick = (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
)
Ask for a meter, take a parsec. Oh you need to pick a single item from an array? Wish granted by pick1 -
constpick1 = (t, q, ifTrue, ifFalse) =>
search
( t
, v => v === q
, (v, i) =>ifTrue(drop(t, i), v)
, ifFalse
)
You're not one of those lame genies limited to fulfilling three wishes. If only I could search the array...
Wish granted! -
constsearch = (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)
Grants wishes for days -
constdrop = (t, i, n = 1) =>
t.slice(0, i).concat(t.slice(i + n))
When the wishing ends and the wishes are fulfilled your program is complete. As if by magic -
// 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" ]
, []
]
The output for make here shows all possible buying options. Writing maximal subsets is real head-scratcher. I'm going to pore over Scott's notes now...
write modules
Organising your code is an important hygienic exercise. Bundling function in modules promotes code reuse and gives us a manageable barrier of abstraction.
Many of the functions we wrote are generic and can be used on any array. Let's put them in a module called arr -
// arr.jsconstdrop = (t, i, n = 1) =>
t.slice(0, i).concat(t.slice(i + n))
constpick1 = (t, q, ifTrue, ifFalse) =>
search
( t
, v => v === q
, (v, i) =>ifTrue(drop(t, i), v)
, ifFalse
)
constpick = (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
)
constsearch = (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 }
We'll bundle the item crafting functions into a module called craft. Notice how this module can depend on functionality provided by another module -
// craft.jsimport { drop, pick } from"./arr.js"constmake1 = (item, components, ifTrue, ifFalse) =>
arr.pick
( components
, item.components
, (remainder, _) =>ifTrue(remainder, item.name)
, ifFalse
)
constmake = (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 }
Finally write your main module -
// main.jsimport { make } from"./craft.js"const itemCatalog = ...
const myComponents = ...
const result =
make
( Object.values(itemCatalog)
, myComponents
)
console.log(result)
// ...Solution 3:
I think several functions are required to get the output.
a) A function that says: given required components (for an item), does inventory exists to make the item ?
// are required components (req) a subset of inventory (inv) ?constcanMakeItem = (req, inv) => req.every(r => inv.indexOf(r) > -1);
b) An 'n choose k' function to return an array of item combinations that are to be considered as 'simultaneously createable'. I used this one:
// choose k items from arrayconstchooseCombos = (arr, k, prefix=[]) => {
if (k == 0) return [prefix];
return arr.flatMap((v, i) =>chooseCombos(arr.slice(i+1), k-1, [...prefix, v])
);
}
In your example output, we see pairs of items because this is what the example inputs of the item catalog and component list allow. Given a bigger item catalog and bigger component list then the output would be more than 'pairs' - I try and address that later on in the answer. Using an 'n choose k' function will ultimately allow for testing of combinations of 3, 4, more etc items from the catalog.
c) A function that can take the difference of two arrays (preserving duplicates) to keep track of remaining components as a set of items 'simultaneous creatability' is tested. I used this one:
// array difference with dupesconst 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() ));
}
d) My version of buildSimultaneousItems:
// eliminate combos (arrs[n]) with insufficient inventory (inv) for all items in comboconstcreateableCombos = (arrs, inv) => {
return arrs.filter(arr => {
// we know arr[0] is possible so remove componentslet currentComponents = remainingComponents(myComponents, itemCatalog[arr[0]].components);
// check subsequent array itemsfor (let i=1; i<arr.length; i++) {
let requiredComponents = itemCatalog[arr[i]].components;
if (!canMakeItem(requiredComponents, currentComponents)) {
// this combo cannot be made from available componentsreturnfalse
} else {
// remove components from inventory for this item
currentComponents = remainingComponents(currentComponents, requiredComponents);
}
}
// we can make all the items in this combo!returntrue;
});
}
The start point here is e.g.
[
[violin, guitar],
[guitar, trumpet],
[violin, trumpet]
]
In that all items of the array are to be tested, but not all are possible e.g. strings used on violin and not available for guitar. The chooseCombos function should eliminate the duplicates e.g. [trumpet, violin].
For each array, assume the first item is createable and remove the required components from inventory. For the rest of the items, repeat the createability test and remove components. If at any point an item cannot be created, then return false for that array and it will be filtered out from the result.
e) Putting it all together:
// eliminate single items not able to be made// in the example all items can be createdlet 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);
The array of createableSingleItems as a start point will reduce redundant processing later and enable createableCombos to 'know' that arr[0] is 'createable'.
So choosing pairs from the item catalog (where each pair is known to be createable individually):
// candidate pairs - pairs is n choose _2_let candidatePairs = chooseCombos(createableSingleItems, 2, []);
let createablePairs = createableCombos (candidatePairs, myComponents)
Produces this output:
[
["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"]
]
For the named output e.g.
createablePairs.map(a => a.map(b => itemCatalog[b].name));
Gives:
[
["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"]
]
Choosing triples (n choose 3) from the item catalog gives [] because we don't have enough inventory...
The maximum choice for n choose k is k == n == max(catalog). For a very large catalog and a very large inventory, it may be optimisation is required for this method. For a very large catalog and a relatively small inventory, the preparatory step of createableSingleItems may suffice.
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) ?constcanMakeItem = (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 arrayconstchooseCombos = (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 dupesconstremainingComponents = (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), newMap() ));
}
// eliminate combos (arrs[n]) with insufficient inventory (inv) for all items in comboconstcreateableCombos = (arrs, inv) => {
return arrs.filter(arr => {
// we know arr[0] is possible so remove componentslet currentComponents = remainingComponents(myComponents, itemCatalog[arr[0]].components);
// check subsequent array itemsfor (let i=1; i<arr.length; i++) {
let requiredComponents = itemCatalog[arr[i]].components;
if (!canMakeItem(requiredComponents, currentComponents)) {
// this combo cannot be made from available componentsreturnfalse
} else {
// remove components from inventory for this item
currentComponents = remainingComponents(currentComponents, requiredComponents);
}
}
// we can make all the items in this combo!returntrue;
});
}
// eliminate single items not able to be made// in the example all items can be createdlet 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.log("Pairs:");
console.log(createablePairs );
console.log("Triples:");
console.log(createableTriples);
Post a Comment for "Output Array Of Simultaneously Possible Unique Element Combinations"