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

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

arrays - C++ error: a brace-enclosed initializer is not allowed here before ‘{’ token -

-
simple question: i'm trying initialize array within c++ class declaration: using namespace std; #include <string> class myclass{ public: string myarray[] = {"a","b","c"}; }; and i'm getting error: error: brace-enclosed initializer not allowed here before ‘{’ token no, without complied c++11 compiler, cannot initialize member array in declaration. have initialize array member in constructor. , don't use open array if know number of elements initialize array.
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