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

suppose want take items 4 sets, s1-s4. sets share items between them. example sets be:

s1 = ['b1']; s2 = ['b1', 'b2']; s3 = ['b1', 'b2', 'b3']; s4 = ['b1', 'b2', 'b3', 'b4']; 

it pretty obvious if pick 1 item s1 (b1) can pick 1 item s2, 2 s3 , 3 s4.

but if pick 1 item s4 @ next step able pick items s1 or items s2 or items s3, because algorithm must smart enough know there combination (e.g. allocating b4 s4) allow higher max free elements other sets (by picking b4 have max free 3 in s3, 2 in s2 , 1 in s1)

to put in way, algorithm, when occupy 1 element set, should not occupy specific element instead smart enough know how many elements (max number) can occupied other sets given items picked in smart way.

demonstration of how should work (green = available, red = occupied, orange = occupied because of occupation set):

another demonstration:

(note algorithm finds s5 has 3 unique elements, other set free)

and one:

(notice algorithm understands if pick 4 s5 have give 1 other categories)

another one:

(if pick 3 items s5 have give 1 item s2 , can pickup 2 elements @ max. notice occupied item in s2 not specific element, it's either b1 or b7, doesn't matter, i'm interested on max number of elements can pick it)

all of above work fine algorithm, fails in other occasions.

what i've tried far (nodejs code language solution 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 = {};     (var in allcategories) {         categories[i] = {             total: allcategories[i].length,             occupied: 0,             dueto: {},             totaldue: 0         };          common[i] = {};          (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 many elements of type', categoryid);         return false;     }      category.occupied += counttooccupy;      (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 not occupied thingies here deoccupy them');         return false;     }      category.occupied -= counttodeoccupy;      (var othercategoryid in common[categoryid]) {          if (!categories[othercategoryid].dueto.hasownproperty(categoryid)) {             continue; // no elements set due parent category         }          var duetonumber = categories[othercategoryid].dueto[categoryid];          var counttoremove = math.min(counttodeoccupy, duetonumber);          if (counttoremove === duetonumber) {             // remove 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()     (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 visualized categories , creates data structure i'm using figure out needs occupied , deoccupied in occupy , deoccupy calls. data structure looks this:

category = { // or "set" of items     total: // number: total entries of set     occupied: // number: how many elements of set occupied, either directly or indirectly     dueto: // object {categoryid -> number}: how many elements of set indirectly occupied , due category. (e.g. dueto = {s1: 1, s3: 1} means 1 occupied indirectly through s1 , 1 indirectly through s3)     totaldue: 0 // number: sum of dueto entries }; 

notes:

• the category processing creates common object, 2d array , saves how many common elements categories have. (e.g. common['s1']['s2'] === 4)
• occupied - totaldue gives directly occupied (red) entries.

• in order occupy entries use

  var atleastthatmustoccupied = (category.occupied + commoncount) - category.total;

which seems working in cases in others doesn't work.

• dueto used in order de-occupy entries.

in first images, code works fine, in example code fails:

in worst case real world scenario, sets can have 300 items each, have 10 sets , algorithm should fast enough (hopefully < 1s in common cpus) determine how many items can picked sets. also, algorithm should able de-occupy items e.g. opposite thing - remove item set , determine how many items can picked other sets.

it assumed element can de-occupied set if directly occupied set. (e.g. if s3 = ['b1', 'b2', 'b3'] , of elements indirectly occupied, cannot call de-occupy remove elements s3)