This is a submodule of std.algorithm
. It contains generic sorting algorithms.
Function Name  Description 

completeSort  If a = [10, 20, 30] and b = [40, 6, 15] , then completeSort(a, b) leaves a = [6, 10, 15] and b = [20, 30, 40] . The range a must be sorted prior to the call, and as a result the combination std.range.chain(a, b) is sorted. 
isPartitioned  isPartitioned!"a < 0"([1, 2, 1, 0, 2]) returns true because the predicate is true for a portion of the range and false afterwards. 
isSorted  isSorted([1, 1, 2, 3]) returns true . 
isStrictlyMonotonic  isStrictlyMonotonic([1, 1, 2, 3]) returns false . 
ordered  ordered(1, 1, 2, 3) returns true . 
strictlyOrdered  strictlyOrdered(1, 1, 2, 3) returns false . 
makeIndex  Creates a separate index for a range. 
merge  Lazily merges two or more sorted ranges. 
multiSort  Sorts by multiple keys. 
nextEvenPermutation  Computes the next lexicographically greater even permutation of a range inplace. 
nextPermutation  Computes the next lexicographically greater permutation of a range inplace. 
partialSort  If a = [5, 4, 3, 2, 1] , then partialSort(a, 3) leaves a[0 .. 3] = [1, 2, 3] . The other elements of a are left in an unspecified order. 
partition  Partitions a range according to a unary predicate. 
partition3  Partitions a range according to a binary predicate in three parts (less than, equal, greater than the given pivot). Pivot is not given as an index, but instead as an element independent from the range's content. 
pivotPartition  Partitions a range according to a binary predicate in two parts: less than or equal, and greater than or equal to the given pivot, passed as an index in the range. 
schwartzSort  Sorts with the help of the Schwartzian transform. 
sort  Sorts. 
topN  Separates the top elements in a range. 
topNCopy  Copies out the top elements of a range. 
topNIndex  Builds an index of the top elements of a range. 
Specifies whether the output of certain algorithm is desired in sorted format.
If set to SortOutput.no
, the output should not be sorted.
Otherwise if set to SortOutput.yes
, the output should be sorted.
Sorts the randomaccess range chain(lhs, rhs)
according to predicate less
. The lefthand side of the range lhs
is assumed to be already sorted; rhs
is assumed to be unsorted. The exact strategy chosen depends on the relative sizes of lhs
and rhs
. Performs Ο(lhs.length + rhs.length * log(rhs.length)
) (best case) to Ο((lhs.length + rhs.length) * log(lhs.length + rhs.length)
) (worstcase) evaluations of swap
.
less  The predicate to sort by. 
ss  The swapping strategy to use. 
SortedRange!(Lhs, less) lhs
 The sorted, lefthand side of the random access range to be sorted. 
Rhs rhs
 The unsorted, righthand side of the random access range to be sorted. 
import std.range : assumeSorted; int[] a = [ 1, 2, 3 ]; int[] b = [ 4, 0, 6, 5 ]; completeSort(assumeSorted(a), b); writeln(a); // [0, 1, 2] writeln(b); // [3, 4, 5, 6]
Checks whether a forward range is sorted according to the comparison operation less
. Performs Ο(r.length
) evaluations of less
.
Unlike isSorted
, isStrictlyMonotonic
does not allow for equal values, i.e. values for which both less(a, b)
and less(b, a)
are false.
With either function, the predicate must be a strict ordering just like with isSorted
. For example, using "a <= b"
instead of "a < b"
is incorrect and will cause failed assertions.
less  Predicate the range should be sorted by. 
Range r
 Forward range to check for sortedness. 
