Algorithm to determine how many items are left (at most) between sets that share items

Question

Suppose that we want to take items from 4 sets, S1-S4. The sets share items between them. Some example sets would be:

S1 = ['b1'];
S2 = ['b1', 'b2'];
S3 = ['b1', 'b2', 'b3'];
S4 = ['b1', 'b2', 'b3', 'b4'];

It is pretty obvious that if you pick one item from S1 (b1) then you can only pick 1 item from S2, 2 from S3 and 3 from S4.

But if you pick one item from S4 then at the next step you are able to pick all items from S1 or all items from S2 or all items from S3, simply because the algorithm must be smart enough to know that there is a combination (e.g. allocating b4 from S4) that will allow a higher max free elements from the other sets (by picking b4 you have max free 3 in S3, 2 in S2 and 1 in S1)

To put it in another way, the algorithm, when you occupy one element from a set, should not occupy a specific element but instead be smart enough to know how many elements (max number) can be occupied from the other sets given that the items are picked in a smart way.

Demonstration of how it should work (green = available, red = occupied, orange = occupied because of occupation from another set):

Another demonstration:

(note that the algorithm finds that S5 has 3 unique elements, so any other set is completely free)

And another one:

(notice that the algorithm understands that if you pick all 4 from S5 then you have to give up one from the other categories)

Another one:

