Алгоритм для выбора одной, случайной комбинации значений?

Скажем, у меня есть разные значения, и я хочу выбрать x из них наугад. Каков эффективный алгоритм для этого? Я мог бы просто называть rand() x раз, но производительность была бы плохой, если x , y были большими.

Обратите внимание, что здесь нужны комбинации : каждое значение должно иметь такую ​​же вероятность, чтобы быть выбранным, но их порядок в результате не важен. Конечно, любой алгоритм, генерирующий перестановки, будет квалифицироваться, но мне интересно, можно ли сделать это более эффективно без требования случайного порядка.

Как эффективно генерировать список из K неповторяющихся целых чисел между 0 и верхней границей N охватывает этот случай для перестановок.

Роберт Флойд изобрел алгоритм выборки для таких ситуаций. Обычно он превосходит перетасовку, а затем захватывает первые элементы x так как он не требует хранения O (y). Как первоначально написано, он принимает значения из 1..N, но тривиально производить 0..N и / или использовать несмежные значения, просто обрабатывая значения, которые он выражает как индексы, в вектор / array / whatever.

В псевдокоде алгоритм работает следующим образом (краду из колонки программирования Джона Бентли «Перстень Бриллианта»).

 initialize set S to empty for J := NM + 1 to N do T := RandInt(1, J) if T is not in S then insert T in S else insert J in S 

Этот последний бит (вставка J, если T уже находится в S), является сложной частью. Суть в том, что он обеспечивает правильную математическую вероятность вставки J, чтобы он давал непредвзятые результаты.

Это O (x) 1 и O (1) относительно хранения y , O (x) .

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


1 O (x 2 ) в худшем случае для включения hash-отображения, которым можно пренебречь, поскольку это практически несуществующий патологический случай, когда все значения имеют одинаковый хеш

Предполагая, что вы хотите, чтобы заказ был случайным (или не против, чтобы это было случайным), я просто использовал бы усеченный Fisher-Yates shuffle. Запустите алгоритм перетасовки, но остановитесь, как только вы выбрали первые значения x , вместо «случайного выбора» всех y из них.

Фишер-Йейтс работает следующим образом:

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

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

Конечно, это означает, что вы испортили входной массив – если это означает, что вам нужно будет взять его копию перед запуском, а x мало по сравнению с y, тогда копирование всего массива не очень эффективно. Обратите внимание, что если все, что вы собираетесь использовать в будущем, это еще один выбор, то тот факт, что он находится в несколько случайном порядке, не имеет значения, вы можете просто использовать его снова. Если вы делаете выбор несколько раз, следовательно, вы можете сделать только одну копию в начале и амортизировать стоимость.

Если вам действительно нужно создавать комбинации – где порядок элементов не имеет значения – вы можете использовать комбинаторы, поскольку они реализованы, например, здесь, Джеймс МакКафри .

Сравните это с k-перестановками , где порядок элементов имеет значение.

В первом случае (1,2,3) , (1,3,2) , (2,1,3) , (2,3,1) , (3,1,2) , (3,2,1 ) считаются одинаковыми – в последнем они считаются отличными, хотя они содержат одни и те же элементы.

Если вам нужны комбинации, вам может понадобиться генерировать только одно случайное число (хотя оно может быть немного большим), которое может быть использовано непосредственно для поиска m- й комбинации. Так как это случайное число представляет собой индекс конкретной комбинации, то ваше случайное число должно быть между 0 и C (n, k) . Вычисление combinadics может занять некоторое время.

Это может просто не стоить проблем – кроме того , ответ Джерри и Федерико, безусловно, проще, чем реализация комбинаторов. Однако, если вам действительно нужна только комбинация, и вы пытаетесь генерировать точное количество случайных бит, которые необходимы, и больше ничего … 😉

Пока неясно, нужны ли вам комбинации или k-перестановки, вот код C # для последнего (да, мы могли бы сгенерировать только дополнение, если x> y / 2, но тогда мы остались бы с комбинацией, которая должна перетасовываться, чтобы получить реальную k-перестановку):

 static class TakeHelper { public static IEnumerable TakeRandom( this IEnumerable source, Random rng, int count) { T[] items = source.ToArray(); count = count < items.Length ? count : items.Length; for (int i = items.Length - 1 ; count-- > 0; i--) { int p = rng.Next(i + 1); yield return items[p]; items[p] = items[i]; } } } class Program { static void Main(string[] args) { Random rnd = new Random(Environment.TickCount); int[] numbers = new int[] { 1, 2, 3, 4, 5, 6, 7 }; foreach (int number in numbers.TakeRandom(rnd, 3)) { Console.WriteLine(number); } } } 