true
if the range is sorted, false otherwise. isSorted
allows duplicates, isStrictlyMonotonic
not.assert([1, 1, 2].isSorted); // strictly monotonic doesn't allow duplicates assert(![1, 1, 2].isStrictlyMonotonic); int[] arr = [4, 3, 2, 1]; assert(!isSorted(arr)); assert(!isStrictlyMonotonic(arr)); assert(isSorted!"a > b"(arr)); assert(isStrictlyMonotonic!"a > b"(arr)); sort(arr); assert(isSorted(arr)); assert(isStrictlyMonotonic(arr));
Like isSorted
, returns true
if the given values
are ordered according to the comparison operation less
. Unlike isSorted
, takes values directly instead of structured in a range.
ordered
allows repeated values, e.g. ordered(1, 1, 2)
is true
. To verify that the values are ordered strictly monotonically, use strictlyOrdered
; strictlyOrdered(1, 1, 2)
is false
.
With either function, the predicate must be a strict ordering. For example, using "a <= b"
instead of "a < b"
is incorrect and will cause failed assertions.
T values
 The tested value 
less  The comparison predicate 
true
if the values are ordered; ordered
allows for duplicates, strictlyOrdered
does not.assert(ordered(42, 42, 43)); assert(!strictlyOrdered(43, 42, 45)); assert(ordered(42, 42, 43)); assert(!strictlyOrdered(42, 42, 43)); assert(!ordered(43, 42, 45)); // Ordered lexicographically assert(ordered("Jane", "Jim", "Joe")); assert(strictlyOrdered("Jane", "Jim", "Joe")); // Incidentally also ordered by length decreasing assert(ordered!((a, b) => a.length > b.length)("Jane", "Jim", "Joe")); // ... but not strictly so: "Jim" and "Joe" have the same length assert(!strictlyOrdered!((a, b) => a.length > b.length)("Jane", "Jim", "Joe"));
Partitions a range in two using the given predicate
. Specifically, reorders the range r = [left, right)
using swap
such that all elements i
for which predicate(i)
is true
come before all elements j
for which predicate(j)
returns false
.
Performs Ο(r.length
) (if unstable or semistable) or Ο(r.length * log(r.length)
) (if stable) evaluations of less
and swap
. The unstable version computes the minimum possible evaluations of swap
(roughly half of those performed by the semistable version).
predicate  The predicate to partition by. 
ss  The swapping strategy to employ. 
Range r
 The randomaccess range to partition. 
r
after partitioning. If ss == SwapStrategy.stable
, partition
preserves the relative ordering of all elements a
, b
in r
for which predicate(a) == predicate(b)
. If ss == SwapStrategy.semistable
, partition
preserves the relative ordering of all elements a
, b
in the left part of r
for which predicate(a) == predicate(b)
.import std.algorithm.mutation : SwapStrategy; import std.algorithm.searching : count, find; import std.conv : text; import std.range.primitives : empty; auto Arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]; auto arr = Arr.dup; static bool even(int a) { return (a & 1) == 0; } // Partition arr such that even numbers come first auto r = partition!(even)(arr); // Now arr is separated in evens and odds. // Numbers may have become shuffled due to instability writeln(r); // arr[5 .. $] writeln(count!(even)(arr[0 .. 5])); // 5 assert(find!(even)(r).empty); // Can also specify the predicate as a string. // Use 'a' as the predicate argument name arr[] = Arr[]; r = partition!(q{(a & 1) == 0})(arr); writeln(r); // arr[5 .. $] // Now for a stable partition: arr[] = Arr[]; r = partition!(q{(a & 1) == 0}, SwapStrategy.stable)(arr); // Now arr is [2 4 6 8 10 1 3 5 7 9], and r points to 1 assert(arr == [2, 4, 6, 8, 10, 1, 3, 5, 7, 9] && r == arr[5 .. $]); // In case the predicate needs to hold its own state, use a delegate: arr[] = Arr[]; int x = 3; // Put stuff greater than 3 on the left bool fun(int a) { return a > x; } r = partition!(fun, SwapStrategy.semistable)(arr); // Now arr is [4 5 6 7 8 9 10 2 3 1] and r points to 2 assert(arr == [4, 5, 6, 7, 8, 9, 10, 2, 3, 1] && r == arr[7 .. $]);
Partitions r
around pivot
using comparison function less
, algorithm akin to Hoare partition. Specifically, permutes elements of r
and returns an index k < r.length
such that:
r[pivot]
is swapped to r[k]
e
in subrange r[0 .. k]
satisfy !less(r[k], e)
(i.e. r[k]
is greater than or equal to each element to its left according to predicate less
)e
in subrange r[k .. $]
satisfy !less(e, r[k])
(i.e. r[k]
is less than or equal to each element to its right according to predicate less
)r
contains equivalent elements, multiple permutations of r
satisfy these constraints. In such cases, pivotPartition
attempts to distribute equivalent elements fairly to the left and right of k
such that k
stays close to r.length / 2
. less  The predicate used for comparison, modeled as a strict weak ordering (irreflexive, antisymmetric, transitive, and implying a transitive equivalence) 
Range r
 The range being partitioned 
