Generate Array of Unique Random Numbers within Inc

问题:

I am trying to write a function in Apple Swift (iOS) that will generate any given amount of unique random numbers that are within a given inclusive range, say between 0 and 10. So if I say I want 5 unique random numbers between 0 and 10, it would return an array with [7, 10, 2, 3, 0] or [7, 10, 2, 8, 0], etc.

I have that part working with:

// Returns an array of unique numbers
func uniqueRandoms(numberOfRandoms: Int, minNum: Int, maxNum: UInt32) -> [Int] {

    var uniqueNumbers = [Int]()

    while uniqueNumbers.count < numberOfRandoms {

        let randomNumber = Int(arc4random_uniform(maxNum + 1)) + minNum
        var found = false

        for var index = 0; index < uniqueNumbers.count; ++index {
                if uniqueNumbers[index] == randomNumber {
                    found = true
                    break
                }
        }

        if found == false {
            uniqueNumbers.append(randomNumber)
        }

    }

    return uniqueNumbers
}

print(uniqueRandoms(5, minNum: 0, maxNum: 10))

Now I want to add the ability to blacklist a single number within that range that I don’t want. Say I still want 5 unique random numbers between 0 and 10 BUT I don’t want it to ever include 8.

That part causes an endless loop (25%+ of the time or more) and I can’t figure out why? Here’s what I have:

var blackListNum = 8

// Returns an array of unique numbers
func uniqueRandoms(numberOfRandoms: Int, minNum: Int, maxNum: UInt32, checkBlackList: Bool = false) -> [Int] {

    var uniqueNumbers = [Int]()

    while uniqueNumbers.count < numberOfRandoms {

        let randomNumber = Int(arc4random_uniform(maxNum + 1)) + minNum
        var found = false

        for var index = 0; index < uniqueNumbers.count; ++index {
            if checkBlackList == false {
                if uniqueNumbers[index] == randomNumber {
                    found = true
                    break
                }
            } else {
                if uniqueNumbers[index] == randomNumber || uniqueNumbers[index] == blackListNum  {
                    found = true
                    break
                }
            }
        }

        if found == false {
            uniqueNumbers.append(randomNumber)
        }

    }

    return uniqueNumbers
}

print(uniqueRandoms(5, minNum: 0, maxNum: 10, checkBlackList: true))

I understand that my function is far from efficient because I am just starting to learn Swift but I want to keep it similar as I want to understand how it works. I don’t want to simply copy and paste someone else’s more efficient solution and not understand it. I have just learned variables, constants, if, while, for, etc. statements and the other basics and want to keep it to that.

回答1:

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 Array(uniqueNumbers).shuffle
}

print(uniqueRandoms(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 Array(uniqueNumbers).shuffle
}

uniqueRandoms(3, minNum: 0, maxNum: 10, blackList: 8)  // [0, 10, 7]

You will need this extension to shuffle the result:

extension Array {
    var shuffle:[Element] {
        var elements = self
        for index in 0..<elements.count {
            let anotherIndex = Int(arc4random_uniform(UInt32(elements.count-index)))+index
            if anotherIndex != index {
                swap(&elements[index], &elements[anotherIndex])
            }
        }
        return elements
    }
}

回答2:

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.

回答3:

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.

回答4:

Here's my solution. SwiftStub:

extension Array {
    func shuffle() -> Array<Element> {
        var newArray = self

        for i in 0..<newArray.count {
            let j = Int(arc4random_uniform(UInt32(newArray.count)))
            guard i != j else { continue }
            swap(&newArray[i], &newArray[j])
        }

        return newArray
    }
}

func uniqueRandoms(count: Int, inRange range: Range<Int>, blacklist: [Int] = []) -> [Int] {
    var r = [Int](range)
        .filter{ !blacklist.contains($0) }
        .shuffle()

    return Array(r[0..<count])
}

let x = uniqueRandoms(5, inRange: 1...10000)
let y = uniqueRandoms(5, inRange: 1...10, blacklist: [2,4,6,8,10])
print(x)
print(y)

filter filters out the numbers on the black list.

shuffle is an extension added to the Array class. You implement it as a separate function if you want.

return Array(r[0..<count]) creates a new array from a Slice of the existing array.

This has a potential index out of bound bug when the list is smaller than the count asked for. For examples, these will crash:

let a = uniqueRandoms(10, inRange: 1...5)
let b = uniqueRandoms(3, inRange: 1...5, blacklist: [1,2,3,4])

Handling that is left as an exercise for the OP.

回答5:

// 1st version where I only blacklisted 8
var randomNumbers = [Int]()
for _ in 1...7 {
    var number = Int(arc4random_uniform(8))+1
    while  randomNumbers.contains(number) || number == 8{
        number = Int(arc4random_uniform(8))+1
    }
    randomNumbers.append(number)
}
print(randomNumbers)

// 2nd version where I created an array of blacklisted numbers
var randomNumbers = [Int]()
var blackList = [8, 5, 2, 7]
for _ in 1...3 {
    var number = Int(arc4random_uniform(10))+1
    while  randomNumbers.contains(number) || blackList.contains(number){
        number = Int(arc4random_uniform(10))+1
    }
    randomNumbers.append(number)
}
print(randomNumbers)

I created 2 empty arrays "randomNumbers" and "blackList" then set up a for loop statement. In the loop statement I initialize the variable "number." I assign "number" to a random number, then I use a while statement and .contians to check if "number" is already in the array "randomNumbers" or if the "number" is in the array "blackList" if either array contains "number," "number is reassigned until neither array contains "number". Then I randomNumbers.append(number) to append "number" into "randomNumbers" then the loop starts over again.

回答6:

so much easy way is :

  let UniqueIdNumber = CFUUIDCreateString(nil, CFUUIDCreate(nil))