View source code
Display the source code in std/algorithm/comparison.d from which this page was generated on github.
Report a bug
If you spot a problem with this page, click here to create a Bugzilla issue.
Improve this page
Quickly fork, edit online, and submit a pull request for this page. Requires a signed-in GitHub account. This works well for small changes. If you'd like to make larger changes you may want to consider using local clone.

Function std.algorithm.comparison.isPermutation

Checks if both ranges are permutations of each other.

bool isPermutation(Flag!("allocateGC") allocateGC, Range1, Range2) (
  Range1 r1,
  Range2 r2
)
if (allocateGC == Yes.allocateGC && isForwardRange!Range1 && isForwardRange!Range2 && !isInfinite!Range1 && !isInfinite!Range2);

bool isPermutation(alias pred, Range1, Range2) (
  Range1 r1,
  Range2 r2
)
if (is(typeof(binaryFun!pred)) && isForwardRange!Range1 && isForwardRange!Range2 && !isInfinite!Range1 && !isInfinite!Range2);

This function can allocate if the Yes.allocateGC flag is passed. This has the benefit of have better complexity than the Yes.allocateGC option. However, this option is only available for ranges whose equality can be determined via each element's toHash method. If customized equality is needed, then the pred template parameter can be passed, and the function will automatically switch to the non-allocating algorithm. See binaryFun for more details on how to define pred.

Non-allocating forward range option: Ο(n^2) Non-allocating forward range option with custom pred: Ο(n^2) Allocating forward range option: amortized Ο(r1.length) + Ο(r2.length)

Parameters

NameDescription
pred an optional parameter to change how equality is defined
allocateGC Yes.allocateGC/No.allocateGC
r1 A finite forward range
r2 A finite forward range

Returns

true if all of the elements in r1 appear the same number of times in r2. Otherwise, returns false.

Example

import std.typecons : Yes;

assert(isPermutation([1, 2, 3], [3, 2, 1]));
assert(isPermutation([1.1, 2.3, 3.5], [2.3, 3.5, 1.1]));
assert(isPermutation("abc", "bca"));

assert(!isPermutation([1, 2], [3, 4]));
assert(!isPermutation([1, 1, 2, 3], [1, 2, 2, 3]));
assert(!isPermutation([1, 1], [1, 1, 1]));

// Faster, but allocates GC handled memory
assert(isPermutation!(Yes.allocateGC)([1.1, 2.3, 3.5], [2.3, 3.5, 1.1]));
assert(!isPermutation!(Yes.allocateGC)([1, 2], [3, 4]));

Authors

Andrei Alexandrescu

License

Boost License 1.0.