C Library Functions  - nextp (3)

NAME
nextp(3f) - [M_math] next permutation of a previously sorted integer array (LICENSE:PD)

CONTENTS

Synopsis
Description
Example
References
Written By
License

SYNOPSIS
subroutine nextp(n,a) 

   integer,parameter     :: dp=kind(0.0d0)
   integer,intent(in)    :: n
   integer,intent(inout) :: a(:)

DESCRIPTION
Permutation generation in lexicographic order

There are many ways to systematically generate all permutations of a given sequence. One classic, simple, and flexible algorithm is based upon finding the next permutation in lexicographic ordering, if it exists. It can handle repeated values, for which case it generates each distinct multiset permutation once. Even for ordinary permutations it is significantly more efficient than generating values for the Lehmer code in lexicographic order (possibly using the factorial number system) and converting those to permutations.

It begins by sorting the sequence in (weakly) increasing order (which gives its lexicographically minimal permutation), and then repeats advancing to the next permutation as long as one is found. The method goes back to Narayana Pandita in 14th century India, and has been rediscovered frequently.

The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place.

o Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
o Find the largest index l greater than k such that a[k] < a[l].
o Swap the value of a[k] with that of a[l].
o Reverse the sequence from a[k + 1] up to and including the final element a[n].

For example, given the sequence [10, 20, 30, 40] (which is in increasing order), and given that the index is one-based, the steps are as follows:
1) Index k = 3, because 30 is placed at an index that satisfies condition of being the largest index that is still less than a[k + 1] which is 40. if no such index exists no more permutations exist
2) Index l = 4, because 40 is the only value in the sequence that is greater than 30 in order to satisfy the condition a[k] < a[l].
3) The values of a[3] and a[4] are swapped to form the new sequence [10,20,40,30].
4) The sequence after k-index a[3] to the final element is reversed. Because only one value lies after this index (the 30), the sequence remains unchanged in this instance. Thus the lexicographic successor of the initial state is permuted: [10,20,40,30].
5) Following this algorithm, the next lexicographic permutation will be [10,30,20,40], and the 24th permutation will be [40,30,20,10] at which point a[k] < a[k + 1] does not exist, indicating that this is the last permutation.
This method uses about 3 comparisons and 1.5 swaps per permutation, amortized over the whole sequence, not counting the initial sort.

EXAMPLE

Sample program: 

      program demo_nextp
      use M_math, only : nextp
      integer,parameter :: n=4
      integer i,a(n)
      a=[(i,i=1,n)]  ! Must be sorted from smallest to largest
      do
         print *,(a(i),i=1,n)
         if(.not.nextp(n,a)) exit
      enddo
      end program demo_nextp

REFERENCES
Wikipedia

WRITTEN BY

LICENSE
Public Domain

Nemo Release 3.1 nextp (3) February 23, 2025
Generated by manServer 1.08 from e5c2613d-1c32-4862-8d81-4e37ff6883f8 using man macros.