0001 // MARK: - Common 0002 0003 public extension MutableCollectionType { 0004 0005 /// [Algorithm](https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order) 0006 0007 public mutating func nextLexPerm0008 (isOrderedBefore: (Generator.Element, Generator.Element) -> Bool) -> Self? { 0009 for k in indices.reverse().dropFirst() 0010 where isOrderedBefore(self[k], self[k.successor()]) { 0011 for l in indices.reverse() where isOrderedBefore(self[k], self[l]) { 0012 swap(&self[k], &self[l]) 0013 let r = (k.successor()..<endIndex) 0014 for (x, y) in zip(r, r.reverse()) { 0015 if x == y || x == y.successor() { return self } 0016 swap(&self[x], &self[y]) 0017 } 0018 } 0019 } 0020 return nil 0021 } 0022 } 0023 0024 public extension MutableCollectionType where Generator.Element : Comparable { 0025 0026 /// [Algorithm](https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order) 0027 0028 public mutating func nextLexPerm() -> Self? { 0029 return nextLexPerm(<) 0030 } 0031 } 0032 /// :nodoc: 0033 public struct LexPermGen
Permutations.swift:29 Permutations.swift:38 defer { col = col?.nextLexPerm(order) }<C
Permutations.swift:47 public func generate() -> LexPermGen<C> {Permutations.swift:48 : MutableCollectionType> : GeneratorType { 0034 private var col
Permutations.swift:34 Permutations.swift:35 Permutations.swift:35 Permutations.swift:37 mutating public func next() -> C? {: C? 0035 private let order
Permutations.swift:38 defer { col = col?.nextLexPerm(order) }Permutations.swift:38 defer { col = col?.nextLexPerm(order) }Permutations.swift:39 : (C.Generator.Element, C.Generator.Element) -> Bool 0036 /// :nodoc: 0037 mutating public func next() -> C? { 0038 defer { col = col?.nextLexPerm(order) } 0039 return col 0040 } 0041 } 0042 /// :nodoc: 0043 public struct LexPermSeq
Permutations.swift:38 defer { col = col?.nextLexPerm(order) }<C
Permutations.swift:73 Permutations.swift:94 Permutations.swift:109 return Array(LexPermSeq(col: Array(col.indices), order: <).map { inds in inds.map{col[$0]} })Permutations.swift:142 -> LexPermSeq<[Generator.Element]> {Permutations.swift:143 Permutations.swift:163 public func lazyLexPermutations() -> LexPermSeq<[Generator.Element]> {Permutations.swift:164 Permutations.swift:183 public func lazyPermutations() -> LazyMapSequence<LexPermSeq<[Int]>, [Self.Generator.Element]> {: MutableCollectionType> : LazySequenceType { 0044 private let col
Permutations.swift:44 Permutations.swift:45 Permutations.swift:45 Permutations.swift:47 public func generate() -> LexPermGen<C> {: C 0045 private let order
Permutations.swift:48 : (C.Generator.Element, C.Generator.Element) -> Bool 0046 /// :nodoc: 0047 public func generate() -> LexPermGen<C> { 0048 return LexPermGen(col: col, order: order) 0049 } 0050 } 0051 0052 // MARK: - Eager 0053 0054 public extension SequenceType { 0055 0056 /// Returns an array of the permutations of self, ordered lexicographically, according 0057 /// to the closure `isOrderedBefore`. 0058 /// - Note: The permutations returned follow self, so if self is not the first 0059 /// lexicographically ordered permutation, not all permutations will be returned. 0060 /// ```swift 0061 /// [1, 2, 3].lexPermutations(<) 0062 /// 0063 /// [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]] 0064 /// ``` 0065 /// ```swift 0066 /// [1, 2, 3].lexPermutations(>) 0067 /// 0068 /// [[1, 2, 3]] 0069 /// ``` 0070 @warn_unused_result 0071 public func lexPermutations 0072 (isOrderedBefore: (Generator.Element, Generator.Element) -> Bool) -> [[Generator.Element]] { 0073 return Array(LexPermSeq(col: Array(self), order: isOrderedBefore)) 0074 } 0075 } 0076 0077 public extension MutableCollectionType where Generator.Element : Comparable { 0078 0079 /// Returns an array of the permutations of self, ordered lexicographically. 0080 /// - Note: The permutations returned follow self, so if self is not the first 0081 /// lexicographically ordered permutation, not all permutations will be returned. 0082 /// ```swift 0083 /// [1, 2, 3].lexPermutations() 0084 /// 0085 /// [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]] 0086 /// ``` 0087 /// ```swift 0088 /// [3, 2, 1].lexPermutations() 0089 /// 0090 /// [[3, 2, 1]] 0091 /// ``` 0092 @warn_unused_result 0093 public func lexPermutations() -> [[Generator.Element]] { 0094 return Array(LexPermSeq(col: Array(self), order: <)) 0095 } 0096 } 0097 0098 public extension SequenceType { 0099 0100 /// Returns an array of the permutations of self. 0101 /// ```swift 0102 /// [1, 2, 3].permutations() 0103 /// 0104 /// [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]] 0105 /// ``` 0106 @warn_unused_result 0107 public func permutations
Permutations.swift:48 () -> [[Generator.Element]] { 0108 var col = Array(self) 0109 return Array(LexPermSeq(col: Array(col.indices), order: <).map { inds in inds.map{col[$0]} }) 0110 } 0111 /// Returns an array of the permutations of length `n` of self. 0112 /// ```swift 0113 /// [1, 2, 3].permutations() 0114 /// 0115 /// [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]] 0116 /// ``` 0117 public func permutations(n: Int) -> [[Generator.Element]] { 0118 return Array(lazyCombos(n).flatMap { a in a.permutations() }) 0119 } 0120 } 0121 0122 // MARK: - Lazy 0123 0124 public extension SequenceType { 0125 0126 /// Returns a lazy sequence of the permutations of self, ordered lexicographically, 0127 /// according to the closure `isOrderedBefore`. 0128 /// - Note: The permutations returned follow self, so if self is not the first 0129 /// lexicographically ordered permutation, not all permutations will be returned. 0130 /// ```swift 0131 /// lazy([1, 2, 3]).lazyLexPermutations(<) 0132 /// 0133 /// [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1] 0134 /// ``` 0135 /// ```swift 0136 /// lazy([1, 2, 3]).lazyLexPermutations(>) 0137 /// 0138 /// [1, 2, 3] 0139 /// ``` 0140 @warn_unused_result 0141 public func lazyLexPermutations(isOrderedBefore: (Generator.Element, Generator.Element) -> Bool) 0142 -> LexPermSeq<[Generator.Element]> { 0143 return LexPermSeq(col: Array(self), order: isOrderedBefore) 0144 } 0145 } 0146 0147 public extension SequenceType where Generator.Element : Comparable { 0148 0149 /// Returns a lazy sequence of the permutations of self, ordered lexicographically. 0150 /// - Note: The permutations returned follow self, so if self is not the first 0151 /// lexicographically ordered permutation, not all permutations will be returned. 0152 /// ```swift 0153 /// lazy([1, 2, 3]).lazyLexPermutations() 0154 /// 0155 /// [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1] 0156 /// ``` 0157 /// ```swift 0158 /// lazy([3, 2, 1]).lazyLexPermutations() 0159 /// 0160 /// [3, 2, 1] 0161 /// ``` 0162 @warn_unused_result 0163 public func lazyLexPermutations
Permutations.swift:118 return Array(lazyCombos(n).flatMap { a in a.permutations() })() -> LexPermSeq<[Generator.Element]> { 0164 return LexPermSeq(col: Array(self), order: <) 0165 } 0166 } 0167 0168 public extension SequenceType { 0169 0170 /// Returns a lazy sequence of the permutations of self. 0171 /// - Note: The permutations are lexicographically ordered, based on the indices of self 0172 /// ```swift 0173 /// lazy([1, 2, 3]).lazyPermutations() 0174 /// 0175 /// [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1] 0176 /// ``` 0177 /// ```swift 0178 /// lazy([3, 2, 1]).lazyPermutations() 0179 /// 0180 /// [3, 2, 1], [3, 1, 2], [2, 3, 1], [2, 1, 3], [1, 3, 2], [1, 2, 3] 0181 /// ``` 0182 @warn_unused_result 0183 public func lazyPermutations() -> LazyMapSequence<LexPermSeq<[Int]>, [Self.Generator.Element]> { 0184 let col = Array(self) 0185 return col.indices.lazyLexPermutations().map { $0.map { col[$0] } } 0186 } 0187 } 0188
Permutations.swift:185 return col.indices.lazyLexPermutations().map { $0.map { col[$0] } }