[UP]


Manual Reference Pages  - anagrams (1)

NAME

anagrams(1f) - print anagrams of strings

CONTENTS

Synopsis
Description
References
Examples

SYNOPSIS

anagrams string(s)

DESCRIPTION

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.

REFERENCES

Wikipedia

EXAMPLES

anagrams hello world


anagrams (1) March 11, 2021
Generated by manServer 1.08 from 25d23187-e845-4ad0-b466-5f44a32dcb27 using man macros.