Browse Prior Art Database

Generation of Permutations and an APL Implementation

IP.com Disclosure Number: IPCOM000077874D
Original Publication Date: 1972-Oct-01
Included in the Prior Art Database: 2005-Feb-25
Document File: 1 page(s) / 11K

Publishing Venue

IBM

Related People

Kellerman, E: AUTHOR [+2]

Abstract

This algorithm makes it possible to generate the next permutation of N out of the first M numbers, directly from the results of the previous permutation. Prior solutions to this problem required that a selection of objects be made (using an algorithm for generation of combinations) and then to permutate these selected objects. This algorithm does not use factorials, which can become quite large, and in many cases exceed available storage.

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

Page 1 of 1

Generation of Permutations and an APL Implementation

This algorithm makes it possible to generate the next permutation of N out of the first M numbers, directly from the results of the previous permutation. Prior solutions to this problem required that a selection of objects be made (using an algorithm for generation of combinations) and then to permutate these selected objects. This algorithm does not use factorials, which can become quite large, and in many cases exceed available storage.

The vector V consists of integers between 1 and M, with no repetitions, and its elements are used as pointers to the objects being permuted.

The steps of the algorithm are:
1) Let NN equal the number of objects to be selected (that is,

the value of N).
2) Check the last element of V to see if it is equal to M.
3) Drop the last element from V, set NN equal to the new size

of V, and if NN is not equal to zero, return to Step 2.
4) Let V equal 1, 2, ... N (the new permutation of N out of

M elements) and exit from the routine.
5) Increase the last element of V by one. If this element

already exists in V, then return to Step 2.
6) Exit from the routine if NN=N.
7) Concatenate a 0 onto V, set NN equal to the new size of V,

and return to Step 5.

If V=(1, 2) and permute 2 out of 3 elements, the next permutations found are (1, 3), (2, 1), (2, 3), (3, 1), (3, 2), and (1, 2).

1