У меня возникают проблемы с поиском достойного способа случайного перемешивания элементов в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<BigInteger> для этого алгоритма, но сейчас я просто не могу найти оптимальное решение. Честно говоря, я действительно не забочусь о данных в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;
}

EDIT: После замечания Стива об использовании «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;
}