Browse Prior Art Database

Generalized Factorial Number System and Permutations of K out of N

IP.com Disclosure Number: IPCOM000081949D
Original Publication Date: 1974-Sep-01
Included in the Prior Art Database: 2005-Feb-28
Document File: 2 page(s) / 64K

Publishing Venue

IBM

Related People

Kellerman, E: AUTHOR

Abstract

Described is a representation for integers which permits a one-to-one correspondence to be established between the N!/(NK)! permutations of K out of N objects and the first N!/(NK)! nonnegative integers, thus providing a way for some of the existing algorithms for generating permutations of K objects to be used for generating permutations of K out of N objects. This representation will be called the "Generalized Factorial Representation" (GFR). Given integers K and N, with 0

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 91% of the total text.

Page 1 of 2

Generalized Factorial Number System and Permutations of K out of N

Described is a representation for integers which permits a one-to-one correspondence to be established between the N!/(NK)! permutations of K out of N objects and the first N!/(NK)! nonnegative integers, thus providing a way for some of the existing algorithms for generating permutations of K objects to be used for generating permutations of K out of N objects. This representation will be called the "Generalized Factorial Representation" (GFR). Given integers K and N, with 0</-K</-N, the GFR of an integer I is defined by:

(Image Omitted)

An Algorithm for determining the GFR of an integer 1 is given below. The inputs to the algorithm are the integers 1, K, and N. The variables Q and X are used during the computations. The output of the algorithm is the generalized factorial digits:

(Image Omitted)

To compute the B's for 1=15 it is first necessary to divide by 3 (i.e., NK+1) and obtain a remainder of B(0)=3. The quotient, 4, is then divided by 4, obtaining a remainder of B(1)=0. The new quotient, 1, is then divided by 5, and a remainder of B(2)=1 is obtained.

To generate the permutations of K out of N objects, it is only necessary to establish a one-to-one correspondence between the permutations of K out of N objects, and the generalized factorial digits for the integers 0, 1, ..., N! over (NK)!) -1. This situation resembles the already solved problem of associating the factorial digits with the dif...