Блог пользователя nerd

Выбрать N из M
Автор nerd, 13 лет назад, По-русски

Всем привет!

Как можно сгенерировать N различных случайных элементов из [1..M]. Где N ≤ M.

Например, M = 10, N = 5. Ответом может быть: 2 4 1 9 5.

N ≤ M ≤ 106.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
За O (M) совсем просто: сгенерировать случайную перестановку за линейное время и взять первые N элементов.
→ Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится -9 Проголосовать: не нравится

Cnm способами. Даже не знаю как подробнее ответить.


Если серьезно, то можно выписать все сделать random_shuffle и вывести первые N. Вроде бы равновероятно даже будет.

UPD: Как написать n и m друг под другом, а не так как вышло?
→ Ответить
  • 13 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Кстати, хороший вопрос, как это сделать, если N сильно больше меньше M. Я так сразу умею только за O (N log N) каким-нибудь деревом типа отрезков.

    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Ну мы же random_shuffle после n-ной итерации останавливаем, от величины m асимптотика вообще не зависит.

      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Да, но так получится перестановка длины n. Которая, действительно, не зависит от m, но это не то, что нам нужно.
        → Ответить
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Если делать правильно, то получится то что нужно. Алгоритм: на i-ой итерации менять i-ый элемент со случайным элементом из множества [i,n]. Очевидно, что такой алгоритм не меняет первые n элементов после n-ой итерации, а потому может быть остановлен сразу после нее. В первых n элементах он будет содержать ответ на поставленную выше задачу.
          → Ответить
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            А правда, что при этом нужно O(m) памяти? Или можно как-то этого избежать и при этом сохранить равновероятность перестановок?

            Наверное, можно, храня числа  ≤ n на позициях больше n в какой-нибудь [hash_]map.
            → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Ну если массива нет сразу то не очень понятно, как его сделать, а создать его за О(М)
        → Ответить
    • 13 лет назад, # ^ |
      ← Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

      Так а хэш-таблицей, не? Будет О(n) Хотя, наверное, есть способ и поизящнее.

      UPD. Впрочем, рандомные ключи в хэш-таблице это тоже гуд.

      → Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    — \displaystyle C_n^m. А с HTML вообще так можно сделать?
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится +11 Проголосовать: не нравится
      То что сделал я - C\_n^m . Codeforces простые формулы заменяет на html сам.
      → Ответить
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Ну, вопрос в том, можно ли с HTML исправить этот недочёт. Интуитивно кажется, что наверняка как-то да можно, только решение не будет красивым.
        → Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Оо, индус по-русски пишет. Похвально! :)
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Только заметили?!

    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится +11 Проголосовать: не нравится
      Как-будто я в каждый профиль у каждого поста тыкаю и смотрю кто он и из какой страны. Да только сейчас.
      → Ответить
13 лет назад, # |
← Rev. 2   Проголосовать: нравится -12 Проголосовать: не нравится

Случайно выбрать N чисел из M (сдачу карт из колоды) вроде бы не проблема, а поскольку M<=10^6, то вроде даже всего за N выемок (мегатупо с массивом) можно сделать, переставляя последнее число на место освободившегося.

Или я не понял чего хотел автор? Ну тогда уж сорри, пишите разборчивее. ;-)

→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Извините, но по-поему понятно, чего я хотел. Разве я стал бы спрашивать просто вывести первые M чисел из N. Ведь 1, 2, ..., M тоже одна из перестановок. Тем более я написал "случайных".
    → Ответить
    • 13 лет назад, # ^ |
        Проголосовать: нравится -9 Проголосовать: не нравится
      Извините, но по-поему понятно, чего я хотел.

      Не извиню. Не удивительно, что вам понятно, чего вы хотели.

      Непонятно потому, что вы написали "сгенерировать N случайных элементов" вместо "выбрать N чисел из диапазона". Ну и потому что если вы именно это и имели в виду, то непонятно в чём проблема.
      → Ответить
13 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
Можно выбрать N случайных чисел из [1..M-N+1], отсортировать их и прибавить к каждому его номер в отсортированном порядке. Не гарантирую, что все сочетания окажутся равновероятными :)
→ Ответить