Applications of a Subset-Generating Algorithm to Base Enumeration, Knapsack and Minimal Covering Problems

Abstract

On the basis of a backtrack procedure for lexicographic enumeration of all subsets of a set of n elements, we give an algorithm for both 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 left brace 1,. . . , n right brace .