How to randomize a sorted list?

Question

Here's a weird question for you guys

I have a sorted list that I want to randomize. How can i do this?

In my application, I have a function that returns a list of points that describe the outline of a sampled object. Due to how the problem is solved, the function returns a good ordered list. I have a second boundary, described in mathematics, and you want to determine if these two objects intersect with each other. I simply iterate over the points and determine if any one point is inside the mathematical boundary.

The method works well, but I want to increase speed by randomizing point data. Since it is likely that my mathematical boundary will overlap with a series of points that are next to each other, I think it would be advisable to check a randomized list rather than iterate over beautiful sorting (since only one click is needed to declare an intersection) .

So, any ideas on how I will do the randomization of an ordered list?

Answer 1

Use std::random_shuffle . If you want to implement the method yourself, you should look at the Fisher-Yates shuffle .

Answer 2

You can try the random_shuffle algorithm , but note that it will not work on list , since it requires random access iterators. You can use it on vector or deque , however.

Answer 3

Assuming your “list” does not mean a linked list, but means something that supports random access (such as an array, std :: vector or std :: deque), std :: random_shuffle may be useful.

Answer 4

But the key question is whether the lead time needed to randomize the list cannot be longer than the lead time to go through it sequentially.

Perhaps what you really need to do is not really randomizing it, but rather reading it in some order, except from front to back. For example, if there are n elements in the list, perhaps you should handle 1, n, 2, n-1, 3, n-2, etc. Or 1, n / 2, 2, n / 2 + 1, 3, n / 2 +2, etc.

If you always have the same number of points or the number of points falls into a small finite set, you can make a point estimation order for each possible number of points once in advance, either truly random, or perhaps carefully calculated in some way.

Answer 5

  int array [N];

 for (int i = N - 1; i> 0; i--) {
   int j = rand ()% i;
   int tmp = array [i];  array [i] = array [j];  array [j] = i;
 }

Answer 6

 std::random_shuffle(thelist.begin(), thelist.end());