Estou tendo dificuldade em descobrir uma maneira decente de embaralhar aleatoriamente os elementos em umstd::vector e, após algumas operações, restaurar o pedido original. Eu sei que isso deve ser um algoritmo bastante trivial, mas acho que estou muito cansado ...

Como estou restrito a usar uma classe de gerador de números aleatórios, acho que não posso usarstd::random_shuffle, o que não ajuda de qualquer maneira, porque eu também preciso preservar a ordem original. Então, minha abordagem foi criar umstd::map que serve como um mapeamento entre as posições originais e as aleatórias, assim:

std::map<unsigned int, unsigned int> getRandomPermutation (const unsigned int &numberOfElements)
{
    std::map<unsigned int, unsigned int> permutation;

    //populate the map
    for (unsigned int i = 0; i < numberOfElements; i++)
    {
        permutation[i] = i;
    }

    //randomize it
    for (unsigned int i = 0; i < numberOfElements; i++)
    {
        //generate a random number in the interval [0, numberOfElements)
        unsigned long randomValue = GetRandomInteger(numberOfElements - 1U);

        //broken swap implementation
        //permutation[i] = randomValue;
        //permutation[randomValue] = i;

        //use this instead:
        std::swap(permutation[i], permutation[randomValue]);
    }

    return permutation;
}

Não tenho certeza se o algoritmo acima é uma implementação adequada para uma permutação aleatória, portanto, quaisquer melhorias são bem-vindas.

Agora, aqui está como eu consegui usar este mapa de permutação:

std::vector<BigInteger> doStuff (const std::vector<BigInteger> &input)
{
    /// Permute the values in a random order
    std::map<unsigned int, unsigned int> permutation = getRandomPermutation(static_cast<unsigned int>(input.size()));

    std::vector<BigInteger> temp;

    //permute values
    for (unsigned int i = 0; i < static_cast<unsigned int>(input.size()); ++i)
    {
        temp.push_back(input[permutation[i]]);
    }

    //do all sorts of stuff with temp

    /// Reverse the permutation
    std::vector<BigInteger> output;
    for (unsigned int i = 0; i < static_cast<unsigned int>(input.size()); ++i)
    {
        output.push_back(temp[permutation[i]]);
    }

    return output;
}

Algo me diz que eu deveria ser capaz de usar apenas umstd::vector<BigInteger> para este algoritmo, mas, no momento, simplesmente não consigo descobrir a solução ideal. Honestamente, eu realmente não me importo com os dados eminput, então eu poderia até torná-lo não-const, sobrescrevê-lo e pular a criação de uma cópia dele, mas a questão é como implementar o algoritmo?

Se eu fizer algo assim, acabo me atirando no pé, certo? :)

for (unsigned int i = 0; i < static_cast<unsigned int>(input.size()); ++i)
{
    BigInteger aux = input[i];
    input[i] = input[permutation[i]];
    input[permutation[i]] = aux;
}

EDITAR: Após a observação de Steve sobre o uso do shuffle "Fisher-Yates", eu mudei meugetRandomPermutation função em conformidade:

std::map<unsigned int, unsigned int> getRandomPermutation (const unsigned int &numberOfElements)
{
    std::map<unsigned int, unsigned int> permutation;

    //populate the map
    for (unsigned int i = 0; i < numberOfElements; i++)
    {
        permutation[i] = i;
    }

    //randomize it
    for (unsigned int i = numberOfElements - 1; i > 0; --i)
    {
        //generate a random number in the interval [0, numberOfElements)
        unsigned long randomValue = GetRandomInteger(i);

        std::swap(permutation[i], permutation[randomValue]);
    }

    return permutation;
}