Browse Prior Art Database

Algorithm to Exhaust m Out of n Combinations with Minimum Replacement

IP.com Disclosure Number: IPCOM000074722D
Original Publication Date: 1971-Jun-01
Included in the Prior Art Database: 2005-Feb-23
Document File: 4 page(s) / 88K

Publishing Venue

IBM

Related People

Liu, CN: AUTHOR [+2]

Abstract

These are three efficient algorithms to exhaust m out of n combinations with minimal replacement, where each produces a complete sequence of (n) combinations by single replacement.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 4

Algorithm to Exhaust m Out of n Combinations with Minimum Replacement

These are three efficient algorithms to exhaust m out of n combinations with minimal replacement, where each produces a complete sequence of (n) combinations by single replacement.

In many applications, it is required to find the "best" combination of m elements from a set of n (n > m) elements. Very frequently, the only way to solve this problem is to exhaustively examine all /n/(m) = n! over (n-m)!m! possible combinations of m elements. In those instances where /n/(m) is very large, it is of paramount importance that the computational time required to examine each combination be minimized. Since both the data and computational results related to the elements in a combination may be used in subsequent examination of other combinations, suboptimal replacements of elements invariably result in unnecessary memory transfers and computations. The algorithms disclosed efficiently generate all possible combinations of m elements with the property that between any two consecutive combinations of m elements, only a single element replacement is required.

For a set of n elements, it is well known that all combinations of m elements, 1</-m</-n, may be represented by n-bit binary vectors where a "1" in the ith position of a vector indicates the inclusion of the ith element in the combination. For example, given the set {4, 3, 2, 1}, (0001) represents the combination consisting of single element {1}, (0101) represents {3,1}, and (1101) represents {4,3,1}.

For a fixed value of m, each of the /n/(m) possible combinations of m elements is represented by an n-bit vector with exactly m "1"s. This set of n-bit vectors are referred to as constant weight (weight = m) n-tuples. Given the set of 2/n/ binary numbers represented by n-tuples (b b(n-2)...b(0)), the Gray code representation (g(n-1) g(n-2)...g(0)) is defined by g(n-1) = b(n-1) g(i) = b(i) + b(i+1) (mod 2), 0 </- i </- n-1 Given (g(n-1) g(n-2) ...g(0)), the binary equivalent may be obtained by

(Image Omitted)

It may be verified that in passing from any Gray code representation to an adjacent Gray code representation, in either direction, only the change of one bit is required. This is true also of the transition from the bottom of the column back to the top. The cyclic sequence of n-bit Gray code words is called n-bit Gray code circuit.

It can also be shown that on an n-bit Gray code circuit, consecutive constant weight (weight = m) n-tuples have a Hamming distance equal to 2 (this is illustrated by the underlined 4-tuples tabulated in the above example). Note that if this Gray code sequence of constant weight n-tuples is employed to represent the (/n/m) combinations of m elements, the difference between two consecutive combinations will be a single element.

1

Pa...