Files
Nate Cook 66ae806bbe Enable CI format check (#253)
* 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
2025-03-05 09:11:17 -06:00

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"],
])
}
}