create combinations for items with multiple unique identifiers

README.md

How to combine some stuff

Scenario

Imagine that you want to buy DVDs for all the Star Wars movies of the original trilogy. (For all the prequel and sequel lovers, this scenario works as well with more movies.) You search Ebay and end up with a list of auctions, each with a different price and each containing a certain subset of the three movies.

const auctions = [
  { id: 1, price: 11,  movies: ["NEW_HOPE"] },
  { id: 2, price: 13,  movies: ["EMPIRE_STRIKES_BACK"] },
  { id: 3, price: 8,   movies: ["RETURN_OF_THE_JEDI"] },
  { id: 4, price: 15,  movies: ["NEW_HOPE", "RETURN_OF_THE_JEDI"] },
  { id: 5, price: 21,  movies: ["NEW_HOPE", "EMPIRE_STRIKES_BACK"] },
  { id: 6, price: 19,  movies: ["EMPIRE_STRIKES_BACK", "RETURN_OF_THE_JEDI"] },
  { id: 7, price: 29,  movies: ["NEW_HOPE", "EMPIRE_STRIKES_BACK", "RETURN_OF_THE_JEDI"] },
];

So the question arises: What auctions should we buy, so that we end up with each movie exactly once?

The solution sounds fairly simple:

1. Build every combination of the seven auctions that contain all movies without duplicates
2. Sum up their prices.
3. Choose the overall cheapest combination.

Steps 2 and 3 aren't that much of a struggle, but how do we get all those combinations?

TL;DR

The file below exports a function that needs two arguments:

1. The list of items.
2. A function that takes in one of those items and returns a list of unique identifiers, that are included in this item.

The function will then return a list of combinations of items so that each of those combinations contains a set of items where each identifier is included exactly once.

To match the terminology of our scenario: The first argument for the function will be the list of the auctions. The second one should be a function that returns the movies array of an item.

const combinations = createCombinations(auctions, auction => auction.movies);

You will get back the expected result, which is:

// With equal we mean deep equality (of arrays).
assert.equal(combinations, [
  [
    { id: 1, price: 11,  movies: ["NEW_HOPE"] },
    { id: 2, price: 13,  movies: ["EMPIRE_STRIKES_BACK"] },
    { id: 3, price: 8,   movies: ["RETURN_OF_THE_JEDI"] },
  ],
  [
    { id: 1, price: 11,  movies: ["NEW_HOPE"] },
    { id: 6, price: 19,  movies: ["EMPIRE_STRIKES_BACK", "RETURN_OF_THE_JEDI"] },
  ],
  [
    { id: 2, price: 13,  movies: ["EMPIRE_STRIKES_BACK"] },
    { id: 4, price: 15,  movies: ["NEW_HOPE", "RETURN_OF_THE_JEDI"] },
  ],
  [
    { id: 3, price: 8,   movies: ["RETURN_OF_THE_JEDI"] },
    { id: 5, price: 21,  movies: ["NEW_HOPE", "EMPIRE_STRIKES_BACK"] }, 
  ],
  [
    { id: 7, price: 29,  movies: ["NEW_HOPE", "EMPIRE_STRIKES_BACK", "RETURN_OF_THE_JEDI"] },
  ],
])

About the algorithm used

So here is what the function createCombinations does:

You always have two sets to remember: The set of all the combinations that you already have found (which is what we will return at the end) and the current combination which usually is not complete yet. Initially, both sets are empty:

let allCombinations = [];
let currentCombination = [];

Let's start by adding the first auction to our current combination:

currentCombination = [
  { id: 1, price: 11,  movies: ["NEW_HOPE"] },
];

After we included something in the current combination we always have to ask ourselves: Does this combination now contain all movies? Currently the answer is no. So let's carry on, we will see later what happens if the answer to this question is yes.

Now we take a look at the next auction. The question we now ask is: Can we include this auction in our currentCombination without duplicate movies? In our case the answer is yes! So let's add it:

currentCombination = [
  { id: 1, price: 11,  movies: ["NEW_HOPE"] },
  { id: 2, price: 13,  movies: ["EMPIRE_STRIKES_BACK"] },
];

Still, not all movies there yet. So we repeat the process with the third auction, which we can also add to the current combination:

currentCombination = [
  { id: 1, price: 11,  movies: ["NEW_HOPE"] },
  { id: 2, price: 13,  movies: ["EMPIRE_STRIKES_BACK"] },
  { id: 3, price: 8,   movies: ["RETURN_OF_THE_JEDI"] },
];

