Given a set of integers $\ S = \{1, 2, ... n\}$ and $R$ the set of all possible partitions of S.
Let's define function $f$ which maps a partition $P \in R$ to a multiset containing the cardinalities of elements of $P$: $f(P)=\{\left\vert{p}\right\vert \mid p \in P\}$.
Let A be the set of all equivalence classes on $R$: $A_i \in A, [A_i] = \{P \in R \mid f(P) = A_j \}\}$. $\left\vert{A}\right\vert = p(n)$, the integer partition function.
I'm interested in $ Q \subseteq R $ with the following conditions:
1) $\forall A_i \in A, \exists P \in [A_i], P \in Q$.
2) $\forall Q_j \in Q, \forall A_i \in A$ where $f(Q_j) \ne A_i$,let $f(Q_j) \cap A_i = C$, if $C \ne ∅$ then $\exists Q_k \in [A_i], U \subset Q_j, V \subset Q_k, f(U) = f(V) = C$ and $U = V$
I'll try to summarise it in english: I have the partitions of a set. I divide the partitions into equivalence classes based on the length of the elements of the partition (these are the same as the elements in the integer partition of $n$). I need at least one element from each equivalence class. The other condition is that for any subset of any element of my result, $Q$, if there are other elements of my result(in each different equivalence class) that have a subset with the same cardinality as my subset then at least one of them must be equal to the first subset.
Example1:
$ S = \{1, 2, 3, 4\}$
$[\{4\}] = \{\{\{1, 2, 3, 4\}\}\}$
$[\{3, 1\}] = \{\{\{1, 2, 3\}, \{4\}\}, \{\{1, 2, 4\}, \{3\}\}, \{\{1, 3, 4\}, \{2\}\}, \{\{2, 3, 4\}, \{1\}\}\}$
$[\{2, 2\}] = \{\{\{1, 2\}, \{3, 4\}\}, \{\{1, 3\}, \{2, 4\}\}, \{\{1, 4\}, \{2, 3\}\}\}$
$[\{2, 1, 1\}] = \{\{\{1, 2\}, \{3\}, \{4\}\}, \{\{2, 3\}, \{1\}, \{4\}\}, \{\{3, 4\}, \{1\}, \{2\}\}, \{\{1, 4\}, \{2\}, \{3\}\}\, \{\{1, 3\}, \{2\}, \{4\}\}\{\{2, 4\}, \{1\}, \{3\}\}\}$
$[\{1,1,1,1\}] = \{\{\{1\}, \{2\}, \{3\}, \{4\}\}\}$
I need (at least) one element from each category.
For example $Q_1 = \{\{\{1, 2, 3, 4\}\}, \{\{1, 2, 3\}, \{4\}\}, \{\{1, 2\}, \{3, 4\}\}, \{\{1, 4\}, \{2\}, \{3\}\}, \{\{1\}, \{2\}, \{3\}, \{4\}\}\}$ is not a good subset because
a) $\{\{4\}\} \subset \{\{1, 2, 3\}, \{4\}\}$ and $\{\{4\}\} \not\subset \{\{1, 4\}, \{2\}, \{3\}\}$, but $\{\{2\}\} \subset \{\{1, 4\}, \{2\}, \{3\}\}$ and $f(\{\{2\}\}) = f(\{\{4\}\}) = \{1\}$
b) $\{\{1, 2\}\} \subset \{\{1,2\}, \{3,4\}\}$ and $\{\{3, 4\}\} \subset \{\{1,2\}, \{3,4\}\}$ but $\{\{1, 2\}\} \not\subset \{\{1, 4\}, \{2\}, \{3\}\},\{\{3, 4\}\} \not \subset \{\{1, 4\}, \{2\}, \{3\}\}$ even though $|\{1, 2\}| = |\{3, 4\}| = |\{1. 4\}|$
$Q_2 = \{\{\{1, 2, 3, 4\}\}, \{\{1, 2, 3\}, \{4\}\}, \{\{1, 2\}, \{3, 4\}\}, \{\{1, 2\}, \{3\}, \{4\}\}, \{\{1\}, \{2\}, \{3\}, \{4\}\}\}$ meets the criteria. So it is enough to choose a good partition one from each category for $n=4$.
Example2: $S = \{1, 2, 3, 4, 5\}$ For $n = 5$, the mininum number of partitions required seems to be 12, here is one (out of the 5, I think) possible solutions when $Q$ has 12 elements.
So the question is: does this problem have a name that I can search for? How could I find the minimum cardinality of $Q$ and what would be a good algorithm to generate it?
