Randomly choosing an item from a Swift array without repeating

Question

This code picks a random color from a array of pre-set colors. How do I make it so the same color doesn't get picked more than once?

var colorArray = [(UIColor.redColor(), "red"), (UIColor.greenColor(), "green"), (UIColor.blueColor(), "blue"), (UIColor.yellowColor(), "yellow"), (UIColor.orangeColor(), "orange"), (UIColor.lightGrayColor(), "grey")]

var random = { () -> Int in
    return Int(arc4random_uniform(UInt32(colorArray.count)))
} // makes random number, you can make it more reusable


var (sourceColor, sourceName) = (colorArray[random()])

You could save an array of selected colors or indexes and if check the color or index is contained in the array when the button is touched. — kye, Mar 27 '16 at 23:32
there is a lot of nice and clear solutions. sometimes the simplest is the best. i recommend you achi's solution. the reason why this work is that arc4random_uniform generates stream of numbers not only randomly but also uniformly. — user3441734, Mar 28 '16 at 06:13

Duncan C · Accepted Answer · 2017-11-24T19:41:54.567

7

Create an array of indexes. Remove one of the indexes from the array and then use that to fetch a color.

Something like this:

var colorArray = [
  (UIColor.redColor(), "red"), 
  (UIColor.greenColor(), "green"), 
  (UIColor.blueColor(), "blue"), 
  (UIColor.yellowColor(), "yellow"), 
  (UIColor.orangeColor(), "orange"), 
  (UIColor.lightGrayColor(), "grey")]

var indexes = [Int]();

func randomItem() -> UIColor
{
  if indexes.count == 0
  {
    print("Filling indexes array")
    indexes = Array(0..< colorArray.count)
  }
  let randomIndex = Int(arc4random_uniform(UInt32(indexes.count)))
  let anIndex = indexes.removeAtIndex(randomIndex)
  return colorArray[anIndex].0;
}

The code above creates an array indexes. The function randomItem looks to see if indexes is empty. if it is, it populates it with index values ranging from 0 to colorArray.count - 1.