size_t pivot
 The index of the pivot for partitioning, must be less than r.length or 0 is r.length is 0

int[] a = [5, 3, 2, 6, 4, 1, 3, 7]; size_t pivot = pivotPartition(a, a.length / 2); import std.algorithm.searching : all; assert(a[0 .. pivot].all!(x => x <= a[pivot])); assert(a[pivot .. $].all!(x => x >= a[pivot]));
pred  The predicate that the range should be partitioned by. 
Range r
 The range to check. 
true
if r
is partitioned according to predicate pred
.int[] r = [ 1, 3, 5, 7, 8, 2, 4, ]; assert(isPartitioned!"a & 1"(r));
Rearranges elements in r
in three adjacent ranges and returns them. The first and leftmost range only contains elements in r
less than pivot
. The second and middle range only contains elements in r
that are equal to pivot
. Finally, the third and rightmost range only contains elements in r
that are greater than pivot
. The lessthan test is defined by the binary function less
.
less  The predicate to use for the rearrangement. 
ss  The swapping strategy to use. 
Range r
 The randomaccess range to rearrange. 
E pivot
 The pivot element. 
std.typecons.Tuple
of the three resulting ranges. These ranges are slices of the original range. partition3
has not been implemented yet.auto a = [ 8, 3, 4, 1, 4, 7, 4 ]; auto pieces = partition3(a, 4); writeln(pieces[0]); // [1, 3] writeln(pieces[1]); // [4, 4, 4] writeln(pieces[2]); // [8, 7]
Computes an index for r
based on the comparison less
. The index is a sorted array of pointers or indices into the original range. This technique is similar to sorting, but it is more flexible because (1) it allows "sorting" of immutable collections, (2) allows binary search even if the original collection does not offer random access, (3) allows multiple indexes, each on a different predicate, and (4) may be faster when dealing with large objects. However, using an index may also be slower under certain circumstances due to the extra indirection, and is always larger than a sortingbased solution because it needs space for the index in addition to the original collection. The complexity is the same as sort
's.
The first overload of makeIndex
writes to a range containing pointers, and the second writes to a range containing offsets. The first overload requires Range
to be a forward range, and the latter requires it to be a randomaccess range.
makeIndex
overwrites its second argument with the result, but never reallocates it.
less  The comparison to use. 
ss  The swapping strategy. 
Range r
 The range to index. 
RangeIndex index
 The resulting index. 
SortedRange
wrapper over index, of type SortedRange!(RangeIndex, (a, b) => binaryFun!less(*a, *b))
thus reflecting the ordering of the index. The indexbased version returns void
because the ordering relation involves not only index
but also r
. immutable(int[]) arr = [ 2, 3, 1, 5, 0 ]; // index using pointers auto index1 = new immutable(int)*[arr.length]; makeIndex!("a < b")(arr, index1); assert(isSorted!("*a < *b")(index1)); // index using offsets auto index2 = new size_t[arr.length]; makeIndex!("a < b")(arr, index2); assert(isSorted! ((size_t a, size_t b){ return arr[a] < arr[b];}) (index2));
Merge multiple sorted ranges rs
with lessthan predicate function pred
into one single sorted output range containing the sorted union of the elements of inputs. Duplicates are not eliminated, meaning that the total number of elements in the output is the sum of all elements in the ranges passed to it; the length
member is offered if all inputs also have length
. The element types of all the inputs must have a common type CommonType
.
less  Predicate the given ranges are sorted by. 
Rs rs
 The ranges to compute the union for. 
