Generating All and Random Instances of a Combinatorial Object
Ivan Stojmenovic · 2007
Many practical problems require an exhaustive search through the solution space, which are represented as combinatorial structures, such as, permutations, combinations, set partitions, integer partitions, and trees. All combinatorial objects of a certain kind need to be generated to test all possible solutions. In some other problems, a randomly generated object is needed, or an object with an approximately correct ranking among all objects, without using large integers. Fast algorithms for generating all objects, random object, or object with approximate ranking for basic types of combinatorial objects are described.