HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMinor

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$

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
s_isuchthehowcardinalityallarraygreaterthanequal

Problem

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?

Solution

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.

Context

StackExchange Computer Science Q#66205, answer score: 4

Revisions (0)

No revisions yet.