std.range.SortedRange
. Use the result of std.algorithm.sorting.sort
, or std.range.assumeSorted
to merge ranges known to be sorted (show in the example below). Note that there is currently no way of ensuring that two or more instances of std.range.SortedRange
are sorted using a specific comparison function pred
. Therefore no checking is done here to assure that all inputs rs
are instances of std.range.SortedRange
. ref
, output becomes a range with mutable front
(and back
where appropriate) that reflects in the original inputs. If any of the inputs rs
is infinite so is the result (empty
being always false
). import std.algorithm.comparison : equal; import std.range : retro; int[] a = [1, 3, 5]; int[] b = [2, 3, 4]; assert(a.merge(b).equal([1, 2, 3, 3, 4, 5])); assert(a.merge(b).retro.equal([5, 4, 3, 3, 2, 1]));
import std.algorithm.comparison : equal; import std.range : retro; import std.traits : CommonType; alias S = short; alias I = int; alias D = double; S[] a = [1, 2, 3]; I[] b = [50, 60]; D[] c = [10, 20, 30, 40]; auto m = merge(a, b, c); static assert(is(typeof(m.front) == CommonType!(S, I, D))); assert(equal(m, [1, 2, 3, 10, 20, 30, 40, 50, 60])); assert(equal(m.retro, [60, 50, 40, 30, 20, 10, 3, 2, 1])); m.popFront(); assert(equal(m, [2, 3, 10, 20, 30, 40, 50, 60])); m.popBack(); assert(equal(m, [2, 3, 10, 20, 30, 40, 50])); m.popFront(); assert(equal(m, [3, 10, 20, 30, 40, 50])); m.popBack(); assert(equal(m, [3, 10, 20, 30, 40])); m.popFront(); assert(equal(m, [10, 20, 30, 40])); m.popBack(); assert(equal(m, [10, 20, 30])); m.popFront(); assert(equal(m, [20, 30])); m.popBack(); assert(equal(m, [20])); m.popFront(); assert(m.empty);
Sorts a range by multiple keys. The call multiSort!("a.id < b.id", "a.date > b.date")(r)
sorts the range r
by id
ascending, and sorts elements that have the same id
by date
descending. Such a call is equivalent to sort!"a.id != b.id ? a.id < b.id : a.date > b.date"(r)
, but multiSort
is faster because it does fewer comparisons (in addition to being more convenient).
SortedRange
with its predicates converted to an equivalent single predicate.import std.algorithm.mutation : SwapStrategy; static struct Point { int x, y; } auto pts1 = [ Point(0, 0), Point(5, 5), Point(0, 1), Point(0, 2) ]; auto pts2 = [ Point(0, 0), Point(0, 1), Point(0, 2), Point(5, 5) ]; multiSort!("a.x < b.x", "a.y < b.y", SwapStrategy.unstable)(pts1); writeln(pts1); // pts2
Sorts a randomaccess range according to the predicate less
. Performs Ο(r.length * log(r.length)
) evaluations of less
. If less
involves expensive computations on the sort key, it may be worthwhile to use schwartzSort
instead.
Stable sorting requires hasAssignableElements!Range
to be true.
sort
returns a std.range.SortedRange
over the original range, allowing functions that can take advantage of sorted data to know that the range is sorted and adjust accordingly. The std.range.SortedRange
is a wrapper around the original range, so both it and the original range are sorted. Other functions can't know that the original range has been sorted, but they can know that std.range.SortedRange
has been sorted.
sort
to behave as expected  otherwise, the program may fail on certain inputs (but not others) when not compiled in release mode, due to the cursory assumeSorted
check. Specifically, sort
expects less(a,b) && less(b,c)
to imply less(a,c)
(transitivity), and, conversely, !less(a,b) && !less(b,c)
to imply !less(a,c)
. Note that the default predicate ("a < b"
) does not always satisfy these conditions for floating point types, because the expression will always be false
when either a
or b
is NaN. Use std.math.cmp
instead. less  The predicate to sort by. 
ss  The swapping strategy to use. 
Range r
 The range to sort. 