Другая, более сложная реализация, которая генерирует k-перестановки , что я лежал, и я считаю, что это улучшает существующие алгоритмы, если вам нужно только перебирать результаты. Хотя он также должен генерировать x случайных чисел, он использует только O (min (y / 2, x)) память в процессе:

  ///  /// Generates unique random numbers ///  /// Worst case memory usage is O(min((emax-imin)/2, num)) ///  ///  /// Random source /// Inclusive lower bound /// Exclusive upper bound /// Number of integers to generate /// Sequence of unique random numbers public static IEnumerable UniqueRandoms( Random random, int imin, int emax, int num) { int dictsize = num; long half = (emax - (long)imin + 1) / 2; if (half < dictsize) dictsize = (int)half; Dictionary trans = new Dictionary(dictsize); for (int i = 0; i < num; i++) { int current = imin + i; int r = random.Next(current, emax); int right; if (!trans.TryGetValue(r, out right)) { right = r; } int left; if (trans.TryGetValue(current, out left)) { trans.Remove(current); } else { left = current; } if (r > current) { trans[r] = left; } yield return right; } } 

Общая идея состоит в том, чтобы сделать Shisher Fisher-Yates и запомнить транспозиции в перестановке . Он не был опубликован нигде и не получил никакого экспертного обзора. Я считаю, что это скорее любопытство, чем практическое значение. Тем не менее я очень открыт для критики и, как правило, хотел бы знать, если вы обнаружите в этом что-то не так – подумайте об этом (и добавьте комментарий перед downvoting).

Небольшое предложение: если x >> y / 2, то, вероятно, лучше выбрать случайные элементы y – x, а затем выбрать дополнительный набор.

Если, например, у вас есть 2 ^ 64 различных значения, вы можете использовать алгоритм симметричных ключей (с блоком из 64 бит), чтобы быстро перетасовать все комбинации. (например, Blowfish).

 for(i=0; i 

Это не случайно в чистом смысле, но может быть полезно для вашей цели. Если вы хотите работать с произвольными # различных значений, следуя криптографическим методам, вы можете, но это сложнее.

Хитрость заключается в использовании вариации тасования или, другими словами, частичного перетасовки.

 function random_pick( a, n ) { N = len(a); n = min(n, N); picked = array_fill(0, n, 0); backup = array_fill(0, n, 0); // partially shuffle the array, and generate unbiased selection simultaneously // this is a variation on fisher-yates-knuth shuffle for (i=0; i=0; i--) // O(n) times { selected = backup[ i ]; value = a[ N ]; a[ N ] = a[ selected ]; a[ selected ] = value; N++; } return picked; } 

ПРИМЕЧАНИЕ. Алгоритм строго O(n) как во времени, так и в пространстве , создает несмещенные выборки (это частичная несмещенная перетасовка ) и неразрушающий на входном массиве (в качестве частичного перетасовки), но это необязательно

адаптирован отсюда

Обновить

другой подход, использующий только один вызов PRNG (генератор псевдослучайных чисел) в [0,1] ИВАН СТОЙМЕНОВИЧ, «О СЛУЧАЙНОМ И АДАПТИВНОМ ПАРАЛЛЕЛЬНОМ ПОКОЛЕНИИ КОМБИНАТОРНЫХ ОБЪЕКТОВ» (раздел 3 ), O(N) случае) сложность

введите описание изображения здесь

Вот простой способ сделать это, что является только неэффективным, если Y много больше X

 void randomly_select_subset( int X, int Y, const int * inputs, int X, int * outputs ) { int i, r; for( i = 0; i < X; ++i ) outputs[i] = inputs[i]; for( i = X; i < Y; ++i ) { r = rand_inclusive( 0, i+1 ); if( r < i ) outputs[r] = inputs[i]; } } 

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

Случайное число также используется для выбора элемента нашего (изменяемого) выходного массива для замены.

Interesting Posts

Группировка элементов в ComboBox

Вычисление суммы повторяющихся элементов в AngularJS ng-repeat

Есть ли веская причина использовать «printf» вместо «print» в java?

Событие, зарегистрированное в CheckedListBox?

Eclipse экспортирован Runnable JAR, не отображающий изображения

Как заставить Safari открывать результаты поиска на новой вкладке по умолчанию?

Плагин Phonegap: как преобразовать строку Base64 в PNG-изображение в Android

Изменение домена поиска Google по умолчанию

Выходной журнал ошибок / предупреждений (txt-файл) при запуске R-скрипта в командной строке

Почему копирование файлов в проводнике Windows намного медленнее командной строки

Выводит ли квадрат из прямоугольника нарушением Принципа замещения Лискова?

Как POST объект JSON для службы JAX-RS

Cookie заблокирован / не сохранен в IFRAME в Internet Explorer

Скопируйте большой файл по ненадежной ссылке

Windows Vista, не удалось загрузить в безопасном режиме или загрузить предыдущий вход в стандартных условиях. HP Pavillion DV6000

Давайте будем гением компьютера.