Случайные перестановки

У меня возникли проблемы с определением достойного способа случайного перетасовки элементов в std::vectorи, после некоторых операций, восстановления исходного заказ. Я знаю, что это должен быть довольно тривиальный алгоритм, но, видимо, я слишком устал...

Поскольку я вынужден использовать собственный класс генератора случайных чисел, я не могу использовать std: :random_shuffle, что в любом случае не помогает, потому что мне также нужно сохранить первоначальный порядок. Итак, мой подход состоял в том, чтобы создать std::map, который служит отображением между исходными позициями и случайными, например:

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

Я не уверен, что приведенный выше алгоритм является правильной реализацией. для случайной перестановки, поэтому любые улучшения приветствуются.

Вот как мне удалось использовать эту карту перестановок:

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

Что-то мне подсказывает, что я должен иметь возможность использовать только один std::vectorдля этого алгоритм, но сейчас я просто не могу найти оптимальное решение.Честно говоря, меня не особо волнуют данные в input, поэтому я мог бы даже сделать их неконстантными, перезаписать их и пропустить создание копии, но вопрос в том, как реализовать алгоритм ?

Если я сделаю что-то подобное, я в конечном итоге выстрелю себе в ногу, верно? :)

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

РЕДАКТИРОВАТЬ:Следуя замечанию Стива об использовании перетасовки "Fisher-Yates", я соответственно изменил свою функцию getRandomPermutation:

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