It then picks a random index in the indexes array, removes the value at that index in the indexes array, and uses it to fetch and return an object from your colorArray. (It doesn't remove objects from the colorArray. It uses indirection, and removes objects from the indexesArray, which initially contains an index value for each entry in your colorArray.

The one flaw in the above is that after you fetch the last item from indexArray, you populate it with a full set of indexes, and it's possible that the next color you get from the newly repopulated array will be the same as the last one you got.

It's possible to add extra logic to prevent this.

edited Nov 24 '17 at 19:41

answered Mar 27 '16 at 23:39

Duncan C

128,072
22
173
272

mistake, need to be `return colorArray[anIndex].0` – dimpiax Mar 28 '16 at 01:59
I guess you're right, it's an array of tuples, isn't it? I didn't look that closely at the OPs data structure. I wrote my code to fetch a random, non-repeating element from an array of SOMETHING. It could be generalized to an array of *anything* using generics. – Duncan C Mar 28 '16 at 03:06
in this case, this function must be abstract. And I would use for readability `stride` filling for array, instead of range. – dimpiax Mar 28 '16 at 09:13
@dimpiax Why not post your version of the answer with the enhancements you suggest? I'm still weak with generics, and not sure what you mean using stride. – Duncan C Mar 28 '16 at 11:22
lol here is nervous in air, or what? Check my post below with two approaches. – dimpiax Mar 28 '16 at 14:33
I actually prefer `indexes = Array(0 ..< colorArray.count)` to using stride. – Duncan C Nov 24 '17 at 19:41

user3441734 · Answer 2 · 2016-03-30T07:57:59.340

based on the fact, that arc4random_uniform generate not only random, but also uniformly distributed numbers

import Foundation // arc4random_uniform

class Random {
    var r:UInt32
    let max: UInt32
    init(max: UInt32) {
        self.max = max
        r = arc4random_uniform(max)
    }
    var next: UInt32 {
        var ret: UInt32
        repeat {
            ret = arc4random_uniform(max)
        } while r == ret
        r = ret
        return r
    }
}
// usage example
let r = Random(max: 5)
for i in 0..<10 {
    print(r.r, r.next) // there will never be a pair of the same numbers in the
    // generated stream
}
/*
 2 4
 4 0
 0 3
 3 0
 0 3
 3 4
 4 1
 1 3
 3 4
 4 3
 */

simple test for different k and stream length of one milion

class Random {
    var r:UInt32
    let max: UInt32
    init(max: UInt32) {
        self.max = max
        r = arc4random_uniform(max)
    }
    var next: (UInt32, Int) {
        var i = 0
        var ret: UInt32
        repeat {
            ret = arc4random_uniform(max)
            i += 1
        } while r == ret
        r = ret
        return (r,i)
    }
}
for k in 3..<16 {
    let r = Random(max: UInt32(k))
    var repetition = 0
    var sum = 0
    for i in 0..<1000000 {
        let j = r.next
        repetition = max(repetition, j.1)
        sum += j.1
    }
    print("maximum of while repetition for k:", k, "is", repetition, "with average of", Double(sum) / Double(1000000) )
}

prints

maximum of while repetition for k: 3 is 15 with average of 1.499832
maximum of while repetition for k: 4 is 12 with average of 1.334008
maximum of while repetition for k: 5 is 9 with average of 1.250487
maximum of while repetition for k: 6 is 8 with average of 1.199631
maximum of while repetition for k: 7 is 8 with average of 1.167501
maximum of while repetition for k: 8 is 7 with average of 1.142799
maximum of while repetition for k: 9 is 8 with average of 1.124096
maximum of while repetition for k: 10 is 6 with average of 1.111178
maximum of while repetition for k: 11 is 7 with average of 1.099815
maximum of while repetition for k: 12 is 7 with average of 1.091041
maximum of while repetition for k: 13 is 6 with average of 1.083582
maximum of while repetition for k: 14 is 6 with average of 1.076595
maximum of while repetition for k: 15 is 6 with average of 1.071965

finaly, here is more Swifty and functional approach based on the same idea

import Foundation

func random(max: Int)->()->Int {
    let max = UInt32(max)
    var last = arc4random_uniform(max)
    return {
        var r = arc4random_uniform(max)
        while r == last {
            r = arc4random_uniform(max)
        }
        last = r
        return Int(last)
    }
}

let r0 = random(8)
let r1 = random(4)
for i in 0..<20 {
    print(r0(), terminator: " ")
}
print("")
for i in 0..<20 {
    print(r1(), terminator: " ")
}

/*
 4 5 4 3 4 0 5 6 7 3 6 7 5 4 7 4 7 2 1 6
 0 3 0 1 0 2 3 1 2 0 1 0 1 0 1 3 0 3 0 2
 */

score 1 · Answer 3 · edited May 23 '17 at 10:29

Fill an array with the colors and shuffle it with a Fisher-Yates shuffle. Then use the element at an end, remove it, and insert it at a random position at least n positions from the end.

For example, say my array has 10 elements. I shuffle it and take the last. I want at least 2 values to be chosen before I see it again so I generate a random position in the range 0...8 and insert it there.

var colorArray = [
  (UIColor.redColor()      , "red"   ),
  (UIColor.greenColor()    , "green" ),
  (UIColor.blueColor()     , "blue"  ),
  (UIColor.yellowColor()   , "yellow"),
  (UIColor.orangeColor()   , "orange"),
  (UIColor.lightGrayColor(), "grey"  )].shuffle() // shuffle() is from my link above

let spacing = 2 // Pick at least 2 colors before we see it again
if let randomColor = colorArray.popLast() {
  colorArray.insert(randomColor,
                    atIndex: Int(arc4random_uniform(UInt32(colorArray.count - spacing))))
}

score 0 · Answer 4 · answered Mar 28 '16 at 14:32

One case, described here: https://github.com/dimpiax/GenericSequenceType

Another is functional:

func getRandomItem<T>(arr: [T]) -> (unique: Bool) -> T {
    var indexes: [Int]!

    return { value in
        let uniqIndex: Int

        if value {
            if indexes?.isEmpty != false {
                indexes = [Int](0.stride(to: arr.count, by: 1))
            }

            uniqIndex = indexes.removeAtIndex(Int(arc4random_uniform(UInt32(indexes.count))))
        }
        else {
            uniqIndex = Int(arc4random_uniform(UInt32(arr.count)))
        }
        return arr[uniqIndex]
    }
}

let generate = getRandomItem(colorArray)
generate(unique: true).0 // greenColor
generate(unique: true).0 // redColor
generate(unique: true).0 // lightGrayColor

score 0 · Answer 5 · answered Jan 02 '20 at 05:31

Try it it's work for me and 100% tested

let arrString = ["1","2","3","4","5","6"]
var selectedIndix = -1

@IBAction func btnClick(_ sender: Any) {

    let randomElementIndex = randomElementString()
}

Call this function when button clicked

func randomElementString() -> Int{

    let randomm = Int(arc4random_uniform(UInt32(arrString.count)))

    if selectedIndix == randomm{
        return randomElementString()
    }else{
        selectedIndix = randomm
        return randomm
    }
}

OUTPUT:-

5121242316513126

esreli · Answer 6 · 2016-03-28T16:16:06.237

-2

How about running a while loop with the condition:

while(self.source.backgroundColor == sourceColor) {
  // get a new random sourceColor
}

This will keep looping until a new random color has been selected.

edit

Additional Note: The point was the while loop. There are ways to safeguard from an infinite loop, it's up to the coder to find the right solution. I don't think SO is a place to write other's code but instead to offer suggestions .. mine is a start.

But since my answer was given such a negative rating, i'll push instead of nudge in the right direction.

The other answers are unnecessarily bloated. And? The one I offered above offers a less than desirable time complexity. So, here's my new answer (in meta code):

// array of all background colors
var arrayOfColors = [..]

// get a random index
var randomIndex = arc4random(size of arrayOfColors)

// select new background color
var newBGColor = arrayOfColors[randomIndex]

// old background color
var oldBGColor = self.source.backgroundColor

// remove new color from array (so that it's excluded from choices next time)
arrayOfColors.removeAtIndex(randomIndex)

// set the new color to the background
self.source.backgroundColor = newBGColor

// add current color back into the pool of potential colors
arrayOfColors.addObject(oldBGColor)

edited Mar 28 '16 at 16:16

answered Mar 28 '16 at 02:03

esreli

4,993
2
26
40

While this solution can work it has the possibility of looping forever, however unlikely. It's also potentially slow if you get a string of bad randoms. – Mar 28 '16 at 04:26
1

@KennethBruno using arc4random_uniform, the possibility of looping forever is ZERO, if number of colors > 2. More colors, less potential to be slow ... In practice, this solution is very efficient and perfectly fits OP needs. You are welcome to test it :-) – user3441734 Mar 28 '16 at 06:06
Out of interest i tried the while loop there because I initially thought this might be how to do it. this is how i used it but it give a EXC_BAD_ACCESS if a color wants to come up twice. this is how i tried to use it. – Mar 28 '16 at 10:16
var background = self.source.backgroundColor while(last == background) { hello() } – Mar 28 '16 at 10:18
The point was the while loop. There are ways to safeguard from an infinite loop, it's up to the coder to find the right solution. I don't think SO is a place to write other's code but instead to offer suggestions .. mine is a start – esreli Mar 28 '16 at 15:57
@PeterGaffney peep my revised answer. It's the easiest to understand and offers the best time & space complexity – esreli Mar 28 '16 at 16:16

Randomly choosing an item from a Swift array without repeating

6 Answers6

Linked

Related