SortedRange
with the predicate binaryFun!less
. n log n
) worstcase time complexity. std.range.assumeSorted
std.range.SortedRange
std.algorithm.mutation.SwapStrategy
std.functional.binaryFun
int[] array = [ 1, 2, 3, 4 ]; // sort in descending order array.sort!("a > b"); writeln(array); // [4, 3, 2, 1] // sort in ascending order array.sort(); writeln(array); // [1, 2, 3, 4] // sort with reusable comparator and chain alias myComp = (x, y) => x > y; writeln(array.sort!(myComp).release); // [4, 3, 2, 1]
// Showcase stable sorting import std.algorithm.mutation : SwapStrategy; string[] words = [ "aBc", "a", "abc", "b", "ABC", "c" ]; sort!("toUpper(a) < toUpper(b)", SwapStrategy.stable)(words); writeln(words); // ["a", "aBc", "abc", "ABC", "b", "c"]
// Sorting floatingpoint numbers in presence of NaN double[] numbers = [0.0, 3.0, 2.0, double.nan, 0.0, double.nan]; import std.algorithm.comparison : equal; import std.math : cmp, isIdentical; sort!((a, b) => cmp(a, b) < 0)(numbers); double[] sorted = [double.nan, 2.0, 0.0, 0.0, 3.0, double.nan]; assert(numbers.equal!isIdentical(sorted));
Alternative sorting method that should be used when comparing keys involves an expensive computation. Instead of using less(a, b)
for comparing elements, schwartzSort
uses less(transform(a), transform(b))
. The values of the transform
function are precomputed in a temporary array, thus saving on repeatedly computing it. Conversely, if the cost of transform
is small compared to the cost of allocating and filling the precomputed array, sort
may be faster and therefore preferable.
This approach to sorting is akin to the Schwartzian transform, also known as the decoratesortundecorate pattern in Python and Lisp. The complexity is the same as that of the corresponding sort
, but schwartzSort
evaluates transform
only r.length
times (less than half when compared to regular sorting). The usage can be best illustrated with an example.
uint hashFun(string) { ... expensive computation ... } string[] array = ...; // Sort strings by hash, slow sort!((a, b) => hashFun(a) < hashFun(b))(array); // Sort strings by hash, fast (only computes arr.length hashes): schwartzSort!(hashFun, "a < b")(array);The
schwartzSort
function might require less temporary data and be faster than the Perl idiom or the decoratesortundecorate idiom present in Python and Lisp. This is because sorting is done inplace and only minimal extra data (one array of transformed elements) is created. To check whether an array was sorted and benefit of the speedup of Schwartz sorting, a function schwartzIsSorted
is not provided because the effect can be achieved by calling isSorted!less(map!transform(r))
. transform  The transformation to apply. 
less  The predicate to sort by. 
ss  The swapping strategy to use. 
R r
 The range to sort. 
SortedRange
with the predicate (a, b) => binaryFun!less(transform(a), transform(b))
.import std.algorithm.iteration : map; import std.numeric : entropy; auto lowEnt = [ 1.0, 0, 0 ], midEnt = [ 0.1, 0.1, 0.8 ], highEnt = [ 0.31, 0.29, 0.4 ]; auto arr = new double[][3]; arr[0] = midEnt; arr[1] = lowEnt; arr[2] = highEnt; schwartzSort!(entropy, "a > b")(arr); writeln(arr[0]); // highEnt writeln(arr[1]); // midEnt writeln(arr[2]); // lowEnt assert(isSorted!("a > b")(map!(entropy)(arr)));
Reorders the randomaccess range r
such that the range r[0 .. mid]
is the same as if the entire r
were sorted, and leaves the range r[mid .. r.length]
in no particular order. Performs Ο(r.length * log(mid)
) evaluations of pred
. The implementation simply calls topN!(less, ss)(r, n)
and then sort!(less, ss)(r[0 .. n])
.
less  The predicate to sort by. 
ss  The swapping strategy to use. 
Range r
 The randomaccess range to reorder. 
