mirror of
https://github.com/apple/swift-algorithms
synced 2026-11-22 04:10:39 +00:00
* Incorporate swift-format formatting fixes * Resolve linting issues * Doc edits, mostly to fix linter-identified issues * Early exit improvements * Indentation fixes * Line lengths to 80 maximum * Implement case binding rule, plus argument line break improvements * Implement NoForceUnwrap rule * Format the tests, as well * Stop masquerading as XCTest
218 lines
5.7 KiB
Swift
218 lines
5.7 KiB
Swift
//===----------------------------------------------------------------------===//
|
|
//
|
|
// This source file is part of the Swift Algorithms open source project
|
|
//
|
|
// Copyright (c) 2020 Apple Inc. and the Swift project authors
|
|
// Licensed under Apache License v2.0 with Runtime Library Exception
|
|
//
|
|
// See https://swift.org/LICENSE.txt for license information
|
|
//
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
import XCTest
|
|
|
|
@testable import Algorithms
|
|
|
|
final class PermutationsTests: XCTestCase {
|
|
func testPermutations() {
|
|
let c = "ABCDE"
|
|
|
|
func t(count: Int?) {
|
|
let p = c.permutations(ofCount: count)
|
|
|
|
let count = count ?? c.count
|
|
let permCount = c.count.factorial() / (c.count - count).factorial()
|
|
XCTAssertEqual(permCount, p.count)
|
|
XCTAssertEqual(p.count, Array(p).count)
|
|
XCTAssertTrue(p.allSatisfy { $0.count == count })
|
|
XCTAssertTrue(p.isSorted(by: { $0.lexicographicallyPrecedes($1) }))
|
|
}
|
|
|
|
func ts<R: RangeExpression>(count: R) where R.Bound == Int {
|
|
let p = count.relative(to: 0 ..< .max)
|
|
.clamped(to: 0..<c.count + 1)
|
|
.flatMap {
|
|
c.permutations(ofCount: $0)
|
|
}
|
|
|
|
let p2 = c.permutations(ofCount: count)
|
|
|
|
XCTAssertEqual(p.count, p2.count)
|
|
expectEqualSequences(p, Array(p2))
|
|
}
|
|
|
|
t(count: 0)
|
|
t(count: 1)
|
|
t(count: 2)
|
|
t(count: 3)
|
|
t(count: 4)
|
|
t(count: 5)
|
|
t(count: nil)
|
|
|
|
ts(count: 0...0)
|
|
ts(count: 1...1)
|
|
ts(count: 0...1)
|
|
ts(count: 0...2)
|
|
ts(count: 0...3)
|
|
ts(count: 1...3)
|
|
ts(count: 2...3)
|
|
ts(count: 0...)
|
|
ts(count: ...5)
|
|
ts(count: ...4)
|
|
ts(count: ...6)
|
|
}
|
|
|
|
func testEmpty() {
|
|
// `k == 0` results in one zero-length permutation
|
|
XCTAssertEqual(1, "".permutations().count)
|
|
XCTAssertEqual(1, "ABCD".permutations(ofCount: 0).count)
|
|
XCTAssertEqual(1, "ABCD".permutations(ofCount: 0...0).count)
|
|
XCTAssertEqual(Array("".permutations()), [[]])
|
|
XCTAssertEqual(Array("".permutations(ofCount: 0)), [[]])
|
|
XCTAssertEqual(Array("ABCD".permutations(ofCount: 0)), [[]])
|
|
XCTAssertEqual(Array("ABCD".permutations(ofCount: 0...0)), [[]])
|
|
|
|
// `k` greater than element count results in zero permutations
|
|
XCTAssertEqual(0, "".permutations(ofCount: 5).count)
|
|
XCTAssertEqual(Array("".permutations(ofCount: 5)), [])
|
|
XCTAssertEqual(Array("ABCD".permutations(ofCount: 5)), [])
|
|
XCTAssertEqual(Array("ABCD".permutations(ofCount: 5..<6)), [])
|
|
XCTAssertEqual(Array("ABCD".permutations(ofCount: 5..<7)), [])
|
|
XCTAssertEqual(Array("ABCD".permutations(ofCount: 5...)), [])
|
|
}
|
|
|
|
func testNextPermutation() {
|
|
var numbers = Array(1...7)
|
|
|
|
_ = numbers.nextPermutation()
|
|
XCTAssertEqual([1, 2, 3, 4, 5, 7, 6], numbers)
|
|
_ = numbers.nextPermutation()
|
|
XCTAssertEqual([1, 2, 3, 4, 6, 5, 7], numbers)
|
|
_ = numbers.nextPermutation()
|
|
XCTAssertEqual([1, 2, 3, 4, 6, 7, 5], numbers)
|
|
_ = numbers.nextPermutation()
|
|
XCTAssertEqual([1, 2, 3, 4, 7, 5, 6], numbers)
|
|
_ = numbers.nextPermutation()
|
|
XCTAssertEqual([1, 2, 3, 4, 7, 6, 5], numbers)
|
|
_ = numbers.nextPermutation()
|
|
XCTAssertEqual([1, 2, 3, 5, 4, 6, 7], numbers)
|
|
|
|
// Fast-forward to end of permutations.
|
|
while numbers.nextPermutation() {}
|
|
XCTAssertEqual([1, 2, 3, 4, 5, 6, 7], numbers)
|
|
}
|
|
|
|
func testPermutationsLazy() {
|
|
requireLazySequence("ABCD".lazy.permutations(ofCount: 2))
|
|
}
|
|
|
|
func testDocumentationExample1() {
|
|
// From Guides/Permutations.md
|
|
let numbers = [10, 20, 30]
|
|
let permutations = numbers.permutations()
|
|
expectEqualSequences(
|
|
permutations,
|
|
[
|
|
[10, 20, 30],
|
|
[10, 30, 20],
|
|
[20, 10, 30],
|
|
[20, 30, 10],
|
|
[30, 10, 20],
|
|
[30, 20, 10],
|
|
])
|
|
}
|
|
|
|
func testDocumentationExample2() {
|
|
// From Guides/Permutations.md
|
|
let numbers = [10, 20, 30]
|
|
let permutations = numbers.permutations(ofCount: 2)
|
|
expectEqualSequences(
|
|
permutations,
|
|
[
|
|
[10, 20],
|
|
[10, 30],
|
|
[20, 10],
|
|
[20, 30],
|
|
[30, 10],
|
|
[30, 20],
|
|
])
|
|
}
|
|
|
|
func testDocumentationExample3() {
|
|
// From Guides/Permutations.md
|
|
let numbers2 = [20, 10, 10]
|
|
let permutations = numbers2.permutations()
|
|
expectEqualSequences(
|
|
permutations,
|
|
[
|
|
[20, 10, 10],
|
|
[20, 10, 10],
|
|
[10, 20, 10],
|
|
[10, 10, 20],
|
|
[10, 20, 10],
|
|
[10, 10, 20],
|
|
])
|
|
}
|
|
|
|
func testDocumentationExample4() {
|
|
// From Guides/Permutations.md
|
|
let numbers = [10, 20, 30]
|
|
let permutations = numbers.permutations(ofCount: 0...)
|
|
expectEqualSequences(
|
|
permutations,
|
|
[
|
|
[],
|
|
[10],
|
|
[20],
|
|
[30],
|
|
[10, 20],
|
|
[10, 30],
|
|
[20, 10],
|
|
[20, 30],
|
|
[30, 10],
|
|
[30, 20],
|
|
[10, 20, 30],
|
|
[10, 30, 20],
|
|
[20, 10, 30],
|
|
[20, 30, 10],
|
|
[30, 10, 20],
|
|
[30, 20, 10],
|
|
])
|
|
}
|
|
|
|
func testDocumentationExample5() {
|
|
// From Permutations.swift
|
|
let names = ["Alex", "Celeste", "Davide"]
|
|
let permutations = names.permutations(ofCount: 2)
|
|
expectEqualSequences(
|
|
permutations,
|
|
[
|
|
["Alex", "Celeste"],
|
|
["Alex", "Davide"],
|
|
["Celeste", "Alex"],
|
|
["Celeste", "Davide"],
|
|
["Davide", "Alex"],
|
|
["Davide", "Celeste"],
|
|
])
|
|
}
|
|
|
|
func testDocumentationExample6() {
|
|
// From Permutations.swift
|
|
let names = ["Alex", "Celeste", "Davide"]
|
|
let permutations = names.permutations(ofCount: 1...2)
|
|
expectEqualSequences(
|
|
permutations,
|
|
[
|
|
["Alex"],
|
|
["Celeste"],
|
|
["Davide"],
|
|
["Alex", "Celeste"],
|
|
["Alex", "Davide"],
|
|
["Celeste", "Alex"],
|
|
["Celeste", "Davide"],
|
|
["Davide", "Alex"],
|
|
["Davide", "Celeste"],
|
|
])
|
|
}
|
|
}
|