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

130 lines
3.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 Algorithms
import XCTest
final class UniquePermutationsTests: XCTestCase {
static let numbers = [1, 1, 1, 2, 3]
static let numbersPermutations: [[[Int]]] = [
// k = 0
[[]],
// 1
[[1], [2], [3]],
// 2
[[1, 1], [1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [3, 2]],
// 3
[
[1, 1, 1], [1, 1, 2], [1, 1, 3],
[1, 2, 1], [1, 2, 3], [1, 3, 1], [1, 3, 2],
[2, 1, 1], [2, 1, 3], [2, 3, 1],
[3, 1, 1], [3, 1, 2], [3, 2, 1],
],
// 4
[
[1, 1, 1, 2], [1, 1, 1, 3],
[1, 1, 2, 1], [1, 1, 2, 3],
[1, 1, 3, 1], [1, 1, 3, 2],
[1, 2, 1, 1], [1, 2, 1, 3], [1, 2, 3, 1],
[1, 3, 1, 1], [1, 3, 1, 2], [1, 3, 2, 1],
[2, 1, 1, 1], [2, 1, 1, 3], [2, 1, 3, 1], [2, 3, 1, 1],
[3, 1, 1, 1], [3, 1, 1, 2], [3, 1, 2, 1], [3, 2, 1, 1],
],
// 5
[
[1, 1, 1, 2, 3], [1, 1, 1, 3, 2],
[1, 1, 2, 1, 3], [1, 1, 2, 3, 1],
[1, 1, 3, 1, 2], [1, 1, 3, 2, 1],
[1, 2, 1, 1, 3], [1, 2, 1, 3, 1], [1, 2, 3, 1, 1],
[1, 3, 1, 1, 2], [1, 3, 1, 2, 1], [1, 3, 2, 1, 1],
[2, 1, 1, 1, 3], [2, 1, 1, 3, 1], [2, 1, 3, 1, 1], [2, 3, 1, 1, 1],
[3, 1, 1, 1, 2], [3, 1, 1, 2, 1], [3, 1, 2, 1, 1], [3, 2, 1, 1, 1],
],
]
}
extension UniquePermutationsTests {
func testEmpty() {
expectEqualSequences(([] as [Int]).uniquePermutations(), [[]])
expectEqualSequences(([] as [Int]).uniquePermutations(ofCount: 0), [[]])
expectEqualSequences(([] as [Int]).uniquePermutations(ofCount: 1), [])
expectEqualSequences(
([] as [Int]).uniquePermutations(ofCount: 1...3), [])
}
func testSingleCounts() {
for (k, expectation) in Self.numbersPermutations.enumerated() {
expectEqualSequences(
expectation,
Self.numbers.uniquePermutations(ofCount: k))
}
expectEqualSequences(
Self.numbersPermutations[5],
Self.numbers.uniquePermutations())
}
func testRanges() {
for lower in Self.numbersPermutations.indices {
// upper bounded
expectEqualSequences(
Self.numbersPermutations[...lower].joined(),
Self.numbers.uniquePermutations(ofCount: ...lower))
// lower bounded
expectEqualSequences(
Self.numbersPermutations[lower...].joined(),
Self.numbers.uniquePermutations(ofCount: lower...))
for upper in lower..<Self.numbersPermutations.count {
expectEqualSequences(
Self.numbersPermutations[lower..<upper].joined(),
Self.numbers.uniquePermutations(ofCount: lower..<upper))
}
}
}
}
extension UniquePermutationsTests {
private final class IntBox: Hashable {
var value: Int
init(_ value: Int) {
self.value = value
}
static func == (lhs: IntBox, rhs: IntBox) -> Bool {
lhs.value == rhs.value
}
func hash(into hasher: inout Hasher) {
hasher.combine(value)
}
}
func testFirstUnique() {
// When duplicate elements are encountered, all permutations use the first
// instance of the duplicated elements.
let numbers = Self.numbers.map(IntBox.init)
for k in 0...numbers.count {
for p in numbers.uniquePermutations(ofCount: k) {
XCTAssertTrue(
p.filter { $0.value == 1 }.allSatisfy { $0 === numbers[0] })
}
}
}
func testLaziness() {
requireLazySequence("ABCD".lazy.uniquePermutations())
}
}