| Function Name | Description |
|---|---|
| completeSort | Ifa = [10, 20, 30] andb = [40, 6, 15], thencompleteSort(a, b) leavesa = [6, 10, 15] andb = [20, 30, 40]. The rangea must be sorted prior to the call, and as a result the combinationstd.range.chain(a, b) is sorted. |
| isPartitioned | isPartitioned!"a < 0"([-1, -2, 1, 0, 2]) returnstrue because the predicate istrue for a portion of the range andfalse afterwards. |
| isSorted | isSorted([1, 1, 2, 3]) returnstrue. |
| isStrictlyMonotonic | isStrictlyMonotonic([1, 1, 2, 3]) returnsfalse. |
| ordered | ordered(1, 1, 2, 3) returnstrue. |
| strictlyOrdered | strictlyOrdered(1, 1, 2, 3) returnsfalse. |
| 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 in-place. |
| nextPermutation | Computes the next lexicographically greater permutation of a range in-place. |
| nthPermutation | Computes the nth permutation of a range in-place. |
| partialSort | Ifa = [5, 4, 3, 2, 1], thenpartialSort(a, 3) leavesa[0 .. 3] = [1, 2, 3]. The other elements ofa 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 theSchwartzian transform. |
| sort | Sorts. |
| topN | Separates the top elements in a range, akin toQuickselect. |
| topNCopy | Copies out the top elements of a range. |
| topNIndex | Builds an index of the top elements of a range. |
Sourcestd/algorithm/sorting.d
SortOutput = std.typecons.Flag!"sortOutput".Flag;SortOutput.no, the output should not be sorted.Otherwise if set toSortOutput.yes, the output should be sorted.completeSort(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Lhs, Rhs)(SortedRange!(Lhs, less)lhs, Rhsrhs)lhs,rhs) according topredicateless.lhs is assumed to be already sorted;rhs is assumed to be unsorted.The exact strategy chosen depends on the relative sizes oflhs andrhs. PerformsΟ(lhs.length + rhs.length * log(rhs.length))(best case) toΟ((lhs.length + rhs.length) * log(lhs.length +rhs.length)) (worst-case) evaluations ofswap.| less | The predicate to sort by. |
| ss | The swapping strategy to use. |
SortedRange!(Lhs, less)lhs | The sorted, left-hand side of the random access range to be sorted. |
Rhsrhs | The unsorted, right-hand 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]
isSorted(alias less = "a < b", Range)(Ranger)isStrictlyMonotonic(alias less = "a < b", Range)(Ranger)isSorted,isStrictlyMonotonic does not allow for equal values,i.e. values for which bothless(a, b) andless(b, a) are false.With either function, the predicate must be a strict ordering just like withisSorted. For example, using"a <= b" instead of"a < b" isincorrect and will cause failed assertions.| less | Predicate the range should be sorted by. |
Ranger | Forward range to check for sortedness. |
isSorted allows duplicates,isStrictlyMonotonic not.assert([1, 1, 2].isSorted);// strictly monotonic doesn't allow duplicatesassert(![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));
ordered(alias less = "a < b", T...)(Tvalues)values[1],values[0])) : bool) || T.length > 2 && is(typeof(ordered!less(values[0..1 + $ / 2]))) && is(typeof(ordered!less(values[$ / 2..$]))));strictlyOrdered(alias less = "a < b", T...)(Tvalues)values))));values are orderedaccording to the comparison operationless. UnlikeisSorted, takes valuesdirectly instead of structured in a range.ordered allows repeated values, e.g.ordered(1, 1, 2) istrue. To verifythat the values are ordered strictly monotonically, usestrictlyOrdered;strictlyOrdered(1, 1, 2) isfalse.With either function, the predicate must be a strict ordering. For example,using"a <= b" instead of"a < b" is incorrect and will cause failedassertions.Tvalues | The tested value |
| less | The comparison predicate |
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 lexicographicallyassert(ordered("Jane","Jim","Joe"));assert(strictlyOrdered("Jane","Jim","Joe"));// Incidentally also ordered by length decreasingassert(ordered!((a, b) => a.length > b.length)("Jane","Jim","Joe"));// ... but not strictly so: "Jim" and "Joe" have the same lengthassert(!strictlyOrdered!((a, b) => a.length > b.length)("Jane","Jim","Joe"));
partition(alias predicate, SwapStrategy ss, Range)(Ranger)partition(alias predicate, SwapStrategy ss = SwapStrategy.unstable, Range)(Ranger)r = [left, right) usingswapsuch that all elementsi for whichpredicate(i) istrue comebefore all elementsj for whichpredicate(j) returnsfalse.PerformsΟ(r.length) (if unstable or semistable) orΟ(r.length * log(r.length)) (if stable) evaluations ofless andswap.The unstable version computes the minimum possible evaluations ofswap(roughly half of those performed by the semistable version).| predicate | The predicate to partition by. |
| ss | The swapping strategy to employ. |
Ranger | The random-access range to partition. |
r after partitioning.Ifss == SwapStrategy.stable,partition preserves the relativeordering of all elementsa,b inr for whichpredicate(a) == predicate(b).Ifss == SwapStrategy.semistable,partition preservesthe relative ordering of all elementsa,b in the left part ofrfor whichpredicate(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;staticbool even(int a) {return (a & 1) == 0; }// Partition arr such that even numbers come firstautor =partition!(even)(arr);// Now arr is separated in evens and odds.// Numbers may have become shuffled due to instabilitywriteln(r);// arr[5 .. $]writeln(count!(even)(arr[0 .. 5]));// 5assert(find!(even)(r).empty);// Can also specify the predicate as a string.// Use 'a' as the predicate argument namearr[] = 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 1assert(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 leftbool 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 2assert(arr == [4, 5, 6, 7, 8, 9, 10, 2, 3, 1] &&r == arr[7 .. $]);
pivotPartition(alias less = "a < b", Range)(Ranger, size_tpivot)r and returnsan indexk <r.length such that:r[pivot] is swapped tor[k]r[0 .. k] satisfy!less(r[k], e)(i.e.r[k] is greater than or equal to each element to its left according topredicateless)r[k .. $] satisfy!less(e,r[k])(i.e.r[k] is less than or equal to each element to its rightaccording to predicateless)r contains equivalent elements, multiple permutations ofr satisfy theseconstraints. In such cases,pivotPartition attempts to distribute equivalentelements fairly to the left and right ofk such thatk stays close tor.length / 2.| less | The predicate used for comparison, modeled as a strict weak ordering (irreflexive, antisymmetric, transitive, and implying a transitive equivalence) |
Ranger | The range being partitioned |
size_tpivot | The index of the pivot for partitioning, must be less thanr.length or0 ifr.length is0 |
int[] a = [5, 3, 2, 6, 4, 1, 3, 7];size_tpivot =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]));
isPartitioned(alias pred, Range)(Ranger)| pred | The predicate that the range should be partitioned by. |
Ranger | The range to check. |
r is partitioned according to predicatepred.int[]r = [ 1, 3, 5, 7, 8, 2, 4, ];assert(isPartitioned!"a & 1"(r));
partition3(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range, E)(Ranger, Epivot)r.front,pivot)) == bool) && is(typeof(binaryFun!less(pivot,r.front)) == bool) && is(typeof(binaryFun!less(r.front,r.front)) == bool));r in three adjacent ranges and returnsthem.rless thanpivot. The second and middle range only containselements inr that are equal topivot. Finally, the thirdand rightmost range only contains elements inr that are greaterthanpivot. The less-than test is defined by the binary functionless.| less | The predicate to use for the rearrangement. |
| ss | The swapping strategy to use. |
Ranger | The random-access range to rearrange. |
Epivot | The pivot element. |
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]
makeIndex(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range, RangeIndex)(Ranger, RangeIndexindex)makeIndex(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range, RangeIndex)(Ranger, RangeIndexindex)r based on the comparisonless.makeIndex writes to a range containingpointers, and the second writes to a range containing offsets. Thefirst overload requiresRange to be aforward range, and thelatter requires it to be a random-access range.makeIndex overwrites its second argument with the result, butnever reallocates it.| less | The comparison to use. |
| ss | The swapping strategy. |
Ranger | The range to index. |
RangeIndexindex | The resulting index. |
index but alsor.immutable(int[]) arr = [ 2, 3, 1, 5, 0 ];// index using pointersauto index1 =newimmutable(int)*[arr.length];makeIndex!("a < b")(arr, index1);assert(isSorted!("*a < *b")(index1));// index using offsetsauto 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(alias less = "a < b", Rs...)(Rsrs)rs with less-than predicate functionpred into one single sorted output range containing the sorted union of the elements of inputs.| less | Predicate the given ranges are sorted by. |
Rsrs | The ranges to compute the union for. |
DetailsAll of its inputs are assumed to be sorted. This can mean that inputs are instances ofstd.range.SortedRange. Use the result of std.algorithm.sorting.sort, orstd.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 functionpred. Therefore no checking is done here to assure that all inputsrs are instances ofstd.range.SortedRange.
rs is infinite so is the result (empty being alwaysfalse).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);staticassert(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);
multiSort(less...)multiSort is faster because itdoes fewer comparisons (in addition to being more convenient).import std.algorithm.mutation : SwapStrategy;staticstruct 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
sort(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range)(Ranger);sort returns astd.range.SortedRange over the original range,allowing functions that can take advantage of sorted data to know that therange is sorted and adjust accordingly. Thestd.range.SortedRange is awrapper 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, buttheycan know thatstd.range.SortedRange has been sorted.PreconditionsThe predicate is expected to satisfy certain rules in order forsort tobehave as expected - otherwise, the program may fail on certain inputs (but notothers) when not compiled in release mode, due to the cursoryassumeSortedcheck. Specifically,sort expectsless(a,b) && less(b,c) to implyless(a,c) (transitivity), and, conversely,!less(a,b) && !less(b,c) toimply!less(a,c). Note that the default predicate ("a < b") does notalways satisfy these conditions for floating point types, because the expressionwill always befalse when eithera orb is NaN.Usestd.math.cmp instead.
| less | The predicate to sort by. |
| ss | The swapping strategy to use. |
Ranger | The range to sort. |
AlgorithmsIntrosort is used for unstable sorting andTimsort is used for stable sorting.Each algorithm has benefits beyond stability. Introsort is generally faster butTimsort may achieve greater speeds on data with low entropy or if predicate callsare expensive. Introsort performs no allocations whereas Timsort will perform oneor more allocations per call. Both algorithms haveΟ(n log n) worst-casetime complexity.
int[] array = [ 1, 2, 3, 4 ];// sort in descending orderarray.sort!("a > b");writeln(array);// [4, 3, 2, 1]// sort in ascending orderarray.sort();writeln(array);// [1, 2, 3, 4]// sort with reusable comparator and chainalias myComp = (x, y) => x > y;writeln(array.sort!(myComp).release);// [4, 3, 2, 1]
// Showcase stable sortingimport 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 floating-point numbers in presence of NaNdouble[] numbers = [-0.0, 3.0, -2.0,double.nan, 0.0, -double.nan];import std.algorithm.comparison : equal;import std.math.operations : cmp;import std.math.traits : 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));
schwartzSort(alias transform, alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, R)(Rr)schwartzSort(alias transform, SwapStrategy ss, R)(Rr)schwartzSort usesless(transform(a), transform(b)). The values of thetransform function are precomputed in a temporary array, thus saving onrepeatedly computing it. Conversely, if the cost oftransform is smallcompared to the cost of allocating and filling the precomputed array,sortmay be faster and therefore preferable.This approach to sorting is akin to theSchwartzian transform, also known asthe decorate-sort-undecorate pattern in Python and Lisp. The complexity is thesame as that of the correspondingsort, butschwartzSort evaluatestransform onlyr.length times (less than half when compared to regularsorting). The usage can be best illustrated with an example.Example
uint hashFun(string) { ... expensive computation ... }string[] array = ...;// Sort strings by hash, slowsort!((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 andbe faster than the Perl idiom or the decorate-sort-undecorate idiompresent in Python and Lisp. This is because sorting is done in-placeand only minimal extra data (one array of transformed elements) iscreated.To check whether an array was sorted and benefit of the speedup ofSchwartz sorting, a functionschwartzIsSorted is not providedbecause the effect can be achieved by callingisSorted!less(map!transform(r)).| transform | The transformation to apply. Either a unary function (unaryFun!transform(element)), or a binary function (binaryFun!transform(element, index)). |
| less | The predicate to sort the transformed elements by. |
| ss | The swapping strategy to use. |
Rr | The range to sort. |
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 =newdouble[][3];arr[0] = midEnt;arr[1] = lowEnt;arr[2] = highEnt;schwartzSort!(entropy,"a > b")(arr);writeln(arr[0]);// highEntwriteln(arr[1]);// midEntwriteln(arr[2]);// lowEntassert(isSorted!("a > b")(map!(entropy)(arr)));
partialSort(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range)(Ranger, size_tn)r such that the ranger[0 .. mid]is the same as if the entirer were sorted, and leavesthe ranger[mid ..r.length] in no particular order.r,n) and thensort!(less, ss)(r[0 .. n]).| less | The predicate to sort by. |
| ss | The swapping strategy to use. |
Ranger | The random-access range to reorder. |
size_tn | The length of the initial segment ofr 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]
partialSort(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range1, Range2)(Range1r1, Range2r2)| less | The predicate to sort by. |
| ss | The swapping strategy to use. |
Range1r1 | The first range. |
Range2r2 | 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]
topN(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range)(Ranger, size_tnth)r usingswapsuch thatr[nth] refers to the element that would fall there if the rangewere fully sorted.r such that all elementse1 fromr[0] tor[nth] satisfy!less(r[nth], e1),and all elementse2 fromr[nth] tor[r.length] satisfy!less(e2,r[nth]). Effectively, it finds thenth + 1 smallest(according toless) elements inr. Performs an expectedΟ(r.length) (if unstable) orΟ(r.length * log(r.length))(if stable) evaluations ofless andswap.Ifn >=r.length, the algorithm has no effect and returnsr[0 ..r.length].| less | The predicate to sort by. |
| ss | The swapping strategy to use. |
Ranger | The random-access range to reorder. |
size_tnth | The index of the element that should be in sorted position after the function is done. |
r[0] tor[nth], excludingr[nth] itself.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
topN(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range1, Range2)(Range1r1, Range2r2)| less | The predicate to sort by. |
| ss | The swapping strategy to use. |
Range1r1 | The first range. |
Range2r2 | 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]
topNCopy(alias less = "a < b", SRange, TRange)(SRangesource, TRangetarget, SortOutputsorted = No.sortOutput)source into therandom-access rangetarget, wheren =target.length.source are not touched. Ifsorted istrue, the target is sorted. Otherwise, the targetrespects theheap property.| less | The predicate to sort by. |
SRangesource | The source range. |
TRangetarget | The target range. |
SortOutputsorted | Whether to sort the elements copied intotarget. |
target containing the copied elements.import std.typecons : Yes;int[] a = [ 10, 16, 2, 3, 1, 5, 0 ];int[] b =newint[3];topNCopy(a, b, Yes.sortOutput);writeln(b);// [0, 1, 2]
topNIndex(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range, RangeIndex)(Ranger, RangeIndexindex, SortOutputsorted = No.sortOutput)| less | A binary predicate that defines the ordering of range elements. Defaults toa < b. |
| ss | (Not implemented yet.) Specify the swapping strategy. |
Ranger | Arandom-access range of elements to make an index for. |
RangeIndexindex | Arandom-access range with assignable elements to build the index in. The length of this range determines how many top elements to index inr. This index range can either have integral elements, in which case the constructed index will consist of zero-based numerical indices intor; or it can have pointers to the element type ofr, in which case the constructed index will be pointers to the top elements inr. |
SortOutputsorted | 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 =newint[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 =newint*[3];topNIndex(a, ptrIndex, Yes.sortOutput);writeln(ptrIndex);// [&a[5], &a[1], &a[3]]
nextPermutation(alias less = "a < b", BidirectionalRange)(BidirectionalRangerange)range in-place to the next lexicographically greater permutation.// Enumerate all permutationsint[] 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. |
BidirectionalRangerange | The range to permute. |
// Step through all permutations of a sorted array in lexicographic orderint[] a = [1,2,3];writeln(nextPermutation(a));// truewriteln(a);// [1, 3, 2]writeln(nextPermutation(a));// truewriteln(a);// [2, 1, 3]writeln(nextPermutation(a));// truewriteln(a);// [2, 3, 1]writeln(nextPermutation(a));// truewriteln(a);// [3, 1, 2]writeln(nextPermutation(a));// truewriteln(a);// [3, 2, 1]writeln(nextPermutation(a));// falsewriteln(a);// [1, 2, 3]
// Step through permutations of an array containing duplicate elements:int[] a = [1,1,2];writeln(nextPermutation(a));// truewriteln(a);// [1, 2, 1]writeln(nextPermutation(a));// truewriteln(a);// [2, 1, 1]writeln(nextPermutation(a));// falsewriteln(a);// [1, 1, 2]
nextEvenPermutation(alias less = "a < b", BidirectionalRange)(BidirectionalRangerange)range in-place to the next lexicographically greatereven permutation.// Enumerate even permutationsint[] 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 theodd 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 permutationsint[] 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));
WarningSince even permutations are only distinct from all permutations when the range elements are unique, this function assumes that there are no duplicate elements under the specified ordering. If this is not true, some permutations may fail to be generated. When the range has non-unique elements, you should usenextPermutation instead.
| less | The ordering to be used to determine lexicographical ordering of the permutations. |
BidirectionalRangerange | The range to permute. |
// Step through even permutations of a sorted array in lexicographic orderint[] a = [1,2,3];writeln(nextEvenPermutation(a));// truewriteln(a);// [2, 3, 1]writeln(nextEvenPermutation(a));// truewriteln(a);// [3, 1, 2]writeln(nextEvenPermutation(a));// falsewriteln(a);// [1, 2, 3]
import std.math.algebraic : sqrt;// Print the 60 vertices of a uniform truncated icosahedron (soccer ball)enumreal Phi = (1.0 + sqrt(5.0)) / 2.0;// Golden ratioreal[][] 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 seeddo {// Loop over all sign changes of each permutation size_t i;do {// Generate all possible sign changesfor (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
nthPermutation(Range)(auto ref Rangerange, const ulongperm)range into theperm permutation.range can be permuted. The rest of the range will therefore not bepermuted.This algorithm uses theLehmerCode.The algorithm works as follows:auto pem = [4,0,4,1,0,0,0]; // permutation 2982 in factorial auto src = [0,1,2,3,4,5,6]; // the range to permutate auto i = 0; // range index // range index iterates pem and src in sync // pem[i] + i is used as index into src // first src[pem[i] + i] is stored in t auto t = 4; // tmp value src = [0,1,2,3,n,5,6]; // then the values between i and pem[i] + i are moved one // to the right src = [n,0,1,2,3,5,6]; // at last t is inserted into position i src = [4,0,1,2,3,5,6]; // finally i is incremented ++i; // this process is repeated while i < pem.length t = 0; src = [4,n,1,2,3,5,6]; src = [4,0,1,2,3,5,6]; ++i; t = 6; src = [4,0,1,2,3,5,n]; src = [4,0,n,1,2,3,5]; src = [4,0,6,1,2,3,5];
Rangerange | The Range to permute. The original ordering will be lost. |
ulongperm | The permutation to permutaterange to. |
auto src = [0, 1, 2, 3, 4, 5, 6];auto rslt = [4, 0, 6, 2, 1, 3, 5];src =nthPermutation(src, 2982);writeln(src);// rslt
nthPermutationImpl(Range)(auto ref Rangerange, ulongperm)perm had more digits in the factorial number system than range had elements. This case must not occur as this would lead to out of range accesses.auto src = [0, 1, 2, 3, 4, 5, 6];auto rslt = [4, 0, 6, 2, 1, 3, 5];bool worked =nthPermutationImpl(src, 2982);assert(worked);writeln(src);// rslt