Редактирование: Методы генерации случайного сочетания

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 6: Строка 6:
 
==Наивное решение==
 
==Наивное решение==
  
Пусть <tex>S</tex>  —  множество из <tex>n</tex> элементов, тогда для генерации случайного сочетания сделаем следующее:
+
Пусть <tex>S</tex>  —  массив из <tex>n</tex> элементов, тогда для генерации случайного сочетания сделаем следующее:
* '''Шаг 1.''' Запишем в массив <tex>C</tex> числа от <tex>1</tex> до <tex>k</tex>,
+
* запишем в массив <tex>C</tex> числа от <tex>1</tex> до <tex>k</tex>,
* '''Шаг 2.''' Выберем случайный номер сочетания <tex>r</tex>,
+
* выберем случайные номер сочетания <tex>r</tex>,
* '''Шаг 3.''' Применим алгоритм [[Получение следующего объекта|получение следующего сочетания]] <tex>r - 1</tex> раз к массиву <tex>C</tex>,
+
* применим алгоритм генерации следующего сочетания <tex>r - 1</tex> раз к массиву <tex>C</tex>.
* '''Шаг 4.''' В <tex>C</tex> хранятся номера позиции из <tex>S</tex> входящих в случайное сочетание, запишем в <tex>C</tex> эти элементы.
+
 
 +
<br/>
 +
*<tex>\mathrm{random(1..i)}</tex> генерирует случайное число в интервале <tex> [1;\; i] </tex> <br/>
 +
 
 
===Псевдокод===
 
===Псевдокод===
*<tex>\mathtt{arrayOfElements}</tex> — массив, в котором находятся все элементы множества <tex>\mathtt{S}</tex>.
+
 
 
<code>
 
<code>
   '''int[]''' randomCombination('''int[]''' arrayOfElements, '''int''' n, '''int''' k):
+
   '''int[]''' randomCombination('''int[]''' S, '''int''' n, '''int''' k)
 +
    sort(S);
 
     '''for''' i = 1 '''to''' k  
 
     '''for''' i = 1 '''to''' k  
 
       C[i] = i
 
       C[i] = i
     r = random(1, n! / (k!(n - k)!))     <font color=darkgreen> //random(1, i) генерирует случайное целое число в интервале [1..i]</font color=darkgreen>
+
     r = random(1, n! / (k!(n - k)!))
 
     '''for''' i = 1 '''to''' r - 1
 
     '''for''' i = 1 '''to''' r - 1
       nextCombination(C, n, k)           <font color=darkgreen> //nextCombination(C, n, k) генерирует следующие сочетание</font color=darkgreen>
+
       next_Combination(C, n, k)
 
     '''for''' i = 1 '''to''' k
 
     '''for''' i = 1 '''to''' k
       C[i] = arrayOfElements[C[i]]
+
       C[i] = S[C[i]]
 
     '''return''' C
 
     '''return''' C
 
</code>
 
</code>
  
Сложность алгоритма — <tex dpi="150">O({n! \over k!(n - k)!} \cdot n)</tex>.
+
==Решение за время <tex>O(n ^ 2)</tex>==
 
 
==Решение за время <tex>O(nk)</tex>==
 
  
 
Пусть <tex>S</tex>  —  множество из <tex>n</tex> элементов, тогда для генерации случайного сочетания сделаем следующее:
 
Пусть <tex>S</tex>  —  множество из <tex>n</tex> элементов, тогда для генерации случайного сочетания сделаем следующее:
* '''Шаг 1.''' Выберем в множестве случайный элемент,
+
* выберем в множестве случайный элемент,
* '''Шаг 2.''' Добавим его в сочетание,
+
* добавим его в сочетание,
* '''Шаг 3.''' Удалим элемент из множества.
+
* удалим элемент из множества.
  
 
Эту процедуру необходимо повторить <tex>k</tex> раз.
 
Эту процедуру необходимо повторить <tex>k</tex> раз.
 +
 
===Псевдокод===
 
===Псевдокод===
*<tex>\mathtt{arrayOfElements}</tex> — массив, в котором находятся все элементы множества <tex>\mathtt{S}</tex>,
+
  randomCombination(arrayOfElements, n, k)
*<tex>\mathtt{exist}</tex> — такой массив, что если <tex>\mathtt{exist[i] == 1}</tex>, то <tex>\mathtt{i}</tex> элемент присутствует в множестве <tex>\mathtt{S}</tex>,
 
<code>
 
  '''int[]''' randomCombination('''int[]''' arrayOfElements, '''int''' n, '''int''' k):
 
 
   '''for''' i = 1 '''to''' k  
 
   '''for''' i = 1 '''to''' k  
     r = random(1, (n - i + 1))              
+
     r = rand(1..(n - i + 1))
 
     cur = 0
 
     cur = 0
 
     '''for''' j = 1 '''to''' n  
 
     '''for''' j = 1 '''to''' n  
 
       '''if''' exist[j]
 
       '''if''' exist[j]
         cur = cur + 1
+
         cur++;
 
         '''if''' cur == r
 
         '''if''' cur == r
 
           res[i] = arrayOfElements[j]
 
           res[i] = arrayOfElements[j]
