<?xml version="1.0"?>
<feed xmlns="http://www.w3.org/2005/Atom" xml:lang="ru">
		<id>https://nerc.itmo.ru/wiki/api.php?action=feedcontributions&amp;feedformat=atom&amp;user=91.122.11.127&amp;*</id>
		<title>Викиконспекты - Вклад участника [ru]</title>
		<link rel="self" type="application/atom+xml" href="https://nerc.itmo.ru/wiki/api.php?action=feedcontributions&amp;feedformat=atom&amp;user=91.122.11.127&amp;*"/>
		<link rel="alternate" type="text/html" href="https://nerc.itmo.ru/wiki/index.php?title=%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:%D0%92%D0%BA%D0%BB%D0%B0%D0%B4/91.122.11.127"/>
		<updated>2026-11-16T20:41:00Z</updated>
		<subtitle>Вклад участника</subtitle>
		<generator>MediaWiki 1.30.0</generator>

	<entry>
		<id>https://nerc.itmo.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%B3%D0%B5%D0%BD%D0%B5%D1%80%D0%B0%D1%86%D0%B8%D0%B8_%D1%81%D0%BB%D1%83%D1%87%D0%B0%D0%B9%D0%BD%D0%BE%D0%B9_%D0%BF%D0%B5%D1%80%D0%B5%D1%81%D1%82%D0%B0%D0%BD%D0%BE%D0%B2%D0%BA%D0%B8,_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A4%D0%B8%D1%88%D0%B5%D1%80%D0%B0-%D0%99%D0%B5%D1%82%D1%81%D0%B0&amp;diff=63787</id>
		<title>Метод генерации случайной перестановки, алгоритм Фишера-Йетса</title>
		<link rel="alternate" type="text/html" href="https://nerc.itmo.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%B3%D0%B5%D0%BD%D0%B5%D1%80%D0%B0%D1%86%D0%B8%D0%B8_%D1%81%D0%BB%D1%83%D1%87%D0%B0%D0%B9%D0%BD%D0%BE%D0%B9_%D0%BF%D0%B5%D1%80%D0%B5%D1%81%D1%82%D0%B0%D0%BD%D0%BE%D0%B2%D0%BA%D0%B8,_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%A4%D0%B8%D1%88%D0%B5%D1%80%D0%B0-%D0%99%D0%B5%D1%82%D1%81%D0%B0&amp;diff=63787"/>
				<updated>2018-02-21T06:30:49Z</updated>
		
		<summary type="html">&lt;p&gt;91.122.11.127: /* Обоснование */&lt;/p&gt;
&lt;hr /&gt;
&lt;div&gt;'''Тасование Фишера-Йетса''' (названо в честь Рональда Фишера (Ronald Fisher) и Франка Йетса (Frank Yates)) {{---}} алгоритм создания случайных перестановок конечного множества, попросту говоря, для случайного тасования множества.  &lt;br /&gt;
Основная процедура тасования Фишера-Йетса аналогична случайному вытаскиванию записок с числами из шляпы или карт из колоды, один элемент за другим, пока элементы не кончатся. Алгоритм обеспечивает эффективный и строгий метод таких операций, гарантирующий несмещённый результат. Время работы алгоритма &amp;lt;tex&amp;gt; O(n)&amp;lt;/tex&amp;gt;.&lt;br /&gt;
==Применение алгоритма==&lt;br /&gt;
{{Задача&lt;br /&gt;
|definition = Необходимо сгенерировать случайную перестановку из &amp;lt;tex&amp;gt; n &amp;lt;/tex&amp;gt; чисел с равномерным распределением вероятности, если в наличии есть функция для генерации случайного числа в заданном интервале.&lt;br /&gt;
}}&lt;br /&gt;
===Решение:===&lt;br /&gt;
&lt;br /&gt;
Пусть &amp;lt;br/&amp;gt;&lt;br /&gt;
*&amp;lt;tex&amp;gt;\mathtt{random(1..i) }&amp;lt;/tex&amp;gt; генерирует случайное число в отрезке &amp;lt;tex&amp;gt; [1;\; i] &amp;lt;/tex&amp;gt; &amp;lt;br/&amp;gt;&lt;br /&gt;
Следующий алгоритм решает задачу:&lt;br /&gt;
&lt;br /&gt;
  '''int[n]''' randomPermutation(a: '''int[n]'''):  &amp;lt;font color = green&amp;gt; // '''n''' {{---}} длина перестановки &amp;lt;/font&amp;gt;&lt;br /&gt;
    '''for''' i = n '''downto''' 1&lt;br /&gt;
      j = random(1..i)&lt;br /&gt;
      swap(a[i], a[j])&lt;br /&gt;
    '''return''' a&lt;br /&gt;
