Mam problem z ustaleniem przyzwoitego sposobu losowego tasowania elementów wstd::vector i po niektórych operacjach przywrócenie pierwotnej kolejności. Wiem, że powinien to być dość trywialny algorytm, ale myślę, że jestem zbyt zmęczony ...

Ponieważ jestem zmuszony używać niestandardowej klasy generatora liczb losowych, myślę, że nie mogę użyćstd::random_shuffle, co i tak nie pomaga, ponieważ muszę też zachować oryginalny porządek. Więc moim podejściem było stworzeniestd::map który służy jako odwzorowanie oryginalnych pozycji i losowych, takich jak:

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

Nie jestem pewien, czy powyższy algorytm jest właściwą implementacją losowej permutacji, więc wszelkie ulepszenia są mile widziane.

Oto jak udało mi się wykorzystać tę mapę permutacji:

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

Coś mi mówi, że powinienem móc używać tylko jednegostd::vector<BigInteger> dla tego algorytmu, ale właśnie teraz nie mogę znaleźć optymalnego rozwiązania. Szczerze mówiąc, nie dbam o daneinput, więc mógłbym nawet sprawić, by nie stał, nadpisać go i pominąć tworzenie jego kopii, ale pytanie brzmi, jak zaimplementować algorytm?

Jeśli coś takiego zrobię, skończę strzelać sobie w stopę, prawda? :)

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

EDYTOWAĆ: Idąc za uwagą Steve'a na temat korzystania z tasowania „Fisher-Yates”, zmieniłamgetRandomPermutation funkcja odpowiednio:

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