(if you pick 3 items from S5 you will have to give up 1 item from S2 and now you can pickup only 2 elements from it at max. Notice that the occupied item in S2 is not a specific element, it's either b1 or b7, it doesn't matter, I'm only interested on what is the max number of elements that I can now pick from it)

All of the above work fine with my algorithm, but it fails in other occasions.

What I've tried so far (nodejs code but any language solution is welcome):

var allCategories = [];

const process = require('process');

Reset = '\x1b[0m'
FgRed = '\x1b[31m'
FgGreen = '\x1b[32m'
FgYellow = '\x1b[33m'

function getCommonCount(s1, s2) {
    return s1.filter((n) => s2.includes(n)).length;
}

var categories = {};
var common = {};
function processCategories() {
    categories = {};
    for (var i in allCategories) {
        categories[i] = {
            total: allCategories[i].length,
            occupied: 0,
            dueTo: {},
            totalDue: 0
        };

        common[i] = {};

        for (var j in allCategories) {
            if (i === j) {
                continue;
            }
            common[i][j] = getCommonCount(allCategories[i], allCategories[j]);
        }
    }
}

function occupy(countToOccupy, categoryId) {
    console.log('OCCUPY', countToOccupy, 'from', categoryId);

    var category = categories[categoryId];
    var free = category.total - category.occupied;

    if (free < countToOccupy) {
        console.log('Cannot occupy that many elements of type', categoryId);
        return false;
    }

    category.occupied += countToOccupy;

    for (var otherCategoryId in common[categoryId]) {
        var commonCount = common[categoryId][otherCategoryId];

        var atLeastThatMustOccupied =  (category.occupied + commonCount) - category.total;

        if (atLeastThatMustOccupied < 0) {
            continue;
        };

        var otherCategory = categories[otherCategoryId];

        if (otherCategory.occupied < atLeastThatMustOccupied) {

            var countToOccupyOtherCategory = atLeastThatMustOccupied - otherCategory.occupied;

            otherCategory.occupied += countToOccupyOtherCategory;

            if (!otherCategory.dueTo.hasOwnProperty(categoryId)) {
                otherCategory.dueTo[categoryId] = 0;
            }

            otherCategory.dueTo[categoryId] += countToOccupyOtherCategory;
            otherCategory.totalDue += countToOccupyOtherCategory;
        }
    }

    return true;
}

function deoccupy(countToDeoccupy, categoryId) {
    console.log('DEOCCUPY', countToDeoccupy, 'from', categoryId);
    var category = categories[categoryId];

    var reallyOccupied = (category.occupied - category.totalDue);

    if (reallyOccupied < countToDeoccupy) {
        console.log('There are not that much really occupied thingies here so as to deoccupy them');
        return false;
    }

    category.occupied -= countToDeoccupy;

    for (var otherCategoryId in common[categoryId]) {

        if (!categories[otherCategoryId].dueTo.hasOwnProperty(categoryId)) {
            continue; // no elements set due to the parent category
        }

        var dueToNumber = categories[otherCategoryId].dueTo[categoryId];

        var countToRemove = Math.min(countToDeoccupy, dueToNumber);

        if (countToRemove === dueToNumber) {
            // remove the dueTo field
            delete categories[otherCategoryId].dueTo[categoryId];
        } else {
            categories[otherCategoryId].dueTo[categoryId] -= countToRemove;
        }

        categories[otherCategoryId].totalDue -= countToRemove;
        categories[otherCategoryId].occupied -= countToRemove;
    }

    return true;
}

function visualizeCategories() {
    process.stdout.write(Reset);

    console.log()
    for (let categoryId in categories) {
        var category = categories[categoryId];
        var reallyOccupied = (category.occupied - category.totalDue);
        var free = category.total - category.occupied;
        process.stdout.write(FgGreen + categoryId + ' ');
        process.stdout.write(FgRed + '0'.repeat(reallyOccupied));
        process.stdout.write(FgYellow + '0'.repeat(category.totalDue));
        process.stdout.write(FgGreen + '0'.repeat(free));
        console.log()
    }

    console.log(Reset);
}

allCategories = {
    S1: ['b1'],
    S2: ['b1', 'b2'],
    S3: ['b1', 'b2', 'b3'],
    S4: ['b1', 'b2', 'b3', 'b4'],
    S5: ['b5', 'b1', 'b7', 'b8']
};

console.log('CATEGORIES:');
console.log(allCategories);

processCategories();

occupy(1, 'S1'); visualizeCategories();
occupy(3, 'S5'); visualizeCategories();
occupy(1, 'S2'); visualizeCategories();
occupy(1, 'S3'); visualizeCategories();

deoccupy(3, 'S5'); visualizeCategories();
deoccupy(1, 'S1'); visualizeCategories();
deoccupy(1, 'S3'); visualizeCategories();
deoccupy(1, 'S2'); visualizeCategories();


allCategories = {
    S1: ['b1'],
    S2: ['b1', 'b2'],
    S3: ['b2']
};

console.log('CATEGORIES:');
console.log(allCategories);

processCategories();

occupy(1, 'S1', true); visualizeCategories();
occupy(1, 'S3', true); visualizeCategories();

Code explanation: processCategories analyzes the visualized categories and creates the data structure I'm using to figure out what needs to be occupied and deoccupied in occupy and deoccupy calls. The data structure looks like this:

category = { // or "set" of items
    total: // NUMBER: total entries of this set
    occupied: // NUMBER: how many elements of this set are occupied, either directly or indirectly
    dueTo: // OBJECT {categoryId -> number}: how many elements of this set are indirectly occupied and due to which category. (e.g. dueTo = {S1: 1, S3: 1} means 1 occupied indirectly through S1 and 1 indirectly through S3)
    totalDue: 0 // NUMBER: sum of the dueTo entries
};

Notes:

The category processing creates the common object, which is essentially a 2d array and it saves how many common elements the categories have. (e.g. common['S1']['S2'] === 4)
occupied - totalDue gives the directly occupied (red) entries.
In order to occupy entries I use

var atLeastThatMustOccupied = (category.occupied + commonCount) - category.total;

which seems to be working in some cases but in others it doesn't work.

dueTo is used in order to de-occupy entries.

In the first images, the code works fine, in this example the code fails:

In the worst case real world scenario, the sets can have up to 300 items each, have up to 10 sets and the algorithm should be fast enough (hopefully < 1s in common cpus) to determine how many items can be picked from all the sets. Also, the algorithm should be able to de-occupy items e.g. do the opposite thing - remove an item from a set and determine how many items can now be picked from the other sets.

It is assumed that an element can be de-occupied from a set only if it is directly occupied from this set. (e.g. if S3 = ['b1', 'b2', 'b3'] and all of its elements are indirectly occupied, you cannot call de-occupy to remove elements from S3)

Algorithm to determine how many items are left (at most) between sets that share items

0 Answers