2

I have a vector in C++ that has sorted data, I want to access the data in random order for shuffling the data. The problem with rand is that two indexes can be accessed at the same time and also when the last item remains there will be a lot of un-needed lookups. Any suggestions.

coder
  • 119
  • 1
  • 2
  • 10
  • 5
    This is a classic XY problem. – erip Jan 19 '16 at 15:46
  • 1
    Please clarify "two indexes can be accessed at the same time". My understanding is that only one element can be accessed in a vector at a time (unless you are performing parallel computing or the hardware is accessing the location *at the same time*). Are you talking about re-entrancy? – Thomas Matthews Jan 19 '16 at 15:48
  • Possible duplicate: [How to shuffle a std::vector?](http://stackoverflow.com/questions/6926433/how-to-shuffle-a-stdvector). Although the OP hasn't shown whether the sorted array can be modified. – Thomas Matthews Jan 19 '16 at 15:51
  • Is the sorted array allowed to be modified? The answer determines whether one has to use sorted indices or whether the contents of the array can be *shuffled*. – Thomas Matthews Jan 19 '16 at 15:52

3 Answers3

5

If you don't want to modify the original and only access each element once, you can shuffle a vector of indices:

#include <algorithm>
#include <random>


auto engine = std::default_random_engine{};
const std::vector<int> numbers = {4, 5, 7, 12};
std::vector<int> indices(numbers.size());
std::iota(indices.begin(), indices.end(), 0);
std::shuffle(indices.begin(), indices.end(), engine);
for (auto i : indices)
{
    std::cout << numbers[i] << std::endl;
}
molbdnilo
  • 64,751
  • 3
  • 43
  • 82
4

You can simply shuffle the array with std::shuffle, which exists in <algorithm>. It takes the an iterator pointing to the first position to be considered for shuffling, an iterator pointing to the last position to be considered for shuffling, and a RNG engine. In the following example, I'll use std::default_random_engine found in <random>.

#include <iostream>
#include <algorithm>
#include <random>
#include <vector>

int main() {

  std::vector<int> v{1, 2, 3, 4, 5, 6};

  auto rng = std::default_random_engine{};
  std::shuffle(std::begin(v), std::end(v), rng);

  for(auto&& e: v) {
    std::cout << e << " ";
  }

  std::cout << '\n';
}

When I run this, I got:

3 1 5 6 2 4

There are no details on how std::shuffle is implemented, but it's very likely an O(n) shuffle algorithm like the Fisher-Yates (Knuth) Shuffle, so there won't be many "unneeded" lookups.

erip
  • 16,374
  • 11
  • 66
  • 121
  • 1
    This won't work if the array is not allowed to be modified, an array of constant values. A sorted array may not want to be modified (because it will have to be resorted). – Thomas Matthews Jan 19 '16 at 15:54
  • @ThomasMatthews Fair point. If OP confirms array is immutable, I'll edit. – erip Jan 19 '16 at 15:56
1

You can create a shuffled vector. See random_shuffle. In the link there is a complete example, I will not post one for sake of brevity.

MagoNick
  • 331
  • 1
  • 4
  • 17
  • But the question is whether or not the array is allowed to be modified. The OP hasn't indicated either way on that topic. – Thomas Matthews Jan 19 '16 at 15:52
  • 1
    `std::random_shuffle` is deprecated in C++14. – erip Jan 19 '16 at 15:54
  • Actually you are right. The thing is that it is not clear what the OP would like to know. I assumed that the array was allowed to be modified since not specified otherwise – MagoNick Jan 19 '16 at 15:55
  • So basically I have to shuffle a list of files, so the objects( which are file names can not be changed) any thing else can be changed. – coder Jan 25 '16 at 09:38