I am looking for an algorithm to solve the following problem. I am unsure whether to post this in computational science or here, but since this is an algorithm I thought I would try here first.

I have a set of species made from a number of components.
Let's number each component $0, 1, 2 ... n$.
So now each species can be described as a set of these components. Each species is unique.

I am given a set of species, and I need to check whether any subset of these species fulfills the following condition: that the number of species in this subset is greater than the number of unique components in this subset.

For example: the set of species {[0, 1, 2], [0, 2], [1, 2], [0, 1]} fulfills the criterion, as the set has 4 species and 3 unique components. The set of species {[0, 1, 2], [0, 2], [1, 2], [0,1], [3,4]} also fulfills the criterion, as a subset of the set fulfills the criterion. The system {[0, 1, 2], [0, 2]} does not fulfill the criterion, as there are 2 species and 3 unique components.
In case it is relevant: there can be many species and components (20) but the number of components per species remains relatively small (2-5)

An easier version of this problem is also of interest to me: I have system which I know does not fulfill the criterion. The question is: if I add this species, will it fulfill the criterion?

This problem is equivalent to determining if a system of equations is over determined.

Edit: The criterion is equivalent to checking if the Gibbs Phase Rule is being violated in a system with only pure solid phases with at least 1 degree of freedom in addition to pressure and temperature. In this situation the number of phases is equal to the number of solids. There has a 0 or positive number of degrees of freedom left in the system or it becomes over constrained, so $0 \geq \text{number of components} - \text{number of species}$


The gibbs phase rule is simply a way of determining whether the system of equations which describes the system will be overdetermined.

As we are talking about (usually) solids, this system of equations looks like $K=A^nB^m...$
If we take the log of both sides, this can be simplified to $\log{k}=n\log{A}+m\log{B}...$.
If we substitute $a=\log{A}, b=\log{B}$ then this becomes a system of linear equations $\log{k}=n*a+m*b...$

Now we can represent this system of linear of equations as a coefficient matrix and then use the Rouche Cappeli Theorem to determine whether the system is overdetermined. Since each species each unique in your system, you simply need to determine if there are any rank deficiencies in your coefficient matrix.

In the first example: {[0, 1, 2], [0, 2], [1, 2]} can be represented as the matrix $$\begin{bmatrix} 1 & 1 & 1\\ 1 & 0 & 1\\ 0 & 1 & 1\\ 0 & 1 & 0 \end{bmatrix}$$ Which has a rank deficiency, therefore is overdetermined.


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.