4
$\begingroup$

Lately, I asked this question to find the maximal set of elements $S$ of a given array $T$ such that every element of $S$ is greater than or equal to the cardinality of $S$.

My question is now different. How to find all maximal sets $S_i$ of a given array $T$ such that every element of $S_i$ is greater than or equal to the cardinality of $S_i$.

For example, if $T=[9, 8, 2, 2, 1]$, then all maximal sets that satisfy the condition are $S_1=[9, 8]$, $S_2=[9, 2]$, $S_3=[9, 2]$, $S_4=[8, 2]$, $S_5=[8, 2]$ and $S_6=[2, 2]$.

My recursive solution or the solutions given in the previous question do not generate all maximal sets.

Is there any efficient algorithm that finds all maximal sets of such problem?

I think one way to solve the problem is to find a maximal set $S$ and return its size $|S|$--using any algorithm from this question. Then, generate all combinations $\displaystyle\binom{|T|}{|S|}$ and find which one of these combinations satisfies the condition. But can we do better?

$\endgroup$
  • 1
    $\begingroup$ Obviously, you can drop 1 from T, once you know that |S|=2. Other than that (and some duplicate handling), there is nothing to improve. There really are that many maximal sets. $\endgroup$ – Karolis Juodelė Nov 18 '16 at 19:34
  • 1
    $\begingroup$ What do you mean by maximal set? Maximum size, or inclusion-maximal? $\endgroup$ – Yuval Filmus Nov 18 '16 at 21:07
4
$\begingroup$

Assuming that by maximal sets you mean sets of maximal size (rather than sets which are inclusion-maximal), then there is a very simple algorithm. First, find the maximal size $s$. Second, filter out all elements smaller than $s$. Third, output all subsets of size $s$ of the remaining elements.

$\endgroup$
  • $\begingroup$ Good. I think this works fine. Thanks. $\endgroup$ – drzbir Nov 18 '16 at 21:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.