1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
|
//===--------------- Permutations.swift - Swift Permutations --------------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2014 - 2019 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
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//
// Copied from StdlibCoreExtras.swift in StdlibUnittest.
enum FormNextPermutationResult {
case success
case formedFirstPermutation
}
extension MutableCollection
where
Self : BidirectionalCollection,
Iterator.Element : Comparable
{
mutating func _reverseSubrange(_ subrange: Range<Index>) {
if subrange.isEmpty { return }
var f = subrange.lowerBound
var l = index(before: subrange.upperBound)
while f < l {
swapAt(f, l)
formIndex(after: &f)
formIndex(before: &l)
}
}
mutating func formNextPermutation() -> FormNextPermutationResult {
if isEmpty {
// There are 0 elements, only one permutation is possible.
return .formedFirstPermutation
}
do {
var i = startIndex
formIndex(after: &i)
if i == endIndex {
// There is only element, only one permutation is possible.
return .formedFirstPermutation
}
}
var i = endIndex
formIndex(before: &i)
var beforeI = i
formIndex(before: &beforeI)
var elementAtI = self[i]
var elementAtBeforeI = self[beforeI]
while true {
if elementAtBeforeI < elementAtI {
// Elements at `i..<endIndex` are in non-increasing order. To form the
// next permutation in lexicographical order we need to replace
// `self[i-1]` with the next larger element found in the tail, and
// reverse the tail. For example:
//
// i-1 i endIndex
// V V V
// 6 2 8 7 4 1 [ ] // Input.
// 6 (4) 8 7 (2) 1 [ ] // Exchanged self[i-1] with the
// ^--------^ // next larger element
// // from the tail.
// 6 4 (1)(2)(7)(8)[ ] // Reversed the tail.
// <-------->
var j = endIndex
repeat {
formIndex(before: &j)
} while !(elementAtBeforeI < self[j])
swapAt(beforeI, j)
_reverseSubrange(i..<endIndex)
return .success
}
if beforeI == startIndex {
// All elements are in non-increasing order. Reverse to form the first
// permutation, where all elements are sorted (in non-increasing order).
reverse()
return .formedFirstPermutation
}
i = beforeI
formIndex(before: &beforeI)
elementAtI = elementAtBeforeI
elementAtBeforeI = self[beforeI]
}
}
}
/// Generate all permutations.
public func forAllPermutations(_ size: Int, _ body: ([Int]) -> Void) {
var data = Array(0..<size)
repeat {
body(data)
} while data.formNextPermutation() != .formedFirstPermutation
}
|