&lt;br /&gt;
==Обоснование==&lt;br /&gt;
На каждой итерации цикла мы выбираем случайный элемент из всех оставшихся, то есть у нас есть &amp;lt;tex&amp;gt; n&amp;lt;/tex&amp;gt; способов выбрать &amp;lt;tex&amp;gt;1&amp;lt;/tex&amp;gt; элемент, &amp;lt;tex&amp;gt; n - 1&amp;lt;/tex&amp;gt; способов выбрать &amp;lt;tex&amp;gt;2&amp;lt;/tex&amp;gt; элемент... &amp;lt;tex&amp;gt; 1&amp;lt;/tex&amp;gt; способ выбрать последний элемент. Ни на одной итерации нам не попадется ни один элемент, который уже был выбран ранее, ведь на каждом шаге выбираемые числа мы переносим в конец массива путём перестановки с последним невыбранным числом. Таким образом, последовательность длины &amp;lt;tex&amp;gt; n&amp;lt;/tex&amp;gt; мы можем получить  &amp;lt;tex&amp;gt; n \times (n - 1) \times \ldots \times 1 = n!  &amp;lt;/tex&amp;gt; способами, что совпадает с числом различных перестановок длины &amp;lt;tex&amp;gt; n&amp;lt;/tex&amp;gt;. Это означает, что вероятность выбрать любую перестановку длины &amp;lt;tex&amp;gt; n&amp;lt;/tex&amp;gt; равна &amp;lt;tex&amp;gt; \dfrac{1}{n!}&amp;lt;/tex&amp;gt;, то есть все перестановки равновероятны.&lt;br /&gt;
&lt;br /&gt;
==Неправильные способы реализации==&lt;br /&gt;
Небольшая модификация этого алгоритма, может резко сказаться на его корректности. &lt;br /&gt;
&lt;br /&gt;
===Пример неправильной реализации:===&lt;br /&gt;
  '''for''' i = n '''downto''' 1&lt;br /&gt;
    swap(a[i], a[random(1..n)])&lt;br /&gt;
В данном случае число способов сгенерировать последовательность равно &amp;lt;tex&amp;gt;n^n&amp;lt;/tex&amp;gt;, в то время как существует всего &amp;lt;tex&amp;gt; n!&amp;lt;/tex&amp;gt; возможных перестановок из &amp;lt;tex&amp;gt; n&amp;lt;/tex&amp;gt; элементов. Поскольку &amp;lt;tex&amp;gt; n^n&amp;lt;/tex&amp;gt; никогда не может делиться на &amp;lt;tex&amp;gt; n!&amp;lt;/tex&amp;gt; без остатка при &amp;lt;tex&amp;gt; n &amp;gt; 2&amp;lt;/tex&amp;gt; (так как &amp;lt;tex&amp;gt; n!&amp;lt;/tex&amp;gt; делится на число &amp;lt;tex&amp;gt; n - 1&amp;lt;/tex&amp;gt; , которое не имеет с &amp;lt;tex&amp;gt; n&amp;lt;/tex&amp;gt; общих простых делителей), то некоторые перестановки должны появляться чаще, чем другие.&lt;br /&gt;
&lt;br /&gt;
===Другой пример неправильной реализации:===&lt;br /&gt;
  '''for''' i = n '''downto''' 1&lt;br /&gt;
    swap(a[random(1..n)], a[random(1..n)])&lt;br /&gt;
&lt;br /&gt;
Теперь уже число способов сгенерировать последовательность равно &amp;lt;tex&amp;gt;(n^2)^n&amp;lt;/tex&amp;gt;. По той же причине, что и раньше &amp;lt;tex&amp;gt; (n^2)^n&amp;lt;/tex&amp;gt; не делится на  &amp;lt;tex&amp;gt; n!&amp;lt;/tex&amp;gt; без остатка при &amp;lt;tex&amp;gt; n &amp;gt; 2&amp;lt;/tex&amp;gt;, следовательно некоторые перестановки будут появляться еще чаще.&lt;br /&gt;
&lt;br /&gt;
==См.также==&lt;br /&gt;
*[[Методы генерации случайного сочетания | Методы генерации случайного сочетания]]&lt;br /&gt;
==Источники информации==&lt;br /&gt;
*[http://bost.ocks.org/mike/shuffle/ Интерактивный пример]&lt;br /&gt;
*Д.Э. Кнут Искусство программирования, том 2. Получисленные методы — 3-е изд. — М.: «Вильямс», 2007. — С. 832. — ISBN 0-201-89684-2&lt;br /&gt;
*[https://ru.wikipedia.org/wiki/%D0%A2%D0%B0%D1%81%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%A4%D0%B8%D1%88%D0%B5%D1%80%D0%B0%E2%80%93%D0%99%D0%B5%D1%82%D1%81%D0%B0 Википедия — Тасование Фишера-Йетса]&lt;br /&gt;
*[https://en.wikipedia.org/wiki/Fisher–Yates_shuffle Wikipedia — Fisher-Yates shuffle]&lt;br /&gt;
&lt;br /&gt;
[[Категория: Дискретная математика и алгоритмы]]&lt;br /&gt;
&lt;br /&gt;
[[Категория: Комбинаторика ]]&lt;br /&gt;
&lt;br /&gt;
[[Категория: Генерация комбинаторных объектов]]&lt;/div&gt;</summary>
		<author><name>91.122.11.127</name></author>	</entry>

	</feed>