set intersection - finding the smallest array that intersects with a set of arrays -

-

say have 3 arrays - ['a', 'b'], ['b', 'c'] , ['d']. if create fourth array intersects these 3 arrays minimal number of elements array i'd ['b', 'd']. question is... how go finding array?

like ['a', 'b', 'c', 'd'] intersects arrays it's not minimal intersection - ['b', 'd'] is.

any ideas?

i don't have answer algorithm, true that, commenter amit wrote, np-complete problem. problem called hitting set problem, equivalent set cover problem.

if you're fine approximation, according wiki article, greedily picking elements hit arrays gets.


Comments

Post a Comment

Popular posts from this blog

cytoscape.js - How to add nodes to Dagre layout with Cytoscape -

-
i trying add nodes dagre graph through cityscape.js. problem nodes not painted. code have: cy.add({ group: "nodes", data: { id:"n0",name:"n0",weight: 75 }, }); $.ajax(url).done(function(jsontree){ var newnodes=[]; for(var i=1;i<6;i++){ //var child = jsontree.result[i]; newnodes.push( { group: "nodes", data: { id: "n"+i, name:"n"+i}}, { group: "edges", data: { id: "e"+i, source: "n0", target: "n"+i } } ); } cy.add(newnodes); any ideas? have used loaded function reload graph not work. not know if have use specific function reload graph. thank in advance. you need add positions new nodes. cytoscape.js docs : it important note positions of newly added nodes must defined when calling cy.add(). nodes can not placed in graph without valid position — otherwise not displayed. yo...
Read more

apache - setting document root in antoher partition on ubuntu -

-
i place apache document root inside partition of ubuntu hard drive, keep getting forbidden message, when place home directory woking find, how be? group or owner affected ? here mysite.conf , apache2.conf when place document root in home folder (working) #site-available/mysite.conf documentroot /home/jono/www #/etc/apache2/apache2.conf <directory /home/jono/www/> options indexes followsymlinks allowoverride none require granted </directory> bu when change document root partition keep getting forbidden messasge #site-available/mysite.conf documentroot /media/jono/website_data/www #/etc/apache2/apache2.conf <directory /media/jono/website_data/www/> options indexes followsymlinks allowoverride none require granted </directory> is owner/group access affected ? or there problem ? at last it's working, have grant access www:data accesing whole directory @mark-b, using chown -r www-data:www-data whole directory is...
Read more

python - pip install -U PySide error -

-
does know how avoid following error when running pip install -u pyside per official website instructions here: https://pypi.python.org/pypi/pyside/#installing-pyside-on-a-mac-os-x-system note have done brew install qt successfully. you using pip version 7.0.3, version 7.1.2 available. should consider upgrading via 'pip install --upgrade pip' command. collecting pyside using cached pyside-1.2.4.tar.gz installing collected packages: pyside running setup.py install pyside complete output command /applications/anaconda/bin/python -c "import setuptools, tokenize;__file__='/private/var/folders/dy/ttgqhqqx3g9bsbsnqnxsk2z80000gq/t/pip-build-cpxemt/pyside/setup.py';exec(compile(getattr(tokenize, 'open', open)(__file__).read().replace('\r\n', '\n'), __file__, 'exec'))" install --record /var/folders/dy/ttgqhqqx3g9bsbsnqnxsk2z80000gq/t/pip-0r7hri-record/install-record.txt --single-version-externally-managed --compile: ...
Read more