Now that we’ve discussed a nice standard example of canonical deletion, I want to get into more complicated uses. These techniques use more complicated augmentations and deletions, and hence require a little more delicate description of orbit calculations. In order to get to those, we need to be able to store and manipulate subsets of things. Another way to think of “subsets of things” is combinations, especially when we know the size of the subset.
Given a set , we will discuss the power set of all subsets of , the -subsets , the -tuples , and the -permutations . There are multiple ways to store a given subset, tuple, or permutation, but what is more important is how to store a list of information over the entire collection of these objects. My favorite method is to use a ranking function, which assigns each object an integer which I can use as an array position. Then, an unranking function will invert this process.
This area has a long history, with several different methods of ranking and unranking the objects competing for dominance in several measures of quality. My favorite measure is “readability” and/or “ease of programming” but definitely “computation speed” is important, too. However, sometimes ranking is fast and unranking is slow, sometimes the ranking and unranking is fixed to a certain order, such as lexicographic order.
Today we’ll talk about several ranking and unranking procedures, and the next post will discuss how to use these ranking/unranking functions to compute orbits of these objects for a graph with symmetry.
Read the rest of this entry »