Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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 ----------------------------*- 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 -------------------------------------------*- 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 ----------------------------------------*- 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 ----------------------------------*- 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
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.