Вопрос по permutation, random, algorithm, c++, mapping – Случайные перестановки

5

У меня возникают проблемы с поиском достойного способа случайного перемешивания элементов в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;
}
@ Брендан Мне нужно сохранить только порядок, а не содержимое списка. Это часть защищенного интерактивного протокола, который требует, чтобы элементы в списке случайным образом перемешивались перед выполнением взаимодействий, и после завершения протокола мне нужно восстановить первоначальный порядок. Mihai Todor
Почему бы не сохранить состояние исходного списка; а когда закончите перемешивание, просто переназначьте свой сохраненный список на перемешанный? Brendan
Могу я порекомендовать bogosort, он решит обе ваши проблемы.en.wikipedia.org/wiki/Bogosort Skyler Saleh
@ RTS Не могли бы вы разработать свою идею? Mihai Todor

Ваш Ответ

4   ответа
1

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

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

Увидетьhttp://en.wikipedia.org/wiki/Linear_congruential_generator

В качестве альтернативы вы можете просто сгенерировать одно случайное число в диапазоне 0 .. (n! -1) и передать его функции unrank для перестановок. При достаточно малом n вы можете сохранить их и получить алгоритм с постоянным временем, но если n слишком велико для этого, лучшей функцией unrank будет O (n). Применение результирующей перестановки в любом случае будет O (n).

Я использую библиотеку GMP для генерации случайных чисел, которая реализует алгоритм Мерсенна Твистера. Несмотря на то, что это медленно, я все равно должен предварительно генерировать кэш случайных чисел, поэтому я думаю, что этого будет достаточно на данный момент. Код в любом случае не предназначен для производства. Это просто для того, чтобы делать некоторые симуляции криптографического протокола. Mihai Todor
4

Если вы «рандомизируете» вектор из n элементов, вы можете создать другойstd::vector<size_t> index(n), задаватьindex[x] = x за0 <= x < nзатем перемешатьindex, Тогда ваши поиски примут форму:original_vector[index[i]], Порядок исходного вектора никогда не менялся, поэтому нет необходимости восстанавливать порядок.

...constrained to use a custom random number generator class, I guess I can't use std::random_shuffle...

Вы заметили эту перегрузку?

template <class RandomAccessIterator, class RandomNumberGenerator>
void random_shuffle ( RandomAccessIterator first, RandomAccessIterator last,
                    RandomNumberGenerator& rand );

Подробнее о том, как обернуть ваш генератор случайных чисел совместимым объектом, смотритеhttp://www.sgi.com/tech/stl/RandomNumberGenerator.html

@SteveJessop Да, но у него есть эта подпись:Pointer to unary function taking one argument and returning a value, both of the appropriate difference type (generally ptrdiff_t). The function shall return a value between zero and its argument (lower than this). это подразумевает, что мне нужно обернуть свой собственный генератор в какую-то функцию, и, честно говоря, я не думаю, что это стоит усилий. Я только что преобразовал свой код, чтобы использовать & quot; Fisher-Yates & quot; shuffle, и я в порядке с этим. Осталось только посмотреть, смогу ли я улучшить способ использования своей карты перестановок. Mihai Todor
@Mihai:random_shuffle имеет необязательный третий аргумент для указания источника случайных чисел.
Да, и даже если вам по какой-то причине нужно изменить исходный вектор, вы можете использовать индексный вектор, чтобы сделать это, и использовать его снова, чтобы полностью изменить процесс. Это делается путем следования циклам в перестановке, определяемой индексным вектором.
К сожалению, поскольку это будет интерактивный протокол, я не могу отправить индексный вектор вместе сoriginal_vector, Если бы я должен был использоватьstd::random_shuffleМне нужно было бы обернуть его в некоторый пользовательский класс (шаблон), потому что я не могу подключить генератор случайных чисел из коробки. Mihai Todor
& quot; установить индекс [x] = x для 0 & lt; = x & lt; N & Quot; используя, наконец, существует в конце концовstd::iota, где доступно :-)
2

Если вы ищете конкретные ошибки в своем коде:

permutation[i] = randomValue;
permutation[randomValue] = i;

неправильно. Обратите внимание, что после того, как вы закончите, каждое значение не обязательно будет отображаться ровно один раз среди значений карты. Так что это не перестановка, не говоря уже о равномерно распределенной случайной.

Тони говорит, что правильное средство для генерации случайной перестановки - использоватьstd::random_shuffle на векторе, который изначально представляет тождественную перестановку. Или, если вы хотите узнать, как правильно выполняется перемешивание, найдите «Fisher-Yates». В общем, любой подход, который делаетN случайные выборы равномерно из0 .. N-1 обречен на неудачу, потому что это означает, что он имеетN^N возможные пути это может работать. Но естьN! возможные перестановкиN предметы иN^N как правило, не делится наN!, Следовательно, невозможно, чтобы каждая перестановка была результатом равного числа случайных выборок, то есть распределение не является равномерным.

the question is how to implement the algorithm?

Итак, у вас есть перестановка, и вы хотите изменить порядок элементовinput на месте, в соответствии с этой перестановкой.

