Array iteration at random

Question

Given a sequence of N elements (say, std::vector or T* ), is there an efficient way to iterate over elements in random order by visiting each element exactly once. The solution should avoid creating an extra array with shuffled indices.

EDIT:

We also need to be able to track source indexes.

Answer 1

Use std::random_shuffle so you like the code:

 std::random_shuffle ( myvector.begin(), myvector.end() ); // in place no extra array for (std::vector<int>::iterator it=myvector.begin(); it!=myvector.end(); ++it) std::cout << ' ' << *it; 

Answer 2

Not particularly random, but given your limitations, you left a few options.

 A is the array S is the size of the array Generate a random prime number (P), such that P > S Q = P % S for i = 1 to S process A[Q] Q = (Q + P) % S 

Answer 3

Well, I don’t quite understand the limitations of creating additional arrays. But essentially, we randomly generate an index, and then repeat, regenerating, if we get into the index that we have already reached. It is not necessarily effective. But I would venture to suggest that the border is, of course, between O (n ^ 2) and O (n!) (Possibly (O (n ^ n)). With a little work, we could clear this and get almost always fall on n ^ 2.