Hooray, we have a combination that includes all movies! Don't waste any time and put this combination in our array of all combinations:

allCombination = [
  [
    { id: 1, price: 11,  movies: ["NEW_HOPE"] },
    { id: 2, price: 13,  movies: ["EMPIRE_STRIKES_BACK"] },
    { id: 3, price: 8,   movies: ["RETURN_OF_THE_JEDI"] },
  ],
];

To be able to continue, we now forget the last item that we added to our current combination, which means we are back to the following:

currentCombination = [
  { id: 1, price: 11,  movies: ["NEW_HOPE"] },
  { id: 2, price: 13,  movies: ["EMPIRE_STRIKES_BACK"] },
];

We looked auction 3 within this scope, so now we continue with auction 4. But this one doesn't fit in our current combination because it contains the movie NEW_HOPE which we already have through auction 1. Therefore we can skip auction 4 and repeat the process with auction 5.

As it turns out, neither auction 5, 6 or 7 can be included in our current combination. Since we ran out of options here, we again forget the last item that we added to our combination:

currentCombination = [
  { id: 1, price: 11,  movies: ["NEW_HOPE"] },
];

We covered all cases where we added auction 2, so we are done with it for now. We look at the next auction, which is auction 3. This one fits into the current combination:

currentCombination = [
  { id: 1, price: 11,  movies: ["NEW_HOPE"] },
  { id: 3, price: 8,   movies: ["RETURN_OF_THE_JEDI"] },
];

We continue with auctions 4 to 7, but we cannot find any auction that just contains the missing movie. Sadly, we are back to forgetting the last auction:

currentCombination = [
  { id: 1, price: 11,  movies: ["NEW_HOPE"] },
];

From this point we went to auction 2 and 3 and discovered all possibilities there. We now look at auctions 4 and 5 next. But those can't be added since they both contain NEW_HOPE. With auction 6 we finally got some luck again. We gladly add it to the current combination:

currentCombination = [
  { id: 1, price: 11,  movies: ["NEW_HOPE"] },
  { id: 6, price: 19,  movies: ["EMPIRE_STRIKES_BACK", "RETURN_OF_THE_JEDI"] },
];

And take a look at that! We have found another complete combination of auctions! So we add it to the list of all the successful combinations:

allCombination = [
  [
    { id: 1, price: 11,  movies: ["NEW_HOPE"] },
    { id: 2, price: 13,  movies: ["EMPIRE_STRIKES_BACK"] },
    { id: 3, price: 8,   movies: ["RETURN_OF_THE_JEDI"] },
  ],
  [
    { id: 1, price: 11,  movies: ["NEW_HOPE"] },
    { id: 6, price: 19,  movies: ["EMPIRE_STRIKES_BACK", "RETURN_OF_THE_JEDI"] },
  ],
];

