Generate Array of Unique Random Numbers within Inclusive Range
You could make your live much easier using a Set to store all random numbers until you reach the expected number of randoms:
func uniqueRandoms(numberOfRandoms: Int, minNum: Int, maxNum: UInt32) -> [Int] {
var uniqueNumbers = Set<Int>()
while uniqueNumbers.count < numberOfRandoms {
uniqueNumbers.insert(Int(arc4random_uniform(maxNum + 1)) + minNum)
}
return uniqueNumbers.shuffled()
}
print(uniqueRandoms(numberOfRandoms: 5, minNum: 0, maxNum: 10))
func uniqueRandoms(numberOfRandoms: Int, minNum: Int, maxNum: UInt32, blackList: Int?) -> [Int] {
var uniqueNumbers = Set<Int>()
while uniqueNumbers.count < numberOfRandoms {
uniqueNumbers.insert(Int(arc4random_uniform(maxNum + 1)) + minNum)
}
if let blackList = blackList {
if uniqueNumbers.contains(blackList) {
while uniqueNumbers.count < numberOfRandoms+1 {
uniqueNumbers.insert(Int(arc4random_uniform(maxNum + 1)) + minNum)
}
uniqueNumbers.remove(blackList)
}
}
return uniqueNumbers.shuffled()
}
uniqueRandoms(numberOfRandoms: 3, minNum: 0, maxNum: 10, blackList: 8) // [0, 10, 7]
A straight forward approach is to create an array of numbers to choose from and then remove the numbers as you choose them:
// create an array of 0 through 10
var nums = Array(0...10)
// remove the blacklist number
nums.removeAtIndex(nums.indexOf(8)!)
var randoms = [Int]()
for _ in 1...5 {
let index = Int(arc4random_uniform(UInt32(nums.count)))
randoms.append(nums[index])
nums.removeAtIndex(index)
}
The advantage of this method is that you only need to generate as many random numbers as you want values in your array. Since you are selecting from the numbers that are still available each time, you never have to check to see if you already have a random value.
Solutions and Performance breakdown in Swift 4.0
I recently found myself needing a solution to this very same problem, but without the blacklist, and I saw answers on this page and also over at this question, but I was concerned about performance when the set of numbers to choose from was very large and also when choosing a lot of numbers (like, to where you're choosing more than 50% of the numbers in the overall pool).
So I tried out a few solutions.
The first was the kind where you choose a number at random, check if the number has already been chosen before, and either choose a different one or add it to the list of numbers.
func randomNumber(between lower: Int, and upper: Int) -> Int {
return Int(arc4random_uniform(UInt32(upper - lower))) + lower
}
func generateRandomUniqueNumbers1(forLowerBound lower: Int, andUpperBound upper:Int, andNumNumbers iterations: Int) -> [Int] {
guard iterations <= (upper - lower) else { return [] }
var numbers: [Int] = []
(0..<iterations).forEach { _ in
var nextNumber: Int
repeat {
nextNumber = randomNumber(between: lower, and: upper)
} while numbers.contains(nextNumber)
numbers.append(nextNumber)
}
return numbers
}
The second solution is pretty much the same as the one that vacawama is suggesting. You start by loading up an array of all the available numbers, choose one at random, and remove it from the available array, and add it to your numbers array. Repeat for as many numbers as you want.
func generateRandomUniqueNumbers2(forLowerBound lower: Int, andUpperBound upper:Int, andNumNumbers iterations: Int) -> [Int] {
guard iterations <= (upper - lower) else { return [] }
var indices: [Int] = (lower..<upper).sorted()
var numbers: [Int] = []
(0..<iterations).forEach { _ in
let nextNumberIndex = randomNumber(between: 0, and: indices.count)
let nextNumber: Int = indices[nextNumberIndex]
indices.remove(at: nextNumberIndex)
numbers.append(nextNumber)
}
return numbers
}
The third solution was an adaptation of the first solution to address the fact that arrays are slow at finding elements within them. By changing the stored numbers array to a Set, that operation should be faster.
func generateRandomUniqueNumbers3(forLowerBound lower: Int, andUpperBound upper:Int, andNumNumbers iterations: Int) -> [Int] {
guard iterations <= (upper - lower) else { return [] }
var numbers: Set<Int> = Set<Int>()
(0..<iterations).forEach { _ in
let beforeCount = numbers.count
repeat {
numbers.insert(randomNumber(between: lower, and: upper))
} while numbers.count == beforeCount
}
return numbers.map{ $0 }
}
I was pretty sure that solution 1 would bog down in situations like where you have 100 numbers to choose from, and you want 90 unique ones. By the time you are choosing the 80th number, you only have a 20% chance of choosing one that hasn't been chosen yet. And it scales really badly if you have like 5000 numbers and you still want 90% of them.
I figured that solution 2 would handle it better, but I wasn't sure what kind of a performance hit removing so many values from a large array would have.
I wasn't sure what to make of solution 3. Probably somewhere in the middle was my guess.
I set up XCTest to measure some performance on both algorithms under different load conditions. There were 2 parameters: population and density. Population is the total number of numbers to choose from, and density is what percentage of the population that we wanted to pull out (ie: a population of 80 means 80 numbers to choose from, and a density of 50% means we want to choose 40 unique numbers at random from the population of 80).
I did 9 tests for each combination of 3 different populations (5, 250, and 12,500) and density values (10%, 50%, and 90%). Depending on how quickly or slowly the test was able to finish, I adjusted how many iterations of the test I performed (varied from just one pass to as many as 2,500 passes).
These were the results:
Solution 1
(Population: 5; Density: 10%; Iterations: 2,500): 0.0056s
(Population: 250; Density: 10%; Iterations: 50) : 0.0046s
(Population: 12,500; Density: 10%; Iterations: 10) : 1.33s
(Population: 5; Density: 50%; Iterations: 2,500): 0.0131s
(Population: 250; Density: 50%; Iterations: 50) : 0.0912s
(Population: 12,500; Density: 50%; Iterations: 1) : 4.09s
(Population: 5; Density: 90%; Iterations: 2,500): 0.0309s
(Population: 250; Density: 90%; Iterations: 10) : 0.0993s
(Population: 12,500; Density: 90%; Iterations: 1) : 23s
Solution 2
(Population: 5; Density: 10%; Iterations: 2,500): 0.0184s
(Population: 250; Density: 10%; Iterations: 50) : 0.0086s
(Population: 12,500; Density: 10%; Iterations: 10) : 0.103s
(Population: 5; Density: 50%; Iterations: 2,500): 0.0233s
(Population: 250; Density: 50%; Iterations: 50) : 0.0125s
(Population: 12,500; Density: 50%; Iterations: 1) : 0.0209s
(Population: 5; Density: 90%; Iterations: 2,500): 0.0242s
(Population: 250; Density: 90%; Iterations: 10) : 0.0046s
(Population: 12,500; Density: 90%; Iterations: 1) : 0.0278s
Solution 3
(Population: 5; Density: 10%; Iterations: 2,500): 0.00672s
(Population: 250; Density: 10%; Iterations: 50) : 0.0024s
(Population: 12,500; Density: 10%; Iterations: 10) : 0.0148s
(Population: 5; Density: 50%; Iterations: 2,500): 0.0134s
(Population: 250; Density: 50%; Iterations: 50) : 0.00769s
(Population: 12,500; Density: 50%; Iterations: 1) : 0.00789s
(Population: 5; Density: 90%; Iterations: 2,500): 0.0209s
(Population: 250; Density: 90%; Iterations: 10) : 0.00397s
(Population: 12,500; Density: 90%; Iterations: 1) : 0.0163s
Comparison
(Case 1): Solution 1 is fastest; then 3; then 2
(Case 2): Solution 3 is fastest; then 1; then 2
(Case 3): Solution 3 is fastest; then 2; then 3
(Case 4): Solution 1 is fastest; then 3; then 2
(Case 5): Solution 3 is fastest; then 2; then 1
(Case 6): Solution 3 is fastest; then 2; then 1
(Case 7): Solution 3 is fastest; then 2; then 1
(Case 8): Solution 3 is fastest; then 2; then 1
(Case 9): Solution 3 is fastest; then 2; then 1
Conclusion
As I suspected from the first solution, it really bogged down with large populations and high densities. It's still plenty quick when you don't have that much population or when you are only choosing like 2 numbers, but all solutions were pretty fast overall in those conditions. Even if it was the case that solution 1 could choose 25 random numbers from a population of 250 faster than solution 2 or 3 could, the real-time difference was pretty small.
However, it's useful to point out that if you want very few unique numbers from a really large population (ie: 2 unique numbers from a pool of 12,500), solution 1 is fastest, about 77% faster than solution 3, and both are orders of magnitude faster than solution 2. For my specific case, that's closer to what I will be doing almost all the time, so I will probably make a specific function that uses solution 1 for specifically choosing 2 unique numbers from a large pool of data.
Overall, solution 3 is pretty close to an all-around best algorithm. But with large data sets, consider each of these solutions based on what you plan on using them for.