Skip to content

Instantly share code, notes, and snippets.

@glessard glessard/shuffle.swift
Last active Jun 29, 2018

Embed
What would you like to do?
Shuffle a CollectionType
//
// shuffle.swift
//
// Created by Guillaume Lessard on 2014-08-28.
// Copyright (c) 2016 Guillaume Lessard. All rights reserved.
//
// https://github.com/glessard/shuffle
// https://gist.github.com/glessard/7140fe885af3eb874e11
//
#if os(Linux)
import func Glibc.random
#else
import func Darwin.C.stdlib.arc4random_uniform
#endif
/// Get a sequence/generator that will return a collection's elements in a random order.
/// The input collection is not modified.
///
/// - parameter c: The collection to be shuffled
/// - returns: A sequence of of `c`'s elements, lazily shuffled.
public func shuffle<C: Collection>(_ c: C) -> ShuffledSequence<C>
{
return ShuffledSequence(c)
}
public extension Collection where Self.Indices.Iterator.Element == Self.Index
{
/// Get a sequence/generator that will return a collection's elements in a random order.
/// The input collection is not modified.
///
/// - returns: A sequence of of `self`'s elements, lazily shuffled.
public func shuffled() -> ShuffledSequence<Self>
{
return ShuffledSequence(self)
}
}
/// A stepwise implementation of the Knuth Shuffle (a.k.a. Fisher-Yates Shuffle).
/// The input collection is not modified: the shuffling itself is done
/// using an adjunct array of indices.
public struct ShuffledSequence<C: Collection>: Sequence, IteratorProtocol
where C.Indices.Iterator.Element == C.Index
{
public let collection: C
private var shuffler: IndexShuffler<C.Index>
public init(_ input: C)
{
collection = input
shuffler = IndexShuffler(input.indices)
}
public mutating func next() -> C.Iterator.Element?
{
if let index = shuffler.next()
{
return collection[index]
}
return nil
}
public var underestimatedCount: Int {
return shuffler.underestimatedCount
}
}
/// A stepwise (lazy-ish) implementation of the Knuth Shuffle (a.k.a. Fisher-Yates Shuffle),
/// using a sequence of indices for the input. Elements (indices) from
/// the input sequence are returned in a random order until exhaustion.
public struct IndexShuffler<Index>: Sequence, IteratorProtocol
{
public let last: Int
public private(set) var step: Int
private var i: [Index]
public init<S: Sequence>(_ input: S)
where S.Iterator.Element == Index
{
self.init(Array(input))
}
public init(_ input: Array<Index>)
{
i = input
step = i.startIndex
last = i.endIndex
}
public mutating func next() -> Index?
{
if step < last
{
// select a random Index from the rest of the array
#if os(Linux)
let j = step + Int(random() % (last-step)) // with slight modulo bias
#else
let j = step + Int(arc4random_uniform(UInt32(last-step)))
#endif
// swap that Index with the Index present at the current step in the array
if j != step
{
swap(&i[j], &i[step])
}
defer { step += 1 }
// return the new random Index.
return i[step]
}
return nil
}
public var underestimatedCount: Int {
return (last - step)
}
}
@scottrhoyt

This comment has been minimized.

Copy link

scottrhoyt commented Sep 1, 2015

I like it. Cool work and useful!

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.