-
-
Save dfrib/47a5ee4f393b5c55f3d9a0491f68f3e2 to your computer and use it in GitHub Desktop.
Temp
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// from MartinR:s | |
// http://codereview.stackexchange.com/questions/158798/on-knuths-algorithm-l-to-generate-permutations-in-lexicographic-order | |
extension Array where Element: Comparable { | |
// dfri> just changed the return type, and false/true return values to nil/self, respectively | |
mutating func permute() -> Array? { | |
// Nothing to do for empty or single-element arrays: | |
if count <= 1 { | |
return nil | |
} | |
// L2: Find last j such that self[j] <= self[j+1]. Terminate if no such j | |
// exists. | |
var j = count - 2 | |
while j >= 0 && self[j] > self[j+1] { | |
j -= 1 | |
} | |
if j == -1 { | |
return nil | |
} | |
// L3: Find last l such that self[j] <= self[l], then exchange elements j and l: | |
var l = count - 1 | |
while self[j] > self[l] { | |
l -= 1 | |
} | |
swap(&self[j], &self[l]) | |
// L4: Reverse elements j+1 ... count-1: | |
var lo = j + 1 | |
var hi = count - 1 | |
while lo < hi { | |
swap(&self[lo], &self[hi]) | |
lo += 1 | |
hi -= 1 | |
} | |
return self | |
} | |
} | |
// a downside: explicit 'nil' check / worse semantics | |
do { | |
var a = ["a", "b", "c"] | |
repeat { | |
print(a) | |
} while a.permute() != nil | |
} | |
// a possible upside> a possibly more natural consuming sequence (with no extra copies) | |
struct PermutationSequence<T: Comparable>: Sequence, IteratorProtocol { | |
private var current: [T]? | |
private var firstIteration = true | |
init(elements: [T]) { | |
self.current = elements.sorted() | |
} | |
mutating func next() -> [T]? { | |
if firstIteration { | |
firstIteration = false | |
return current | |
} | |
return current?.permute() | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
@dfrib Ah, I totally missed that bit in your comment! Looks good now :)