C++ iterate vector randomly

You can use the algebraic notion of primitive root modulo n.Basically

If n is a positive integer, the integers between 1 and n − 1 that are coprime to n form the group of primitive classes modulo n. This group is cyclic if and only if n is equal to 2, 4, p^k, or 2p^k where p^k is a power of an odd prime number

Wikipedia displays how you can generate numbers below 7 using 3 as generator.

From this statement you derive an algorithm.

1. Take your number n
2. Find the next prime number m which is bigger than n
3. For each of your thread pick a unique random number F(0) between 2 and m
4. Compute the next index using F(i+1) = (F(i) * F(0)) mod m. If that index is within [0, n] range, access the element. If not go towards the next index.
5. Stop after m - 1 iterations (or when you obtain 1, it is the same thing).

Because m is prime, every number between 2 and m-1 is coprime to m so is a generator of the sequence {1 ... m}. You are guaranteed that no number will repeat in the first m - 1 steps, and that all m - 1 numbers will appear.

Complexity :

• Step 2 : Done once, complexity equivalent to finding primes up to n, ie sieve of Eratosthenes
• Step 3 : Done once, you can choose 2, 3 ,4, 5, etc... Which is as low as O(thread count)
• Step 4 : O(m) time, O(1) in space per thread. You dont need to store the F(i). You only need to know first value and last value. This is the same properties as incrementation

If I understand well you want to generate a random permutation in a incremental way, i.e. you want to call n times a function f so that it generates all permuted numbers from 1 to n, so that function has constant memory.

I doubt it exists if you want to obtain an uniform distribution among the permutations, but you may be satisfied with a subset of the set of permutations.

If this is the case you can generate a permutation by taking a number p prime with n and calculate for each i in [1,n] : i.p (mod n).For example, if you have n=5 and p=7, then 7%5=2, 14%5=4, 21%5=1, 28%5=3, 35%5=0. You may combine several such functions to obtain something satisfying for you...

If memory is your biggest problem then you'll have to swap CPU cycles for memory space.

E.g. c++'s std::vector<bool> (http://en.cppreference.com/w/cpp/container/vector_bool) is a bit-array so quite memory efficient.

Each thread could have its own vector<bool> indicating wether or not it has visited a particular index. Then you'd have to use CPU cycles to randomly choose an index that it hasn't visited yet and terminate when all bools are true.