Estoy teniendo problemas para encontrar una manera decente de mezclar aleatoriamente los elementos en unastd::vector y, después de algunas operaciones, restablecer el pedido original. Sé que esto debería ser un algoritmo bastante trivial, pero supongo que estoy demasiado cansado ...

Dado que estoy limitado a usar una clase de generador de números aleatorios personalizada, supongo que no puedo usarstd::random_shuffle, que no ayuda de todos modos, porque también necesito preservar el orden original. Por lo tanto, mi enfoque fue crear unastd::map que sirve como un mapeo entre las posiciones originales y las aleatorias, como esta:

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;
}

No estoy seguro de que el algoritmo anterior sea una implementación adecuada para una permutación aleatoria, por lo que cualquier mejora es bienvenida.

Ahora, aquí es cómo he logrado hacer uso de este mapa de permutación:

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 dice que debería poder usar solo unostd::vector<BigInteger> para este algoritmo, pero, ahora mismo, simplemente no puedo encontrar la solución óptima. Honestamente, no me importan los datos eninput, así que incluso podría hacer que no sea constante, sobrescribirlo y omitir la creación de una copia, pero la pregunta es ¿cómo implementar el algoritmo?

Si hago algo como esto, termino disparándome en el pie, ¿verdad? :)

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: Siguiendo la observación de Steve sobre el uso de la mezcla de "Fisher-Yates", cambié migetRandomPermutation funciona en consecuencia:

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;
}