Главное, что нужно знать, это то, что каждая перестановка представляет собой композицию «циклов». То есть, если вы неоднократно следите за перестановкой из заданной начальной точки, вы возвращаетесь туда, откуда вы начали (и этот путь является циклом, которому принадлежит эта начальная точка). В данной перестановке может быть более одного такого цикла, и еслиpermutation[i] == i для некоторыхiзатем циклi имеет длину 1.

Все циклы не пересекаются, то есть каждый элемент появляется ровно в одном цикле. Поскольку циклы не "мешают" друг с другом мы можем применить перестановку, применяя каждый цикл, и мы можем делать циклы в любом порядке. Итак, для каждого индексаi мы должны:

  • check whether we've already done i. If so, move on to the next index.
  • set current = i
  • swap index[current] with index[permutation[current]]. So index[current] is set to its correct value (the next element in the cycle), and its old value is "pushed" forward along the cycle.
  • mark current as "done"
  • if permutuation[current] is i, we've finished the cycle. So the first value of the cycle ends up in the spot formerly occupied by the last element of the cycle, which is right. Move on to the next index.
  • set current = permutation[current] and go back to the swap step.

В зависимости от задействованных типов, вы можете оптимизировать работу со свопами - может быть лучше скопировать / переместить временную переменную и начало каждого цикла, затем выполнить копирование / перемещение вместо свопа на каждом шаге цикла и наконец, скопируйте / переместите временное в конец цикла.

Обратный процесс является тем же самым, но с использованием «обратного» перестановки. Обратноеinv перестановкиpermэто перестановка такая, чтоinv[perm[i]] == i для каждогоi, Вы можете либо вычислить обратное значение и использовать точный код, приведенный выше, либо код, аналогичный приведенному выше, за исключением перемещения элементов в противоположном направлении вдоль каждого цикла.

Альтернатива всему этому, поскольку вы сами внедрили Fisher-Yates - когда вы запускаете Fisher-Yates, для каждого выполненного свопа записывайте два индекса, поменянные местами.vector<pair<size_t,size_t>>, Тогда вам не нужно беспокоиться о циклах. Вы можете применить перестановку к вектору, применив ту же последовательность перестановок. Вы можете отменить перестановку, применив обратную последовательность перестановок.

& quot; Помните, что перестановка - это std :: map, а не std :: vector & quot; - Я не вижу, как это меняет дело. В вашем оригинальном коде, если вы делаетеfor (unsigned int i = 0; i < numberOfElements; i++) { permutation[i] = 0; permutation[0] = i; }то вы получите множество нулей, независимо от типа контейнераpermutation является.
Самое смешное, что еслиrandomValue каждый раз оказывается равным 0, тогда моя перестановка в конечном итоге станет перестановкой тождеств. Помни чтоpermutation являетсяstd::mapнеstd::vector, Теперь я пытаюсь понять ваш комментарий относительно количества итераций, но это доставляет мне трудные времена. Не могли бы вы привести конкретный пример? Я вижу это как проблему, касающуюся количества итераций, которые я выполняю. Если я делаю только N итераций, то математика говорит, что я не получу правильно перетасованную перестановку, верно? Mihai Todor
@Mihai: Кстати, если ваш RNG работает с семени, то при перестановке вы можете выполнить обмен наinput и обойтись безpermutationэто именно то, чтоrandom_shuffle делает. При обращении перестановки вы можете повторно заполнить ГСЧ тем же семенем, а затем записать перестановки в вектор (илиstd::stack), а затем воспроизвести их задом напередinput, Такif Ваш ГСЧ воспроизводим, вам нужно только кратко хранить свопы.
@MihaiTodor: извините, может, тогда я неправильно прочитал код, прошлой ночью было немного поздно. Моя мысль была, "предположим, чтоrandomValue просто так получилось выйти0 каждый раз. Тогда ваша карта перестановок будет иметь все нули в качестве значений, за исключением того, чтоpermutation[0] будет равенnumberOfElements - 1, Извините, если это неправильно.
Что касается коррекции, на самом деле, это работает. Я не вижу, как я могу получить дубликаты, независимо от того, сколько итераций я выполняю. Спасибо за "Фишер-Йейтс" (Кнут Шаффл) предложение. Я помню, что теперь видел это где-то, но было очень поздно прошлым вечером :) Mihai Todor
0

Учитывая упорядоченную последовательность элементовa,b,c,d,e вы сначала создаете новую индексированную последовательность:X=(0,a),(1,b),(2,c),(3,d),(4,e), Затем вы случайным образом перемешаете эту последовательность и получите второй элемент каждой пары, чтобы получить случайную последовательность. Чтобы восстановить исходную последовательность, вы сортируетеX установить постепенно, используя первый элемент каждой пары.

@thb Это может быть интересный подход. Я подумаю об этом... Mihai Todor
Ответ работает хорошо, однако, если вы сделаете это(0,&a),(1,&b),(2,&c),(3,&d),(4,&e)хранение указателей на элементы, а не на сами элементы, предполагая, что вектор элементов не изменяется в промежуточный период (что приведет к аннулированию указателей).
Ну, да, но это будет связано с изменением моей векторной реализации с std :: vector на std :: map, а это не то, что мне нужно, потому что после применения перестановки мне придется временно клонировать его содержимоеstd::vector Mihai Todor

Похожие вопросы