Es fällt mir schwer, eine anständige Methode zu finden, um die Elemente in einer zufälligen Reihenfolge zu mischenstd::vector und nach einigen Operationen die ursprüngliche Reihenfolge wiederherstellen. Ich weiß, dass dies ein eher trivialer Algorithmus sein sollte, aber ich denke, ich bin zu müde ...

Da ich gezwungen bin, eine benutzerdefinierte Zufallszahlengeneratorklasse zu verwenden, kann ich sie wohl nicht verwendenstd::random_shuffle, was sowieso nicht hilft, da ich auch die ursprüngliche Reihenfolge beibehalten muss. Mein Ansatz war es also, einestd::map Das dient als Zuordnung zwischen den ursprünglichen Positionen und den zufälligen, wie folgt:

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

Ich bin nicht sicher, ob der obige Algorithmus eine ordnungsgemäße Implementierung für eine zufällige Permutation ist, daher sind Verbesserungen willkommen.

Nun, hier ist, wie ich es geschafft habe, diese Permutationskarte zu nutzen:

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

Irgendwas sagt mir, dass ich nur einen verwenden darfstd::vector<BigInteger> Für diesen Algorithmus kann ich derzeit jedoch nicht die optimale Lösung finden. Ehrlich gesagt, interessieren mich die Daten in nicht wirklichinput, also könnte ich es sogar als Nicht-Konstante definieren, überschreiben und das Erstellen einer Kopie davon überspringen, aber die Frage ist, wie der Algorithmus implementiert werden soll.

Wenn ich so etwas mache, schieße ich mir am Ende in den Fuß, oder? :)

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

BEARBEITEN: Nach Steves Bemerkung über die Verwendung von "Fisher-Yates" Shuffle habe ich meine geändertgetRandomPermutation entsprechend funktionieren:

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