Trimming a Combinatorical Tree

In computational material science, one frequently needs to know the number of unique atomic configurations in a structure. For example in an A$_{3}$B phase, two different kinds of atoms may be present on the B sites. In modeling possible alloys one needs to know the number of possible arrangements on the B sites. The obvious solution to this combinatorics problem is to generate the list of all possible configurations and then eliminate those that are symmetrically equivalent. This approach, however, suffers from a combinatoric explosion, particularly for large structures with more than two atom types. This happens even when there are a large number of symmetrically-equivalent configurations and only a few unique configurations that survive the elimination process. We developed a new algorithm that avoids this problem by not generating the entire list of configurations. Instead, it generates ``partial configurations'' and applies the symmetry operations without finding each ``complete'' configuration. This algorithm allows us to tackle much larger problems due to increases in computational efficiency.