Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Techniques to 1) Map A Permutation of an Arbitrary Base Sequence to a Decimal Index, and 2) Identify the Index of a Permutation of a Base Sequence

IP.com Disclosure Number: IPCOM000015502D
Original Publication Date: 2002-Jan-28
Included in the Prior Art Database: 2003-Jun-20
Document File: 3 page(s) / 46K

Publishing Venue

IBM

Abstract

Disclosed is a set of algorithms that, for a base sequence of symbols (N), permit the generation of the Kth permutation of N! permutations from the base sequence, 1. 2.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 76% of the total text.

Page 1 of 3

  Techniques to 1) Map A Permutation of an Arbitrary Base Sequence to a Decimal Index, and 2) Identify the Index of a Permutation of a Base Sequence

Disclosed is a set of algorithms that, for a base sequence of symbols (N), permit

the generation of the Kth permutation of N! permutations from the base sequence,


1.


2.


1.


2.


3.


4.

Note that in a production implementation in Java, the size of the factorials involved will require use of BigInteger objects, rather than long language primitives.

Algorithm 1 (using Java) : Converting a decimal index (K) into a mixed radix array of length N

long [] decimal2MixedRadix(int N, long K) {
long [] mr = new long[N];
long remainder = K;
longf=N-1;
for (int pos = 0; pos < K-1; pos++) {
long ff = factorial(f--);
mr[pos-1] = remainder / ff;
remainder %= ff;

and

the inverse function, i.e. determining K for a particular permutation of the base

sequence.

The permutations, when enumerated, will correspond to the standard lexicographic ordering of a permutation family. In addition, the set of algorithms have additional properties:

The base sequence does not have to be ordered. The base sequence is not limited to single instances of symbol types.

The algorithms treat the permutation as a mixed-radix number, of increasing base, from base 0 to base N-1 (where N is the length of the base sequence). The use of the mixed-radix representation permits the computation of the inverse of the permutation computation.

There are four key algorithms to performi...