Skip to content

Instantly share code, notes, and snippets.

@hamishknight hamishknight/main.swift Secret
Last active Jan 2, 2018

Embed
What would you like to do?
extension RandomAccessCollection {
func first(where predicate: (Iterator.Element) throws -> Bool) rethrows -> Iterator.Element? {
for element in self {
if try predicate(element) {
return element
}
}
return nil
}
}
extension Array {
mutating func reverse(indices: Range<Index>) {
if isEmpty || indices.isEmpty { return }
var low = indices.lowerBound
var high = index(before: indices.upperBound)
while low < high {
swap(&self[low], &self[high])
formIndex(after: &low)
formIndex(before: &high)
}
}
}
extension Array where Element : Comparable {
mutating func permute() -> Bool {
// Nothing to do for empty or single-element arrays:
if count <= 1 {
return false
}
// L2: Find last j such that self[j] <= self[j+1]. Terminate if no such j
// exists.
guard let j = indices.reversed().dropFirst()
.first(where: { self[$0] <= self[$0 + 1] })
else { return false }
// L3: Find last l such that self[j] <= self[l], then exchange elements j and l:
let l = indices.reversed()
.first(where: { self[j] <= self[$0] })!
swap(&self[j], &self[l])
// L4: Reverse elements j + 1 ... count - 1:
reverse(indices: Range(uncheckedBounds: (lower: j + 1, upper: count)))
return true
}
}
@PaulTaykalo

This comment has been minimized.

Copy link

PaulTaykalo commented Jan 2, 2018

Using flatmap will speed up this one up to ~30%

    mutating func permute2() -> Bool {

        // Nothing to do for empty or single-element arrays:
        guard count > 1 else { return false }


        guard let (j,l) = indices.reversed().dropFirst()
            .first(where: { self[$0] <= self[$0 + 1] })
            .flatMap({ j in
                // L3: Find last l such that self[j] <= self[l], then exchange elements j and l:
                (indices.reversed().first(where: { self[j] <= self[$0] })).map { (j, $0)}
            })
            else { return false }

        self.swapAt(j, l)

        // L4: Reverse elements j + 1 ... count - 1:
        reverse(indices: Range(uncheckedBounds: (lower: j + 1, upper: count)))

        return true
    }
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.