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
130 lines
3.7 KiB
Swift
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())
|
|
}
|
|
}
|