#include <algorithm>
#include <iostream>
#include <iterator>
#include <random>
#include <vector>
int main()
{
// seed the RNG
std::random_device rd;
std::mt19937 mt(rd());
std::vector<int> elements { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
std::cout << "Before: ";
std::copy(elements.cbegin(), elements.cend(),
std::ostream_iterator<int>(std::cout, " "));
auto currentIndexCounter = elements.size();
for (auto iter = elements.rbegin(); iter != elements.rend();
++iter, --currentIndexCounter)
{
// get int distribution with new range
std::uniform_int_distribution<> dis(0, currentIndexCounter);
const int randomIndex = dis(mt);
if (*iter != elements.at(randomIndex))
{
std::swap(elements.at(randomIndex), *iter);
}
}
std::cout << "\nAfter: ";
std::copy(elements.cbegin(), elements.cend(),
std::ostream_iterator<int>(std::cout, " "));
}
ICAgICNpbmNsdWRlIDxhbGdvcml0aG0+CiAgICAjaW5jbHVkZSA8aW9zdHJlYW0+CiAgICAjaW5jbHVkZSA8aXRlcmF0b3I+CiAgICAjaW5jbHVkZSA8cmFuZG9tPgogICAgI2luY2x1ZGUgPHZlY3Rvcj4KICAgIAogICAgaW50IG1haW4oKQogICAgewogICAgCS8vIHNlZWQgdGhlIFJORwogICAgICAgIHN0ZDo6cmFuZG9tX2RldmljZSByZDsKICAgICAgICBzdGQ6Om10MTk5MzcgbXQocmQoKSk7CiAgICAKICAgICAgICBzdGQ6OnZlY3RvcjxpbnQ+IGVsZW1lbnRzIHsgMSwgMiwgMywgNCwgNSwgNiwgNywgOCwgOSB9OwogICAgCiAgICAgICAgc3RkOjpjb3V0IDw8ICJCZWZvcmU6ICI7CiAgICAgICAgc3RkOjpjb3B5KGVsZW1lbnRzLmNiZWdpbigpLCBlbGVtZW50cy5jZW5kKCksCiAgICAgICAgICAgIHN0ZDo6b3N0cmVhbV9pdGVyYXRvcjxpbnQ+KHN0ZDo6Y291dCwgIiAiKSk7CiAgICAKICAgICAgICBhdXRvIGN1cnJlbnRJbmRleENvdW50ZXIgPSBlbGVtZW50cy5zaXplKCk7CiAgICAKICAgICAgICBmb3IgKGF1dG8gaXRlciA9IGVsZW1lbnRzLnJiZWdpbigpOyBpdGVyICE9IGVsZW1lbnRzLnJlbmQoKTsKICAgICAgICAgICAgKytpdGVyLCAtLWN1cnJlbnRJbmRleENvdW50ZXIpCiAgICAgICAgewogICAgICAgIAkvLyBnZXQgaW50IGRpc3RyaWJ1dGlvbiB3aXRoIG5ldyByYW5nZQogICAgICAgIAlzdGQ6OnVuaWZvcm1faW50X2Rpc3RyaWJ1dGlvbjw+IGRpcygwLCBjdXJyZW50SW5kZXhDb3VudGVyKTsKICAgICAgICAgICAgY29uc3QgaW50IHJhbmRvbUluZGV4ID0gZGlzKG10KTsKICAgIAogICAgICAgICAgICBpZiAoKml0ZXIgIT0gZWxlbWVudHMuYXQocmFuZG9tSW5kZXgpKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBzdGQ6OnN3YXAoZWxlbWVudHMuYXQocmFuZG9tSW5kZXgpLCAqaXRlcik7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAKICAgICAgICBzdGQ6OmNvdXQgPDwgIlxuQWZ0ZXI6ICI7CiAgICAgICAgc3RkOjpjb3B5KGVsZW1lbnRzLmNiZWdpbigpLCBlbGVtZW50cy5jZW5kKCksCiAgICAgICAgICAgIHN0ZDo6b3N0cmVhbV9pdGVyYXRvcjxpbnQ+KHN0ZDo6Y291dCwgIiAiKSk7CiAgICB9