Browse Prior Art Database

Generic High-Performance Subset Generation Method

IP.com Disclosure Number: IPCOM000101945D
Original Publication Date: 1990-Sep-01
Included in the Prior Art Database: 2005-Mar-17
Document File: 4 page(s) / 105K

Publishing Venue

IBM

Related People

Sun, KC: AUTHOR

Abstract

This method is useful for computer device placement strategy where all devices are to be mounted into a rack. For each device, there are specific locations they can be placed. In order to find out all possible computer configurations, we have to list first all combinations of the device locations. That is, if we consider all devices and their placement locations as a "set", what we need are all the subsets of the set.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Generic High-Performance Subset Generation Method

       This method is useful for computer device placement
strategy where all devices are to be mounted into a rack.  For each
device, there are specific locations they can be placed.  In order to
find out all possible computer configurations, we have to list first
all combinations of the device locations. That is, if we consider all
devices and their placement locations as a "set", what we need are
all the subsets of the set.

      Mathematically, for a set containing elements A, B, and C, all
eight subsets are:
      (), (A), (B), (C), (A,B) (A,C) (B,C), (A,B,C).

      Via a computer program, the usual way to produce the subsets of
this set [A,B,C] is by going through all combinations and extracting
the unique ones.  The following pseudo code describes this method:
      do n1=0 to 3
        do n2=0 to 3
         do n3=o to 3
           call CHECK-IF-QUALIFY-BEING-A-NEW-SUBSET(n1,n2,n3)
           if yes then output n1,n2,n3
          end
        end
      end

      In the above algorithm, each subset generated is a list of
pointers.  For instance, (0,1,2) is considered a subset with three
things - null, a pointer points to the first element (A), and a
pointer to the second element (B) of the set.

      The subroutine CHECK-IF-QUALIFY-BEING-A-NEW-SUBSET is used to
consider two subsets:
      (A,B) and (B,A)
      to be the same subsets, or even further,
      (0,1,2), (1,0,2), (1,1,2), (1,2,2), (2,1,1), (2,1,2),
      and (2,2,1) is identical.

      Thus, this subroutine will definitely require extensive
sorting, searching, and storage to keep track of the subsets
generated during its execution.  About its performance for a set with
N elements, this old method requires (N**N) iterations, that is, this
heavily comparison-involved subroutine will be called (N**N) times.
When the number of elements is big or N is a big number, the
performance of the generation process will become a major problem.

      To solved the above serious performance problem, we discovered
the following algorithm.  Its generated subsets contain only the
pointers.  This makes the method so generic that it can be applied to
any subset's generation. Moreover, this algorithm is very efficient
because it is an actual implementation of an observation.

      To describe the algorithm, we start with a list of subsets of
pointers to a set with five elements as shown below.  The O is
considered pointing to nothing, the 1 points to the first element of
the set, the 2 to the second element, and so on.
(0 0 0 0 1),
(0 0 0 0 2),
(0 0 0 0 3),
(0 0 0 0 4),
(0 0 0 0 5),
(0 0 0 1 2),
(0 0 0 1 3),
(0 0 0 1 4),
(0 0 0 1 5),
(0 0 0 2 3),
(0 0 0 2 4),
(0 0 0 2 5),
(0 0 0 3 4),
(0 0 0 3 5),
(0 0 0 4 5),
(0 0 1 2 3),
(0 0 1 2...