Строка 51: Строка 51:
 
   sort(res)
 
   sort(res)
 
   '''return''' res
 
   '''return''' res
</code>
+
 
 +
Здесь <tex>exist</tex> — такой массив, что если <tex>exist[i] == 1</tex>, то <tex>i</tex> элемент присутствует в множестве <tex>S</tex>.
 +
 
 +
Сложность алгоритма  —  <tex>O(n^2)</tex>
  
 
===Доказательство корректности алгоритма===
 
===Доказательство корректности алгоритма===
На первом шаге мы выбираем один элемент из <tex>n</tex>, на втором из <tex>n - 1</tex> <tex>\dots</tex>  на <tex>k</tex>-ом из <tex>n - k + 1</tex>. Тогда общее число исходов получится <tex>n \times (n - 1) \times \dots \times (n - k + 1)</tex>. Это эквивалентно <tex dpi="180">{n! \over (n - k)!}</tex>. Однако заметим, что на этом шаге у нас получаются лишь размещения из <tex>n</tex> по <tex>k</tex>. Но все эти размещения можно сопоставить одному сочетанию, отсортировав их. И так как размещения равновероятны, и каждому сочетанию сопоставлено ровно <tex>k!</tex> размещений, то сочетания тоже генерируются равновероятно.
+
На первом шаге мы выбираем один элемент из <tex>n</tex>, на втором из <tex>n - 1</tex>, ..., на <tex>k</tex>-ом из <tex>n - k + 1</tex>. Тогда общее число исходов получится <tex>n \cdot (n - 1) \cdot ... \cdot (n - k + 1)</tex>. Это эквивалентно <tex dpi="180">{n! \over (n - k)!}</tex>. Однако заметим, что на этом шаге у нас получаются лишь размещения из <tex>n</tex> по <tex>k</tex>. Но все эти размещения можно сопоставить одному сочетанию, отсортировав их. И так как размещения равновероятны, и каждому сочетанию сопоставлено ровно <tex>k!</tex> размещений, то сочетания тоже генерируются равновероятно.
  
 
==Решение за время <tex>O(n)</tex>==
 
==Решение за время <tex>O(n)</tex>==
  
 
Для более быстрого решения данной задачи воспользуемся следующим алгоритмом: пусть задан для определенности массив <tex>a</tex> размера <tex>n</tex>, состоящий из <tex>k</tex> единиц и <tex>n - k</tex> нулей. Применим к нему [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса|алгоритм генерации случайной перестановки]]. Тогда все элементы <tex>i</tex>, для которых <tex>a[i] = 1</tex>, включим в сочетание.
 
Для более быстрого решения данной задачи воспользуемся следующим алгоритмом: пусть задан для определенности массив <tex>a</tex> размера <tex>n</tex>, состоящий из <tex>k</tex> единиц и <tex>n - k</tex> нулей. Применим к нему [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса|алгоритм генерации случайной перестановки]]. Тогда все элементы <tex>i</tex>, для которых <tex>a[i] = 1</tex>, включим в сочетание.
 +
 
===Псевдокод===
 
===Псевдокод===
*<tex>\mathtt{arrayOfElements}</tex> — массив, в котором находятся все элементы множества <tex>\mathtt{S}</tex>,
+
 
*<tex>\mathtt{randomShuffle()}</tex> — функция генерации случайной перестановки.
 
 
<code>
 
<code>
   '''int[]''' randomCombination('''int[]''' arrayOfElements, '''int''' n, '''int''' k):
+
   randomCombination(arrayOfElements, n, k)
 
     '''for''' i = 1 '''to''' n  
 
     '''for''' i = 1 '''to''' n  
 
       '''if''' i <= k
 
       '''if''' i <= k
Строка 69: Строка 72:
 
       '''else'''
 
       '''else'''
 
         a[i] = 0
 
         a[i] = 0
     randomShuffle(a)                       <font color=darkgreen> //randomShuffle() — функция генерации случайной перестановки</font color=darkgreen>
+
     random_shuffle(a)
 
     '''for''' i = 1 '''to''' n
 
     '''for''' i = 1 '''to''' n
 
       '''if''' a[i] == 1
 
       '''if''' a[i] == 1
Строка 81: Строка 84:
 
===Оценка временной сложности===
 
===Оценка временной сложности===
  
Алгоритм состоит из двух невложенных циклов по <tex>n</tex> итераций каждый и функции генерации случайной перестановки <tex>\mathrm{randomShuffle()}</tex>, работающей за <tex>O(n)</tex> по алгоритму [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса|Фишера—Йетcа]]. Следовательно, сложность и всего алгоритма <tex>O(n)</tex>
+
Алгоритм состоит из 2 невложенных циклов по <tex>n</tex> итераций каждый и функции генерации случайной перестановки <tex>\mathrm{random_shuffle()}</tex>, работающей за <tex>O(n)</tex> по алгоритму [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса|Фишера—Йетcа]]. Следовательно, сложность и всего алгоритма <tex>O(n)</tex>
  
 
== См. также ==
 
== См. также ==

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)

Шаблон, используемый на этой странице: