Simulate random array iteration

Question

I have an array of a given size. I want it to go through, this is a pseudo-random order, keeping the array intact and visiting each element once. It is best if the current state can be stored in several integers.

I know you cannot have complete randomness without preserving the full array , but I don't need an order to be truly random. I need this to be perceived by the user as random. The solution is to use sublinear space.

One possible suggestion — using a large prime — is given here . The problem with this solution is that there is an obvious fixed step (block size of the received module). I would prefer a solution that is not so obviously not accidental. Is there a better solution?

Answer 1

How about this algorithm?

To pseudo-pseudo-random movement of an array of size n.

• Create a small array of size k
• Use the large prime method to populate a small array, i = 0
• Accidentally delete a position using RNG from a small array, I + = 1
• if i <n - k then add a new position using the large prime method
• if i <n goto 3.

the higher k, the more likely you get. This approach allows you to delay the generation of numbers from the prime method.

A similar approach can be taken to generate a number earlier than expected in the sequence, creating another array of "skip-list". Randomly select items later in the sequence, use them to cross the next position, and then add them to the skip list. When they naturally come, they are searched in the skip list and suppressed, and then removed from the skip list, after which you may accidentally add another item to the skip list.

Answer 2

The idea of ​​a random generator that simulates shuffling is good if you can get one whose maximum period you can control.

A Linear congruent generator calculates a random number by the formula:

x[i + 1] = (a * x[i] + c) % m; 

The maximum period is m, and this is achieved by observing the following properties:

• Parameters c and m are coprime.
• For each prime r dividing m, a - 1 is a multiple of r.
• If m is a multiple of 4, then also a-1 is a multiple of 4.

My first darft involved creating the next multiple of 4 after the length of the array, and then finding the appropriate values ​​of a and c. It was (a) a lot of work and (b) sometimes yielded very obvious results.

I rethought this approach. We can make m the smallest power of two so that the length of the array is included. The only prime coefficient m is 2, which will make every odd number relatively simple with it. With the exception of 1 and 2, m will be divided by 4, which means that we must make a - 1 a a multiple of 4.

Having more than m than the length of the array, we must discard all values ​​that are illegal array indices. This will happen in almost every other corner and should be negligible.

The following code lists pseudo-random numbers with a period of exceeding m. I avoided the trivial values ​​for a and c and my (not too numerous) spotted checks, the results looked good. At least there was no obvious cycling scheme.

So:

 class RandomIndexer { public: RandomIndexer(size_t length) : len(length) { m = 8; while (m < length) m <<= 1; c = m / 6 + uniform(5 * m / 6); c |= 1; a = m / 12 * uniform(m / 6); a = 4*a + 1; x = uniform(m); } size_t next() { do { x = (a*x + c) % m; } while (x >= len); return x; } private: static size_t uniform(size_t m) { double p = std::rand() / (1.0 + RAND_MAX); return static_cast<int>(m * p); } size_t len; size_t x; size_t a; size_t c; size_t m; }; 

Then you can use the generator as follows:

 std::vector<int> list; for (size_t i = 0; i < 3; i++) list.push_back(i); RandomIndexer ix(list.size()); for (size_t i = 0; i < list.size(); i++) { std::cout << list[ix.next()]<< std::endl; } 

I know this is still not a great random number generator, but it is fast enough, does not require a copy of the array, and seems to work fine.

If the approach of choosing a and c randomly yields bad results, it might be a good idea to limit the generator to some powers of two and hard-coded literary values ​​that turn out to be good.

Answer 3

As others have pointed out, you can create a sort of “flight plan” in advance by shuffling the array of array indices, and then follow it. This violates "it would be better if the current state can be stored in several integers," but does it really matter? Are there limited performance limitations? In the end, I believe that if you do not accept repetitions, you need to store items that you have already visited somewhere or somehow.

Alternatively, you can choose an intrusive solution and save the bool inside each element of the array, indicating whether this element has already been selected or not. This can be done in an almost pure way, using inheritance (some if necessary).
Many problems come with this solution, for example. and, of course, it violates the "keep array unchanged" restriction.

Answer 4

The quadratic deductions you mentioned (“using big simple”) are well known, will work and guarantee that each element will repeat exactly once (if it is required, but it seems that this is not strictly so?), Unfortunately they are not " very random, "and there are a few more requirements for the module in addition to being simple for its operation.
There is a page on the Jeff Preshing website that describes the technique in detail and suggests again submitting the output of the residual generator to the fixed-offset generator .

However, since you said that you just need to "perceive it as random for the user", it seems that you can do it by supplying a hash function (for example, cityhash or siphash) with integer integers. The output will be a "random" integer, and at least there will still be a strict 1: 1 mapping (since there are much more possible hash values ​​than there are inputs).

Now the problem is that your array is most likely not so large, so you need to somehow reduce the range of these generated indexes without creating duplicates (which is difficult).

The obvious solution (taking modulo) will not work, as it pretty much ensures that you get a lot of duplicates.

Using a bitmask to limit the range to the next greater power of the two should work without introducing an offset, and discarding indices that go beyond (generating a new index) should also work. Please note that this requires a non-deterministic time, but the combination of these two should work quite well (no more than a few attempts) on average.

Otherwise, the only solution that "really works" is to shuffle the index array, as Camil Kilolajczyk pointed out (although you don't want to).

Answer 5

Here is a java solution that can be easily converted to C ++ and is similar to the M Oehm solution above, although with a different way to select LCG parameters.

 import java.util.Enumeration; import java.util.Random; public class RandomPermuteIterator implements Enumeration<Long> { int c = 1013904223, a = 1664525; long seed, N, m, next; boolean hasNext = true; public RandomPermuteIterator(long N) throws Exception { if (N <= 0 || N > Math.pow(2, 62)) throw new Exception("Unsupported size: " + N); this.N = N; m = (long) Math.pow(2, Math.ceil(Math.log(N) / Math.log(2))); next = seed = new Random().nextInt((int) Math.min(N, Integer.MAX_VALUE)); } public static void main(String[] args) throws Exception { RandomPermuteIterator r = new RandomPermuteIterator(100); while (r.hasMoreElements()) System.out.print(r.nextElement() + " "); //output:50 52 3 6 45 40 26 49 92 11 80 2 4 19 86 61 65 44 27 62 5 32 82 9 84 35 38 77 72 7 ... } @Override public boolean hasMoreElements() { return hasNext; } @Override public Long nextElement() { next = (a * next + c) % m; while (next >= N) next = (a * next + c) % m; if (next == seed) hasNext = false; return next; } } 

Answer 6

maybe you could use this: http://www.cplusplus.com/reference/algorithm/random_shuffle/ ?