Confirming permutations, rotating to the next or previous permutation, or going through all permutations; inspired by the C++ Standard Library. See <https://forums.swift.org/t/how-about-detection-and-iteration-of-permutations/31404> for more information.

AdjacentPermutation.swift

//===--- AdjacentPermutation.swift ----------------------------*- swift -*-===//
//
// Created by Daryle Walker on 2019-Nov-27
//
// Copyright © 2019 Daryle Walker
//
// Methods to rearrange a collection to its next or previous permutation.
// Methods to return a sequence of all permutations of a collection, both lazy
// and eager.
//
//===----------------------------------------------------------------------===//


// MARK: Support for Counting Permutations

fileprivate extension Collection {

    /// Determines the number of lexicographically distinct permutations of the
    /// collection that has been sorted along the given predicate.
    ///
    /// The predicate must be a strict weak ordering over the elements.
    ///
    /// - Precondition: The collection is sorted along `areInIncreasingOrder`.
    ///
    /// - Parameter areInIncreasingOrder: A predicate that returns `true` if its
    ///   first argument should be ordered before its second argument;
    ///   otherwise, `false`.
    /// - Returns: The number of permutations that are distinct according to
    ///   `areInIncreasingOrder`, if that count is at most `Int.max`; otherwise,
    ///   `nil`.
    ///
    /// - Complexity: O(*n*), where *n* is the length of the collection
    func countDistinctPermutations(by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows -> Int? {
        // Empty collections only have one permutation.
        let end = endIndex
        guard case var base = startIndex, base < end else { return 1 }

        // Walk the collection for runs of equivalent elements.  Since the
        // collection should be already sorted, we only need to look for a value
        // increase.
        var counts = Array<Int>(), latestCount = 1
        counts.reserveCapacity(Swift.max(1, underestimatedCount))
        for current in indices.dropFirst() {
            if try areInIncreasingOrder(self[base], self[current]) {
                // Found the start of a new run.
                counts.append(latestCount)
                base = current
                latestCount = 1
            } else {
                // Continue this run, since the elements are equivalent.
                latestCount += 1
            }
        }

        // Include the last run.
        counts.append(latestCount)

        // Compute the result from combining the category counts.
        return counts.multinomial()
    }

}

// MARK: - Permute In-Place

extension MutableCollection where Self: BidirectionalCollection {

    /// Moves elements to their immediately-next lexicographical arrangement,
    /// using the given predicate as comparison between elements.
    ///
    /// The predicate must be a strict weak ordering over the elements.
    ///
    /// If there are elements that are equivalent, only one of their
    /// permutations will be vended instead of all *k*! per arrangment (where
    /// *k* is the number of equivalent elements).  Their relative positions are
    /// unstably sorted.
    ///
    /// - Parameter areInIncreasingOrder: A predicate that returns `true` if its
    ///   first argument should be ordered before its second argument;
    ///   otherwise, `false`.
    /// - Returns: `true` if the post-call state is lexicographically higher
    ///   than the pre-call state; otherwise `false`.  The `false` case happens
    ///   when the collection ends in its lexicographically minimum state
    ///   (*i.e.* it becomes sorted).
    /// - Postcondition: `oldSelf.lexicographicallyPrecedes(self, by:`
    ///   `areInIncreasingOrder)` when this method returns `true`, and `self` is
    ///   sorted according to `areInIncreasingOrder` when this method returns
    ///   `false`.
    ///
    /// - Complexity: O(*n*) per call, where *n* is the length of the
    ///   collection, but amortized O(1) if all arrangments are cycled through
    ///   repeated calls of this method.
    public mutating func permuteForward(by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows -> Bool {
        // Find the element before the longest non-increasing suffix.
        let start = startIndex
        guard var afterPivot = index(endIndex, offsetBy: -1, limitedBy: start) else {
            // Empty collections are eternally sorted.
            return false
        }
        guard var pivot = index(afterPivot, offsetBy: -1, limitedBy: start) else {
            // Single-element collections are also eternally sorted.
            return false
        }

        while try !areInIncreasingOrder(self[pivot], self[afterPivot]) {
            guard let beforePivot = index(pivot, offsetBy: -1, limitedBy: start) else {
                // The collection is reverse-sorted; reset to sorted.
                reverse()
                return false
            }

            (afterPivot, pivot) = (pivot, beforePivot)
        }

        // Swap that pivot with the furthest-out higher value.
        let pivotValue = self[pivot]
        let lastHigher = try self[afterPivot...].lastIndex(where: {
            try areInIncreasingOrder(pivotValue, $0)
        })!
        swapAt(pivot, lastHigher)

        // Reset the new suffix to its lexicographic minimum.
        self[afterPivot...].reverse()
        return true
    }

    /// Moves elements to their immediately-previous lexicographical
    /// arrangement, using the given predicate as comparison between elements.
    ///
    /// The predicate must be a strict weak ordering over the elements.
    ///
    /// If there are elements that are equivalent, only one of their
    /// permutations will be vended instead of all *k*! per arrangment (where
    /// *k* is the number of equivalent elements).  Their relative positions are
    /// unstably sorted.
    ///
    /// - Parameter areInIncreasingOrder: A predicate that returns `true` if its
    ///   first argument should be ordered before its second argument;
    ///   otherwise, `false`.
    /// - Returns: `true` if the post-call state is lexicographically lower
    ///   than the pre-call state; otherwise `false`.  The `false` case happens
    ///   when the collection ends in its lexicographically maximum state
    ///   (*i.e.* it becomes reverse-sorted).
    /// - Postcondition: `self.lexicographicallyPrecedes(oldSelf, by:`
    ///   `areInIncreasingOrder)` when this method returns `true`, and `self` is
    ///   reverse-sorted according to `areInIncreasingOrder` when this method
    ///   returns `false`.
    ///
    /// - Complexity: O(*n*) per call, where *n* is the length of the
    ///   collection, but amortized O(1) if all arrangments are cycled through
    ///   repeated calls of this method.
    public mutating func permuteBackward(by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows -> Bool {
        // Find the element before the longest non-decreasing suffix.
        let start = startIndex
        guard var afterPivot = index(endIndex, offsetBy: -1, limitedBy: start) else {
            // Empty collections are eternally sorted.
            return false
        }
        guard var pivot = index(afterPivot, offsetBy: -1, limitedBy: start) else {
            // Single-element collections are also eternally sorted.
            return false
        }

        while try !areInIncreasingOrder(self[afterPivot], self[pivot]) {
            guard let beforePivot = index(pivot, offsetBy: -1, limitedBy: start) else {
                // The collection is sorted; reset to reverse-sorted.
                reverse()
                return false
            }

            (afterPivot, pivot) = (pivot, beforePivot)
        }

        // Swap that pivot with the furthest-out lower value.
        let pivotValue = self[pivot]
        let lastLower = try self[afterPivot...].lastIndex(where: {
            try areInIncreasingOrder($0, pivotValue)
        })!
        swapAt(pivot, lastLower)

        // Reset the new suffix to its lexicographic maximum.
        self[afterPivot...].reverse()
        return true
    }

}

extension MutableCollection where Self: BidirectionalCollection, Element: Comparable {

    /// Moves elements to their immediately-next lexicographical arrangement.
    ///
    /// If there are elements that are equal, only one of their permutations
    /// will be vended instead of all *k*! per arrangment (where *k* is the
    /// number of equal elements).  Their relative positions are unstably
    /// sorted.
    ///
    /// - Returns: `true` if the post-call state is lexicographically higher
    ///   than the pre-call state; otherwise `false`.  The `false` case happens
    ///   when the collection ends in its lexicographically minimum state
    ///   (*i.e.* it becomes sorted).
    /// - Postcondition: `oldSelf.lexicographicallyPrecedes(self)` when this
    ///   method returns `true`, and `self` is monotonically increasing when
    ///   this method returns `false`.
    ///
    /// - Complexity: O(*n*) per call, where *n* is the length of the
    ///   collection, but amortized O(1) if all arrangments are cycled through
    ///   repeated calls of this method.
    @inlinable
    public mutating func permuteForward() -> Bool {
        return permuteForward(by: <)
    }

    /// Moves elements to their immediately-previous lexicographical
    /// arrangement.
    ///
    /// If there are elements that are equal, only one of their permutations
    /// will be vended instead of all *k*! per arrangment (where *k* is the
    /// number of equal elements).  Their relative positions are unstably
    /// sorted.
    ///
    /// - Returns: `true` if the post-call state is lexicographically lower
    ///   than the pre-call state; otherwise `false`.  The `false` case happens
    ///   when the collection ends in its lexicographically maximum state
    ///   (*i.e.* it becomes reverse-sorted).
    /// - Postcondition: `self.lexicographicallyPrecedes(oldSelf)` when this
    ///   method returns `true`, and `self` is monotonically decreasing when
    ///   this method returns `false`.
    ///
    /// - Complexity: O(*n*) per call, where *n* is the length of the
    ///   collection, but amortized O(1) if all arrangments are cycled through
    ///   repeated calls of this method.
    @inlinable
    public mutating func permuteBackward() -> Bool {
        return permuteBackward(by: <)
    }

}

// MARK: - Eager Sequence of Unique Permutations

extension MutableCollection where Self: BidirectionalCollection {

    /// Returns each permutation of this collection, using the given predicate
    /// to compare elements, into an overall collection of the given type.
    ///
    /// The predicate must be a strict weak ordering over the elements.
    ///
    /// - Warning: This collection must not be of a reference type or otherwise
    ///   share state between copies (unless it's copy-on-write).
    ///
    /// - Parameter type: A metatype specifier for the returned collection.
    /// - Parameter areInIncreasingOrder: A predicate that returns `true` if its
    ///   first argument should be ordered before its second argument;
    ///   otherwise, `false`.
    /// - Returns: A collection containing each unique permutation of this
    ///   collection, starting from its sorted state.
    ///
    /// - Complexity: O(*n*) in auxillary space and O(*n*!) in time, where *n*
    ///   is the length of this collection.
    public func permutations<T: RangeReplaceableCollection>(as type: T.Type, by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows -> T where T.Element == Self {
        // Make a proxy to repeatedly permute, starting from the sorted state.
        let sortedSelf = try sorted(by: areInIncreasingOrder)
        var copyOfSelf = self
        _ = copyOfSelf.copy(from: sortedSelf)

        // Prepare the receiving collection...
        let underCount = try sortedSelf.countDistinctPermutations(by: areInIncreasingOrder) ?? Int.max
        var result = T()
        result.reserveCapacity(underCount)

        // ...and load it.
        var keepGoing: Bool
        repeat {
            result.append(copyOfSelf)
            keepGoing = try copyOfSelf.permuteForward(by: areInIncreasingOrder)
        } while keepGoing
        return result
    }

    /// Returns each permutation of this collection, using the given predicate
    /// to compare elements, stored into an array.
    ///
    /// The predicate must be a strict weak ordering over the elements.
    ///
    /// - Warning: This collection must not be of a reference type or otherwise
    ///   share state between copies (unless it's copy-on-write).
    ///
    /// - Parameter areInIncreasingOrder: A predicate that returns `true` if its
    ///   first argument should be ordered before its second argument;
    ///   otherwise, `false`.
    /// - Returns: An array containing each unique permutation of this
    ///   collection, starting from its sorted state.
    ///
    /// - Complexity: O(*n*) in auxillary space and O(*n*!) in time, where *n*
    ///   is the length of this collection.
    @inlinable
    public func permutations(by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows -> [Self] {
        return try permutations(as: Array.self, by: areInIncreasingOrder)
    }

}

extension MutableCollection where Self: BidirectionalCollection, Element: Comparable {

    /// Returns each permutation of this collection, stored into an array.
    ///
    /// - Warning: This collection must not be of a reference type or otherwise
    ///   share state between copies (unless it's copy-on-write).
    ///
    /// - Returns: An array containing each unique permutation of this
    ///   collection, starting from its sorted state.
    ///
    /// - Complexity: O(*n*) in auxillary space and O(*n*!) in time, where *n*
    ///   is the length of this collection.
    @inlinable
    public func permutations() -> [Self] {
        return permutations(by: <)
    }

}

// MARK: - Lazy Sequence of Unique Permutations

/// A sequence of all the permutations of a collection, removing repeats when
/// there are sets of equivalent elements.
///
/// - Precondition: `Element` cannot be a reference type.
public struct DistinctPermutationSequence<Element: MutableCollection & BidirectionalCollection> {

    /// The source collection.
    @usableFromInline
    let base: Element
    /// The predicate determining the relative ranking of elements.
    @usableFromInline
    let areInIncreasingOrder: (Element.Element, Element.Element) -> Bool

    // Since this is precomputed, `base` can't be of a reference type or
    // otherwise be able to have its value changed behind this object's back.
    public let underestimatedCount: Int

    /// Creates a sequence over the unique permutations of the given collection,
    /// using the given predicate to order elements of the collection.
    @usableFromInline
    init(_ base: Element, by areInIncreasingOrder: @escaping (Element.Element, Element.Element) -> Bool) {
        self.areInIncreasingOrder = areInIncreasingOrder

        // The `permuteForward()` method needs the collection to start in its
        // sorted state to reach its full cycle without pre-counting.
        let sortedBase = base.sorted(by: areInIncreasingOrder)
        var temp = base
        _ = temp.copy(from: sortedBase)
        self.base = temp

        underestimatedCount = sortedBase.countDistinctPermutations(by: areInIncreasingOrder) ?? Int.max
    }

}

extension DistinctPermutationSequence: LazySequenceProtocol {

    public struct Iterator {
        /// The next arrangement to vend.
        @usableFromInline
        var upcoming: Element
        /// The predicate determining the relative ranking of elements.
        @usableFromInline
        let areInIncreasingOrder: (Element.Element, Element.Element) -> Bool
        /// Whether the last permutation has been reached.
        var isDone = false

        /// Creates an iterator over the permuations of the given sequence along
        /// the given ordering predicate.
        ///
        /// - Precondition: `base` is sorted along `areInIncreasingOrder`.
        @inlinable
        init(_ base: Element, by areInIncreasingOrder: @escaping (Element.Element, Element.Element) -> Bool) {
            upcoming = base
            self.areInIncreasingOrder = areInIncreasingOrder
        }
    }

    @inlinable
    public __consuming func makeIterator() -> Iterator {
        return Iterator(base, by: areInIncreasingOrder)
    }

}

extension DistinctPermutationSequence.Iterator: IteratorProtocol {

    public mutating func next() -> Element? {
        guard !isDone else { return nil }

        defer {
            isDone = !upcoming.permuteForward(by: areInIncreasingOrder)
        }
        return upcoming
    }

}

extension LazySequenceProtocol where Elements: MutableCollection & BidirectionalCollection {

    /// Returns a lazy sequence going over all the permutations of this
    /// collection, using the given predicate to compare elements.
    ///
    /// The predicate must be a strict weak ordering over the elements.
    ///
    /// - Warning: This collection must not be of a reference type or otherwise
    ///   share state between copies (unless it's copy-on-write).
    ///
    /// - Parameter areInIncreasingOrder: A predicate that returns `true` if its
    ///   first argument should be ordered before its second argument;
    ///   otherwise, `false`.
    /// - Returns: A sequence that lazily generates each unique permutation of
    ///   this collection, starting from its sorted state.
    @inlinable
    public func permutations(by areInIncreasingOrder: @escaping (Element, Element) -> Bool) -> DistinctPermutationSequence<Elements> {
        return DistinctPermutationSequence(elements, by: areInIncreasingOrder)
    }

}

extension LazySequenceProtocol where Elements: MutableCollection & BidirectionalCollection, Element: Comparable {

    /// Returns a lazy sequence going over all the permutations of this
    /// collection.
    ///
    /// - Warning: This collection must not be of a reference type or otherwise
    ///   share state between copies (unless it's copy-on-write).
    ///
    /// - Returns: A sequence that lazily generates each unique permutation of
    ///   this collection, starting from its sorted state.
    @inlinable
    public func permutations() -> DistinctPermutationSequence<Elements> {
        return permutations(by: <)
    }

}

Copy.swift

//===--- Copy.swift -------------------------------------------*- swift -*-===//
//
// Created by Daryle Walker on 2019-Dec-02
//
// Copyright © 2019 Daryle Walker
//
// Method to copy to another collection via overwriting.
//
//===----------------------------------------------------------------------===//


extension MutableCollection {

    /// Copies elements from the given collection to this one from their
    /// respective starts until at least one of them runs out.
    ///
    /// - Parameter source: The source of the new element values.
    /// - Returns: A tuple where the first member is the past-the-end of the
    ///   elements of this collection that had their values replaced, and the
    ///   second member is the past-the-end of the elements from `source` that
    ///   were actually copied.  If the entirety of a collection was
    ///   written-to/read-from, that respective member of the return will be the
    ///   corresponding collection's `endIndex`.
    /// - Postcondition: The first *m* elements of this collection have their
    ///   values replaced by the respective elements from `source`, where *m* is
    ///   the length of the shorter collection.
    ///
    /// - Complexity: O(*m*), where *m* is the length of the shorter collection.
    mutating func copy<C: Collection>(from source: C) -> (end: Index, sourceEnd: C.Index) where C.Element == Element {
        var sourceIndex = source.startIndex, destinationIndex = startIndex
        let sourceEnd = source.endIndex, destinationEnd = endIndex
        while sourceIndex < sourceEnd, destinationIndex < destinationEnd {
            self[destinationIndex] = source[sourceIndex]
            source.formIndex(after: &sourceIndex)
            formIndex(after: &destinationIndex)
        }
        return (destinationIndex, sourceIndex)
    }

}

Integer.swift

//===--- Integer.swift ----------------------------------------*- swift -*-===//
//
// Created by Daryle Walker on 2019-Dec-03
//
// Copyright © 2019 Daryle Walker
//
// Methods to compute the binomial and multinomial coefficients.
//
//===----------------------------------------------------------------------===//


// MARK: Combinatorics

extension FixedWidthInteger {

    /// Determines the binomial coefficient with the nonnegative receiver as the
    /// group size and the given value as the subset size, if it fits.
    func choose(_ k: Self) -> Self? {
        precondition(self >= 0)
        guard 0...self ~= k else { return 0 }
        guard k > 0, k < self else { return 1 }  // Needed for the "..." below

        var result: Self = 1
        for index in 1...Swift.min(k, self - k) {
            let nk = self - index + 1
            let (q, r) = result.quotientAndRemainder(dividingBy: index)
            let (qnk, overflow1) = q.multipliedReportingOverflow(by: nk)
            let (rnk, overflow2) = r.multipliedReportingOverflow(by: nk)
            let (nextResult, overflow3) = qnk.addingReportingOverflow(rnk / index)
            guard !overflow1, !overflow2, !overflow3 else { return nil }

            result = nextResult
        }
        return result
    }

}

extension Sequence where Element: FixedWidthInteger {

    /// Determines the multinomial coefficient using the sequence elements as
    /// the subset sizes and their sum as the group size, if it fits.
    ///
    /// - Precondition: Every element is non-negative.
    ///
    /// - Returns: `reduce(0, +).factorial / map { $0.factorial }.reduce(1, *)`
    func multinomial() -> Element? {
        var result, totalCount: Element
        result = 1
        totalCount = 0
        for count in self {
            precondition(count >= 0)

            let (newTotal, overflow1) = totalCount.addingReportingOverflow(count)
            guard !overflow1, let newChoice = newTotal.choose(count) else {
                return nil
            }

            let (newResult, overflow2) = result.multipliedReportingOverflow(by: newChoice)
            guard !overflow2 else { return nil }

            totalCount = newTotal
            result = newResult
        }
        return result
    }

}

IsPermutation.swift

//===--- IsPermutation.swift ----------------------------------*- swift -*-===//
//
// Created by Daryle Walker on 2019-Nov-26
//
// Copyright © 2019 Daryle Walker
//
// Methods to check if one sequence is a permutation of another.  Typically has
// quadratic complexity, but is linear for hashable elements.
//
//===----------------------------------------------------------------------===//


// MARK: Support for Testing Permutations

/// A quick & dirty linked list node.
fileprivate final class Node<Element> {

    /// The stored value.
    let element: Element
    /// The link to the next node.
    var next: Node?
    /// The link to the previous node.
    weak var previous: Node?

    /// Creates a node with the given element, but no links.
    @inlinable init(_ value: Element) {
        element = value
        next = nil
        previous = nil
    }

}

// MARK: - Testing Permutations

extension Sequence {

    /// Determines whether this sequence is a permutation of the given sequence,
    /// using the given predicate as the equivalence test.
    ///
    /// The predicate must be an equivalence relation over the elements.
    ///
    /// - Precondition: `other` is finite.
    ///
    /// - Parameter other: A sequence to compare to this sequence.
    /// - Parameter areEquivalent: A predicate that returns `true` if its two
    ///   arguments are equivalent; otherwise, `false`.
    /// - Returns: `true` if the elements of this sequence can be rearranged
    ///   into a sequence `x` such that `x.elementsEqual(other, areEquivalent)`
    ///   would return `true`; otherwise, `false`.  Two empty sequences are
    ///   considered equal, and therefore co-permutations.
    ///
    /// - Complexity: O(*m*²) in time and O(*m*) in space, where *m* is the
    ///   length of `other`.  Can go down to O(*m*) in time and O(1) in space
    ///   when the sequences are already equal.
    public func isPermutation<S: Sequence>(of other: S, by areEquivalent: (Element, S.Element) throws -> Bool) rethrows -> Bool {
        // Check for any common prefix.
        var iterator = makeIterator(), otherIterator = other.makeIterator()
        var head: Node<S.Element>?, current: Element
        repeat {
            head = otherIterator.next().map(Node.init(_:))
            guard let next = iterator.next() else { return head == nil }
            guard head != nil else { return false }

            current = next
        } while try areEquivalent(current, head!.element)

        // Lay out `other` into a linked list.
        while let element = otherIterator.next() {
            let newHead = Node(element)
            head?.previous = newHead
            newHead.next = head
            head = newHead
        }

        // Find the element from `self` within the linked list.
        repeat {
            // Make sure at least one node can match `current`.
            var node = head
            while let value = node?.element {
                if try areEquivalent(current, value) {
                    break
                }
                node = node?.next
            }
            guard let match = node else { return false }

            // Remove the matching node from the list.
            match.next?.previous = match.previous
            match.previous?.next = match.next
            if match === head {
                head = head?.next
            }

            // Move on from the matching value in `self`.
            guard let next = iterator.next() else { break }

            current = next
        } while true
        return head == nil
    }

}

extension Sequence where Element: Equatable {

    /// Determines whether this sequence is a permutation of the given sequence.
    ///
    /// - Precondition: `other` is finite.
    ///
    /// - Parameter other: A sequence to compare to this sequence.
    /// - Returns: `true` if the elements of this sequence can be rearranged
    ///   into a sequence `x` such that `x.elementsEqual(other)` would return
    ///   `true`; otherwise, `false`.  Two empty sequences are considered equal,
    ///   and therefore co-permutations.
    ///
    /// - Complexity: O(*m*²) in time and O(*m*) in space, where *m* is the
    ///   length of `other`.  Can go down to O(*m*) in time and O(1) in space
    ///   when the sequences are already equal.
    @inlinable
    public func isPermutation<S: Sequence>(of other: S) -> Bool where S.Element == Element {
        return isPermutation(of: other, by: ==)
    }

}

extension Sequence where Element: Hashable {

    /// Determines whether this sequence is a permutation of the given sequence.
    ///
    /// - Precondition:
    ///     - At least one sequence is finite.
    ///     - Neither sequence has more than `Int.max` copies of any value.
    ///
    /// - Parameter other: A sequence to compare to this sequence.
    /// - Returns: `true` if the elements of this sequence can be rearranged
    ///   into a sequence `x` such that `x.elementsEqual(other)` would return
    ///   `true`; otherwise, `false`.  Two empty sequences are considered equal,
    ///   and therefore co-permutations.
    ///
    /// - Complexity: O(*m*) in time and space, where *m* is the length of the
    ///   shorter sequence.  Can go down to O(1) in space when the sequences are
    ///   already equal.
    public func isPermutation<S: Sequence>(of other: S) -> Bool where S.Element == Element {
        // Based from <https://deque.blog/2017/04/10/still-lost-in-permutation-complexity/>.

        var frequencies: [Element: Int] = [:]
        var iterator = makeIterator(), otherIterator = other.makeIterator()
        frequencies.reserveCapacity(Swift.max(0, underestimatedCount &+ other.underestimatedCount))
        while true {
            switch (iterator.next(), otherIterator.next()) {
            case (nil, nil):
                // Same length; better have all values cancel out.
                // (Note it still works when both sequences are empty.)
                return frequencies.allSatisfy { $0.value == 0 }
            case (_?, nil), (nil, _?):
                // Uneven lengths.
                return false
            case let (element?, otherElement?) where element == otherElement:
                // The elements nullify each other.
                continue
            case let (element?, otherElement?):
                // Count their occurrences, in opposite ways.
                frequencies[element, default: 0] += 1
                frequencies[otherElement, default: 0] -= 1
            }
        }
    }

}