Function std.algorithm.sorting.nextPermutation
Permutes range
The predicate less defines the lexicographical ordering to be used on
the range.
If the range is currently the lexicographically greatest permutation, it is
permuted back to the least permutation and false is returned. Otherwise,
true is returned. One can thus generate all permutations of a range by
sorting it according to less, which produces the lexicographically
least permutation, and then calling nextPermutation until it returns false.
This is guaranteed to generate all distinct permutations of the range
exactly once. If there are N elements in the range and all of them are
unique, then N! permutations will be generated. Otherwise, if there are
some duplicated elements, fewer permutations will be produced.
// Enumerate all permutations
int[] a = [1,2,3,4,5];
do
{
// use the current permutation and
// proceed to the next permutation of the array.
} while (nextPermutation(a));
Prototype
bool nextPermutation(alias less, BidirectionalRange)( BidirectionalRange range ) if (isBidirectionalRange!BidirectionalRange && hasSwappableElements!BidirectionalRange);
Parameters
| Name | Description |
|---|---|
| less | The ordering to be used to determine lexicographical ordering of the permutations. |
| range | The range to permute. |
Returns
false if the range was lexicographically the greatest, in which
case the range is reversed back to the lexicographically smallest
permutation; otherwise returns true.
See Also
Example
// Step through all permutations of a sorted array in lexicographic order int[] a = [1,2,3]; assert(nextPermutation(a) == true); assert(a == [1,3,2]); assert(nextPermutation(a) == true); assert(a == [2,1,3]); assert(nextPermutation(a) == true); assert(a == [2,3,1]); assert(nextPermutation(a) == true); assert(a == [3,1,2]); assert(nextPermutation(a) == true); assert(a == [3,2,1]); assert(nextPermutation(a) == false); assert(a == [1,2,3]);
Example
// Step through permutations of an array containing duplicate elements: int[] a = [1,1,2]; assert(nextPermutation(a) == true); assert(a == [1,2,1]); assert(nextPermutation(a) == true); assert(a == [2,1,1]); assert(nextPermutation(a) == false); assert(a == [1,1,2]);