How to Randomly Iterate Through a Large Range

How can I randomly iterate through a large Range?

I just remembered a similar problem from a class I took years ago; that is, iterating (relatively) randomly through a set (completely exhausting it) given extremely tight memory constraints. If I'm remembering this correctly, our solution algorithm was something like this:

1. Define the range to be from 0 to
   some number N
2. Generate a random starting point x[0] inside N
3. Generate an iterator Q less than N
4. Generate successive points x[n] by adding Q to
   the previous point and wrapping around if needed. That
   is, x[n+1] = (x[n] + Q) % N
5. Repeat until you generate a new point equal to the starting point.

The trick is to find an iterator that will let you traverse the entire range without generating the same value twice. If I'm remembering correctly, any relatively prime N and Q will work (the closer the number to the bounds of the range the less 'random' the input). In that case, a prime number that is not a factor of N should work. You can also swap bytes/nibbles in the resulting number to change the pattern with which the generated points "jump around" in N.

This algorithm only requires the starting point (x[0]), the current point (x[n]), the iterator value (Q), and the range limit (N) to be stored.

Perhaps someone else remembers this algorithm and can verify if I'm remembering it correctly?

random iteration in Python

You can use random.shuffle() to, well, shuffle a list:

import random

r = list(range(1000))
random.shuffle(r)
for i in r:
  # do something with i

By the way, in many cases where you'd use a for loop over a range of integers in other programming languages, you can directly describe the "thing" you want to iterate in Python.

For example, if you want to use the values of i to access elements of a list, you should better shuffle the list directly:

lst = [1970, 1991, 2012]
random.shuffle(lst)
for x in lst:
  print x

NOTE: You should bear the following warning in mind when using random.shuffle() (taken from the docs:

Note that for even rather small len(x), the total number of
permutations of x is larger than the period of most random number
generators; this implies that most permutations of a long sequence can
never be generated.

Randomly iterate through sequence of integers, 1 to n

You can use Format-Preserving Encryption to encrypt a counter.

Pick a symmetric cipher that is crafted to encrypt the numbers up to N. (You can use the proposed scheme of AES-FFX) Then generate a random key with high entropy and start to encrypt the numbers 0, 1, 2, ... upwards. Since the encryption ensures a 1:1 mapping and a good encryption looks random, you'll end up with a sequence of non-repeating random numbers using only O(1) storage.

The usage of a block cipher in counter mode (CTR) is a well known technique to create a cryptographically secure pseudo-random number generator (CSPRNG). Section 10.2.1. of NIST SP 800-90A gives additional tips.
The usage of AES as the underlying block cipher is recommended for stochastic simulation since the quality of the randomness does not show any statistical weaknesses.

The idea is anything but new and was already proposed on stackoverflow multiple times by Craig McQueen:

• Generating non-repeating random numbers in Python
• Unique (non-repeating) random numbers in O(1)?
• Generating millions of non-repeating random numbers in Java

Also crypto.stackexchange has several threads about this:

• Random Number Generator based on AES CTR
• How do I produce a
  stream of secure random numbers from AES-Counter mode?

Randomly iterating through a 2D list in Python

Create an array with all possible pairs of coordinates, shuffle this and iterate through as normal.

import random
coords = [(x,y) for x in range(self.gridWidth) for y in range(self.gridHeight)
random.shuffle(coords)
for i,j in coords:
    if self.grid[i][j] != 'b':
        print i, j
        self.grid[i][j].colour = self.rand_Land_Picker()

How to randomly iterate through an array once, and then repeatedly iterate in that order

Create a second array. Next, populate the array with random numbers (ranging from 0 to array.length). Now create a for loop iterating through the secondary array. Each number in the array corresponds to an index in array.

Result: you can now iterate randomly through array without modifying the order of array.

Later on you can use the splice() function to add to the second array at random points (and push() to add to the main array).

Randomly iterate over ArrayList Integer in Java

You can use Collections.shuffle() on the list.

Note that this will shuffle the list itself, so if order is important you should make a copy of it (and shuffle the copy).

List<Customer> newList = new ArrayList<>( oldList ) ;
Collections.shuffle( newList ) ;

Alternatively you could create a random array which has elements 0 - List.size()-1 and using those as indices to access "random" elements in the List.

Iterate through an array randomly but fast

You should shuffle the entire matrix rather than going through one row/column at a time. This should work pretty fast. It's 125k and should be reasonably cache friendly.

constexpr int N = 250;
std::array<uint16_t, N* N> nums;
std::iota(nums.begin(), nums.end(), 0);
std::shuffle(nums.begin(), nums.end(), engine);

for (auto x : nums)
{
    auto xi = x / N;
    auto yi = x % N;
    // Do Stuff indexed on x and y
}

---

Related Topics