size_t n
 The length of the initial segment of r to sort. 
int[] a = [ 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 ]; partialSort(a, 5); writeln(a[0 .. 5]); // [0, 1, 2, 3, 4]
Stores the smallest elements of the two ranges in the lefthand range in sorted order.
less  The predicate to sort by. 
ss  The swapping strategy to use. 
Range1 r1
 The first range. 
Range2 r2
 The second range. 
int[] a = [5, 7, 2, 6, 7]; int[] b = [2, 1, 5, 6, 7, 3, 0]; partialSort(a, b); writeln(a); // [0, 1, 2, 2, 3]
Reorders the range r
using swap
such that r[nth]
refers to the element that would fall there if the range were fully sorted. In addition, it also partitions r
such that all elements e1
from r[0]
to r[nth]
satisfy !less(r[nth], e1)
, and all elements e2
from r[nth]
to r[r.length]
satisfy !less(e2, r[nth])
. Effectively, it finds the nth smallest (according to less
) elements in r
. Performs an expected Ο(r.length
) (if unstable) or Ο(r.length * log(r.length)
) (if stable) evaluations of less
and swap
.
If n >= r.length
, the algorithm has no effect and returns r[0 .. r.length]
.
less  The predicate to sort by. 
ss  The swapping strategy to use. 
Range r
 The randomaccess range to reorder. 
size_t nth
 The index of the element that should be in sorted position after the function is done. 
topNIndex
, int[] v = [ 25, 7, 9, 2, 0, 5, 21 ]; topN!"a < b"(v, 100); writeln(v); // [25, 7, 9, 2, 0, 5, 21] auto n = 4; topN!((a, b) => a < b)(v, n); writeln(v[n]); // 9
Stores the smallest elements of the two ranges in the lefthand range.
less  The predicate to sort by. 
ss  The swapping strategy to use. 
Range1 r1
 The first range. 
Range2 r2
 The second range. 
int[] a = [ 5, 7, 2, 6, 7 ]; int[] b = [ 2, 1, 5, 6, 7, 3, 0 ]; topN(a, b); sort(a); writeln(a); // [0, 1, 2, 2, 3]
Copies the top n
elements of the input range source
into the randomaccess range target
, where n = target.length
. Elements of source
are not touched. If sorted
is true
, the target is sorted. Otherwise, the target respects the heap property.
less  The predicate to sort by. 
SRange source
 The source range. 
TRange target
 The target range. 
SortOutput sorted
 Whether to sort the elements copied into target . 
target
containing the copied elements.import std.typecons : Yes; int[] a = [ 10, 16, 2, 3, 1, 5, 0 ]; int[] b = new int[3]; topNCopy(a, b, Yes.sortOutput); writeln(b); // [0, 1, 2]
Given a range of elements, constructs an index of its top n elements (i.e., the first n elements if the range were sorted).
Similar to topN
, except that the range is not modified.
less  A binary predicate that defines the ordering of range elements. Defaults to a < b . 
ss  (Not implemented yet.) Specify the swapping strategy. 
Range r
 A randomaccess range of elements to make an index for. 
RangeIndex index
 A randomaccess range with assignable elements to build the index in. The length of this range determines how many top elements to index in r . This index range can either have integral elements, in which case the constructed index will consist of zerobased numerical indices into r ; or it can have pointers to the element type of r , in which case the constructed index will be pointers to the top elements in r . 
SortOutput sorted
 Determines whether to sort the index by the elements they refer to. 
import std.typecons : Yes; // Construct index to top 3 elements using numerical indices: int[] a = [ 10, 2, 7, 5, 8, 1 ]; int[] index = new int[3]; topNIndex(a, index, Yes.sortOutput); assert(index == [5, 1, 3]); // because a[5]==1, a[1]==2, a[3]==5 // Construct index to top 3 elements using pointer indices: int*[] ptrIndex = new int*[3]; topNIndex(a, ptrIndex, Yes.sortOutput); writeln(ptrIndex); // [&a[5], &a[1], &a[3]]
Permutes range
inplace to the next lexicographically greater permutation.
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));
less  The ordering to be used to determine lexicographical ordering of the permutations. 
BidirectionalRange range
 The range to permute. 
