Applications of a Subset-Generating Algorithm to Base Enumeration, Knapsack and Minimal Covering Problems
Ivan Stojmenović · The Computer Journal · 1988
On the basis of a backtrack procedure for lexicographic enumeration of all subsets of a set of n elements, we give an algorithm both for determining all bases consisting of functions from a given complete set in a considered subset of the set of k-valued logical functions, and for enumeration of all classes of bases in the subset. We use the lexicographic algorithm also for solving knapsack and minimal covering problems. A cut technique is described which is used in these algorithms to reduce the number of examined subsets of {1, …, n}.