5 ms·

Could you please expand on your linked code, not really a C++ programmer and line 22/25 confuse me a bit? Unfortunately I don't understand how each element has

• sebleblanc 12y ago
  Regarding the C++ code: /* This is standard modern C++ random number generation. It means, using the random generator "engine", return a number according to distribution "dist". In this "dist" is a uniform distribution from "i" to "max-min". "auto" is the new way to type variables in C++: it infers the type of the variable from the type of the expression */ 22: auto index = dist(engine); /* The following lines are a bit more complex, as they contain a nested expression. Let us focus on the inner expression: (index < size ) ? array[index] : map.insert({index, min + index}).first->second This is in the form: test-expr ? when-true-expr : when-false-expr This expression is a ternary condition. What it means is that the expression before the question mark is computed (index < size), and if it evaluates to true, the overall expression will resolve to the result of the expression between the question mark and the colon, otherwise it resolves to what is after the colon. Here, it means that if "index" is smaller than "size", use "array[index]", otherwise insert a new entry in the map, with key "index" and value "min+index", then reuse the result of the operation by accessing member "second" of the member "first". I am not familiar with STL maps; here is an explanation of the map::insert method from cplusplus.com: The single element versions (1) return a pair, with its member pair::first set to an iterator pointing to either the newly inserted element or to the element with an equivalent key in the map. The pair::second element in the pair is set to true if a new element was inserted or false if an equivalent key already existed. */ 23: std::swap(array[i], index < size 24: ? array[index] 25: : map.insert({index, min + index}).first->second); /* Then, the std::swap operation simply swaps the two indicated values in the array. */
• detrino 12y ago
  > Could you please expand on your linked code, not really a C++ programmer and line 22/25 confuse me a bit? I've annotated the program here: http://ideone.com/gmaBri http://ideone.com/gmaBri > Unfortunately I don't understand how each element has the same probability of being chosen. I.e. the first element seems to have a probability of 1/n, while the second has 1/n + 1/(n-1) etc. Am i wrong about this? This is just a partial Fisher-Yates shuffle[1] using a sparse sequence instead of an array. Keep in mind that if an element is not chosen it is swapped with the chosen element and will be considered again. I think the best way to think about it is that you are choosing a random element from the set and then "removing" it from the set with the swap and then repeating. [1] http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#Th...