std.algorithm.iteration.permutations
.// Step through all permutations of a sorted array in lexicographic order int[] a = [1,2,3]; writeln(nextPermutation(a)); // true writeln(a); // [1, 3, 2] writeln(nextPermutation(a)); // true writeln(a); // [2, 1, 3] writeln(nextPermutation(a)); // true writeln(a); // [2, 3, 1] writeln(nextPermutation(a)); // true writeln(a); // [3, 1, 2] writeln(nextPermutation(a)); // true writeln(a); // [3, 2, 1] writeln(nextPermutation(a)); // false writeln(a); // [1, 2, 3]
// Step through permutations of an array containing duplicate elements: int[] a = [1,1,2]; writeln(nextPermutation(a)); // true writeln(a); // [1, 2, 1] writeln(nextPermutation(a)); // true writeln(a); // [2, 1, 1] writeln(nextPermutation(a)); // false writeln(a); // [1, 1, 2]
Permutes range
inplace to the next lexicographically greater even permutation.
The predicate less
defines the lexicographical ordering to be used on the range.
An even permutation is one which is produced by swapping an even number of pairs of elements in the original range. The set of even permutations is distinct from the set of all permutations only when there are no duplicate elements in the range. If the range has N unique elements, then there are exactly N!/2 even permutations.
If the range is already the lexicographically greatest even permutation, it is permuted back to the least even permutation and false is returned. Otherwise, true is returned, and the range is modified inplace to be the lexicographically next even permutation.
One can thus generate the even permutations of a range with unique elements by starting with the lexicographically smallest permutation, and repeatedly calling nextEvenPermutation until it returns false.
// Enumerate even permutations int[] a = [1,2,3,4,5]; do { // use the current permutation and // proceed to the next even permutation of the array. } while (nextEvenPermutation(a));One can also generate the odd permutations of a range by noting that permutations obey the rule that even + even = even, and odd + even = odd. Thus, by swapping the last two elements of a lexicographically least range, it is turned into the first odd permutation. Then calling nextEvenPermutation on this first odd permutation will generate the next even permutation relative to this odd permutation, which is actually the next odd permutation of the original range. Thus, by repeatedly calling nextEvenPermutation until it returns false, one enumerates the odd permutations of the original range.
// Enumerate odd permutations int[] a = [1,2,3,4,5]; swap(a[$2], a[$1]); // a is now the first odd permutation of [1,2,3,4,5] do { // use the current permutation and // proceed to the next odd permutation of the original array // (which is an even permutation of the first odd permutation). } while (nextEvenPermutation(a));
less  The ordering to be used to determine lexicographical ordering of the permutations. 
BidirectionalRange range
 The range to permute. 
// Step through even permutations of a sorted array in lexicographic order int[] a = [1,2,3]; writeln(nextEvenPermutation(a)); // true writeln(a); // [2, 3, 1] writeln(nextEvenPermutation(a)); // true writeln(a); // [3, 1, 2] writeln(nextEvenPermutation(a)); // false writeln(a); // [1, 2, 3]
import std.math : sqrt; // Print the 60 vertices of a uniform truncated icosahedron (soccer ball) enum real Phi = (1.0 + sqrt(5.0)) / 2.0; // Golden ratio real[][] seeds = [ [0.0, 1.0, 3.0*Phi], [1.0, 2.0+Phi, 2.0*Phi], [Phi, 2.0, Phi^^3] ]; size_t n; foreach (seed; seeds) { // Loop over even permutations of each seed do { // Loop over all sign changes of each permutation size_t i; do { // Generate all possible sign changes for (i=0; i < seed.length; i++) { if (seed[i] != 0.0) { seed[i] = seed[i]; if (seed[i] < 0.0) break; } } n++; } while (i < seed.length); } while (nextEvenPermutation(seed)); } writeln(n); // 60
© 1999–2018 The D Language Foundation
Licensed under the Boost License 1.0.
https://dlang.org/phobos/std_algorithm_sorting.html