After forgetting auction 6 and trying auction 7 (which of course doesn't yield any success) we are finally done with all successful combinations containing the first auction. So now we forget auction 1 and are back to an empty current combination.

currentCombination = [];

What is left is to repeat the process we just did, but starting with auction 2, then starting with auction 3 and so on. We are finished once we looked at only auction 7. (In our example, this is in fact a success, but of course this doesn't have to be the case in general).

A more realistic scenario

You might think I just made up a problem. And (until now) I did. The first scenario should just make the problem more accessible. But I discovered this problem recently while developing a comparison for insurance quotes for my current employer.

We recently developed the first comparison page in Germany, where the customer can compare multiple kinds of insurances at once, e.g. a liability and a legal insurance. Most insurers sell these two products seperately, but there are insurers, which offer those two products under one quote. Now our challenge was to get all possible combinations from the list of available quotes. (Of course, this can scale to more than two insurance products.)

I thought it would be of value to share the solution that we came up with. I can imagine there are other use cases for this in the real world.

In the end, I have to add a warning: The function in this gist doesn't perform that well once the list of items gets large. When we tried it out with five identifiers and 270 items, the NodeJS process crashed after about 10 minutes without any result 😥

FATAL ERROR: CALL_AND_RETRY_LAST Allocation failed - JavaScript heap out of memory

But I believe this function can serve as a baseline for an improved algorithm that might really be useful.

createCombinations.js

function _createCombinations(
  items,
  allIdentifiers,
  getAllIdentifiersForItems,
  currentCombination = []
) {
  // Step 0: Check if there are any items.
  // If not then return since there is nothing left to do.
  if (items.length === 0) {
    return [];
  }

  // Step 1: Separate the first item from the rest of the items.
  const [firstItem, ...restItems] = items;

  // Step 2: Calculate the possible combinations from all the rest items.
  const restCombinations = _createCombinations(
    restItems,
    allIdentifiers,
    getAllIdentifiersForItems,
    currentCombination
  );

  // Step 3: Check if every identifier of the first item is still missing in the current combination
  if (
    getAllIdentifiersForItems([firstItem]).every(
      identifier =>
        !getAllIdentifiersForItems(currentCombination).includes(identifier)
    )
  ) {
    // Step 3.1: Create a new combination form the current one and add the first item.
    const newCombination = [...currentCombination, firstItem];

    // Step 3.2: Check if the new combination contains all identifiers.
    if (
      getAllIdentifiersForItems(newCombination).length === allIdentifiers.length
    ) {
      // Step 3.3: Add the new combination to the array of all combinations.
      // We can return since we don't have to search for more items.
      return [newCombination, ...restCombinations];
    }
    // Step 3.4: Continue the recursion with the new combination. Only try those items that haven't been looked at yet.
    // We can then return the result of this together with the result from step 2.
    return [
      ..._createCombinations(
        restItems,
        allIdentifiers,
        getAllIdentifiersForItems,
        newCombination
      ),
      ...restCombinations
    ];
  }

  // Step 4: We could not find any combinations by going deeper from the current combination.
  // Therefore we can return the combinations which we found in step 2.
  return restCombinations;
}

function createCombinations(items, getIdentifiersFromItem) {
  function getAllIdentifiersForItems(itemList) {
    return itemList.reduce((acc, item) => {
      getIdentifiersFromItem(item).forEach(identifier => {
        if (!acc.includes(identifier)) {
          acc.push(identifier);
        }
      });
      return acc;
    }, []);
  }
  return _createCombinations(
    items,
    getAllIdentifiersForItems(items),
    getAllIdentifiersForItems
  );
}

module.exports.createCombinations = createCombinations;

createCombinations.test.js

const { createCombinations } = require("./foo");

const getIdentifiers = item => item.identifiers;

it("should return the expected list of combinations", () => {
  const collection = [
    { itemId: 0, identifiers: [1] },
    { itemId: 1, identifiers: [1] },
    { itemId: 2, identifiers: [2] },
    { itemId: 3, identifiers: [2] },
    { itemId: 4, identifiers: [3] },
    { itemId: 5, identifiers: [3] },
    { itemId: 6, identifiers: [1, 2] },
    { itemId: 7, identifiers: [1, 2] },
    { itemId: 8, identifiers: [1, 3] },
    { itemId: 9, identifiers: [1, 3] },
    { itemId: 10, identifiers: [2, 3] },
    { itemId: 11, identifiers: [2, 3] },
    { itemId: 12, identifiers: [1, 2, 3] },
    { itemId: 13, identifiers: [1, 2, 3] }
  ];

  const expectedRateCombinations = [
    [collection[0], collection[2], collection[4]],
    [collection[0], collection[2], collection[5]],
    [collection[0], collection[3], collection[4]],
    [collection[0], collection[3], collection[5]],
    [collection[0], collection[10]],
    [collection[0], collection[11]],
    [collection[1], collection[2], collection[4]],
    [collection[1], collection[2], collection[5]],
    [collection[1], collection[3], collection[4]],
    [collection[1], collection[3], collection[5]],
    [collection[1], collection[10]],
    [collection[1], collection[11]],
    [collection[2], collection[8]],
    [collection[2], collection[9]],
    [collection[3], collection[8]],
    [collection[3], collection[9]],
    [collection[4], collection[6]],
    [collection[4], collection[7]],
    [collection[5], collection[6]],
    [collection[5], collection[7]],
    [collection[12]],
    [collection[13]]
  ];
  expect(createCombinations(collection, getIdentifiers)).toEqual(
    expect.arrayContaining(expectedRateCombinations)
  );
});
describe("when there are no items", () => {
  it("should return an empty array", () => {
    expect(createCombinations([], getIdentifiers)).toEqual([]);
  });
});
describe("when there is only one identifier", () => {
  it("should return the list of items", () => {
    const collection = [
      { itemId: 0, identifiers: [1] },
      { itemId: 1, identifiers: [1] },
      { itemId: 2, identifiers: [1] },
      { itemId: 3, identifiers: [1] },
      { itemId: 4, identifiers: [1] }
    ];
    expect(createCombinations(collection, getIdentifiers)).toEqual(
      collection.map(item => [item])
    );
  });
});