Random Number Generation

How can one write a random number generator that takes a number and generates a random number within the range of 0 through the given number and when called the given number of time doesn't repeat a single number more than once.
Example given the number 8, the generator generates [1,3,6,8,2,5,4,7,0] when the next() method is called 8 times

You could make an object that takes the upper bound, generate a randomized list of numbers, then have next() just remove the last one:

// Conforming to Sequence/IteratorProtocol so we can use a for loop
struct RandomGenerator: Sequence, IteratorProtocol {
	// Holds the randomized list
	var items: [Int]

	// Generates the randomized list
	init(upperBound: Int) {
		items = Array(0...upperBound).shuffled()
	}

	// Conformance to IteratorProtocol
	mutating func next() -> Int? {
		items.popLast()
	}
}

for i in RandomGenerator(upperBound: 8) {
	print(i)
}
3 Likes

Thanks @nakajima but this isn't what I hope to achieve. I want one that is thread-safe and infinitely generate numbers without repetition

I want one that is thread-safe

You would put @nakajima's behind the synchronization mechanism of your choice to achieve this.

and infinitely generate numbers without repetition

This is impossible given that the output is supposed to be bounded to a given range. Assuming you want it to exhaust all the numbers in the range, and then start over, do you need it to generate the same sequence the second time through, or a new sequence? (I.e. if the upper bound is 2, do you want to get 0, 2, 1, 0, 2, 1, 0, 2, 1, ... or 0, 2, 1, 1, 0, 2, 0, 1, 2, ...?)

If the former, rather than popping from the array, increment an index, and when it reaches the end start over at the beginning. If the latter, do the same, but reshuffle the array.

If you don't actually want randomness and just want the simplest way to skip around in the range sampling every point once per orbit, pick any integer k coprime to (bound+1) and iterate n*k % (bound+1).

5 Likes

Can you provide the code for this one please?

You could probably pick a large prime number (which is automatically co-prime to other smaller numbers by virtue of being prime), e.g. this:

    var n = 0
    let k = 10000019
    mutating func next() -> Int? {
        n += 1
        return (n * k) % (bound + 1)
    }

Watch out for:

  • "not so randomly looking" sequences. E.g. if you plot your numbers on the XY graph you might see some unwanted patterns like lines. You may want to pick another number for k in that case.
  • multiplication overflow. You can't go away with &* as it would ruin the algorithm, you'd need to choose a smaller number for k to avoid overflow.
1 Like

You avoid multiplication overflow by adding k to the last value and subtracting (bound+1) if the result is larger than (bound+1), instead of multiplying and taking the remainder.

(You have to defend against addition overflow, too, but that’s easier).

2 Likes

Nice! But could you do it without a remainder? For example k=10000019, bound=100, n=1

1 Like

You reduce k to k % (bound+1) (this does not change the generated sequence, because (ab%n) == (a%n)(b%n)%n, up to sign, and all the numbers here are positive). So for your example, it would be something like:

let b = 101
let k = 10000019 % b // 9
var last = 0

mutating func next() -> Int? {
  defer { return last }
  // note that in your example, overflow can never happen,
  // so we could just use `+`. More generally, you need to
  // do this check.
  var (next, overflow) = last.addingReportingOverflow(k)
  if overflow || next >= b { next &-= b }
  last = next
}

(n.b. these are not even remotely "random" numbers; this is just a linear sequence that iterates through all possible values in 0 ... b over and over again, which is about as not-random as its possible to be.)

2 Likes