This work presents a formalism to calculate the configurational entropy of mixing based on the identification of non-interacting atomic complexes in the mixture and the calculation of their respective probabilities, instead of computing the number of atomic configurations in a lattice. The methodology is applied in order to develop a general analytical expression for the configurational entropy of mixing of interstitial solutions. The expression is valid for any interstitial concentration, is suitable for the treatment of interstitial short-range order (SRO) and can be applied to tetrahedral or octahedral interstitial solutions in any crystal lattice. The effect of the SRO of H on the structural properties of the Nb-H and bcc Zr-H solid solutions is studied using an accurate description of the configurational entropy. The methodology can also be applied to systems with no translational symmetry, such as liquids and amorphous materials. An expression for the configurational entropy of a granular system composed by equal sized hard spheres is deduced.