Получение номера по объекту - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:18:51Z

rollbackEdits.php mass rollback

171.25.193.80 в 05:25, 1 сентября 2022

2022-09-01T05:25:40Z

Npanuhin: Лишняя переменная P, кол-во перестановок = n!

2021-12-31T10:33:00Z

Лишняя переменная P, кол-во перестановок = n!

90.154.72.10: Исправил опечатку с $$

2021-06-10T18:58:14Z

Исправил опечатку с $$

176.59.17.215: /* Разбиение на слагаемые */ косметические изменения

2017-12-26T16:08:45Z

‎Разбиение на слагаемые: косметические изменения

Arimon: /* Разбиение на слагаемые */

2017-12-25T22:43:33Z

‎Разбиение на слагаемые

Arimon: /* Разбиение на слагаемые */ поправлен стиль псевдокода

2017-12-25T22:39:43Z

‎Разбиение на слагаемые: поправлен стиль псевдокода

Arimon: /* Разбиение на слагаемые */ исправлена грамматика и косметические изменения

2017-12-25T22:30:15Z

‎Разбиение на слагаемые: исправлена грамматика и косметические изменения

176.59.3.13: /* Разбиение на слагаемые */ исправлен внешний цикл

2017-12-24T17:30:50Z

‎Разбиение на слагаемые: исправлен внешний цикл

Arimon: /* Разбиение на слагаемые */ добавлена точка в конце предложения

2017-12-24T14:15:55Z

‎Разбиение на слагаемые: добавлена точка в конце предложения

← Предыдущая		Версия 16:18, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	== Описание алгоритма ==		== Описание алгоритма ==
	Номер данного [[Комбинаторные объекты\|комбинаторного объекта]] равен количеству меньших в [[Лексикографический порядок\|лексикографическом порядке]] комбинаторных объектов (нумерацию ведём с <tex>0</tex>). Все объекты меньшие данного можно разбить на непересекающиеся группы по длине совпадающего префикса. Тогда количество меньших объектов можно представить как сумму количеств объектов у которых префикс длины <tex>i</tex> совпадает, а <tex>i+1</tex> элемент лексикографически меньше <tex>(i+1)</tex>-го в данном объекте (<tex>i = 0..n-1</tex>).		Номер данного [[Комбинаторные объекты\|комбинаторного объекта]] равен количеству меньших в [[Лексикографический порядок\|лексикографическом порядке]] комбинаторных объектов (нумерацию ведём с <tex>0</tex>). Все объекты меньшие данного можно разбить на непересекающиеся группы по длине совпадающего префикса. Тогда количество меньших объектов можно представить как сумму количеств объектов у которых префикс длины <tex>i</tex> совпадает, а <tex>i+1</tex> элемент лексикографически меньше <tex>(i+1)</tex>-го в данном объекте (<tex>i = 0..n-1</tex>).

← Предыдущая		Версия 05:25, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	== Описание алгоритма ==		== Описание алгоритма ==
	Номер данного [[Комбинаторные объекты\|комбинаторного объекта]] равен количеству меньших в [[Лексикографический порядок\|лексикографическом порядке]] комбинаторных объектов (нумерацию ведём с <tex>0</tex>). Все объекты меньшие данного можно разбить на непересекающиеся группы по длине совпадающего префикса. Тогда количество меньших объектов можно представить как сумму количеств объектов у которых префикс длины <tex>i</tex> совпадает, а <tex>i+1</tex> элемент лексикографически меньше <tex>(i+1)</tex>-го в данном объекте (<tex>i = 0..n-1</tex>).		Номер данного [[Комбинаторные объекты\|комбинаторного объекта]] равен количеству меньших в [[Лексикографический порядок\|лексикографическом порядке]] комбинаторных объектов (нумерацию ведём с <tex>0</tex>). Все объекты меньшие данного можно разбить на непересекающиеся группы по длине совпадающего префикса. Тогда количество меньших объектов можно представить как сумму количеств объектов у которых префикс длины <tex>i</tex> совпадает, а <tex>i+1</tex> элемент лексикографически меньше <tex>(i+1)</tex>-го в данном объекте (<tex>i = 0..n-1</tex>).

@@ Строка 35: / Строка 35: @@
 Рассмотрим алгоритм получения номера в лексикографическом порядке по данной перестановке размера <tex>n</tex>,
 *<tex>\mathtt{a[1..n]}</tex> {{---}} данная перестановка,
-*<tex>\mathtt{P[1..n]}</tex> {{---}} количество перестановок данного размера,
+*<tex>\mathtt{(n - i)!}</tex> {{---}} количество перестановок размера <tex>(n - i)</tex>,
 *<tex>\mathtt{was[1..n]}</tex> {{---}} использовали ли мы уже эту цифру в перестановке,
@@ Строка 43: / Строка 43: @@
       '''for''' j = 1  '''to''' a[i] - 1              <font color=green>// перебираем элементы, лексикографически меньшие нашего, которые могут стоять на <tex>i</tex>-м месте</font>
         '''if''' was[j] == ''false''                <font color=green>// если элемент <tex>j</tex> ранее не был использован</font>
-          numOfPermutation += P[n - i]    <font color=green>// все перестановки с префиксом длиной <tex>i-1</tex> равным нашему, и <tex>i</tex>-й элемент у которых</font>
+          numOfPermutation += (n - i)!    <font color=green>// все перестановки с префиксом длиной <tex>i-1</tex> равным нашему, и <tex>i</tex>-й элемент у которых</font>
                                              <font color=green>меньше нашего в лексикографическом порядке, идут раньше данной перестановки</font>
       was[a[i]] = ''true''                    <font color=green>// <tex>i</tex>-й элемент использован</font>

@@ Строка 51: / Строка 51: @@
 == Сочетания ==
-Рассмотрим алгоритм получения номера в лексикографическом порядке данного сочетания из <tex>n</tex> по <tex>k</tex>. Как известно, количество сочетаний из <tex>n</tex> по <tex>k</tex> обозначается как <tex dpi=140>\binom{n}{k}</tex>. Тогда число сочетаний, в которых на позиции <tex>1</tex> стоит значение <tex>val_1</tex>, равно <tex dpi=140>$$\sum\limits^{val_1-1}_{i=1} {\binom{n-i}{k-1}}$$</tex>; число сочетаний, в которых на позиции <tex>2</tex> стоит значение <tex>val_2</tex>, равно <tex dpi=140>$$\sum\limits^{val_2-1}_{i=val_1+1} {\binom{n-i}{k-2}}$$</tex>. Аналогично продолжаем по следующим позициям:
+Рассмотрим алгоритм получения номера в лексикографическом порядке данного сочетания из <tex>n</tex> по <tex>k</tex>. Как известно, количество сочетаний из <tex>n</tex> по <tex>k</tex> обозначается как <tex dpi=140>\binom{n}{k}</tex>. Тогда число сочетаний, в которых на позиции <tex>1</tex> стоит значение <tex>val_1</tex>, равно <tex dpi=140>\sum\limits^{val_1-1}_{i=1} {\binom{n-i}{k-1}}</tex>; число сочетаний, в которых на позиции <tex>2</tex> стоит значение <tex>val_2</tex>, равно <tex dpi=140>\sum\limits^{val_2-1}_{i=val_1+1} {\binom{n-i}{k-2}}</tex>. Аналогично продолжаем по следующим позициям:
 *<tex>\mathtt{numOfChoose}</tex> {{---}} искомый номер сочетания,
 *<tex>\mathtt{C[n][k]}</tex> {{---}} количество сочетаний из <tex>n</tex> по <tex>k</tex>, <tex>\mathtt{C[n][0] = 1}</tex>,

@@ Строка 88: / Строка 88: @@
   '''int''' part2num(part: '''list<int>'''):
-    '''int''' numOfPart = 0, last = 0, sum = 0
+    numOfPart = 0, last = 0, sum = 0
     '''for''' i = 1 '''to''' part.size
-      '''for''' j = last '''to''' part[i] - 1            <font color=green>// перебираем все элементы, лексикографически меньшие нашего, но большие или равные предыдущего</font>
+      '''for''' j = last '''to''' part[i] - 1            <font color=green>// перебираем все элементы, лексикографически меньшие текущего, но не меньшие предыдущего</font>
         numOfPart += d[N - sum - j][j]       <font color=green>// прибавляем количество перестановок, которые могли начинаться с <tex>j</tex></font>
       sum += part[i]                         <font color=green>// увеличиваем уже поставленную сумму</font>

@@ Строка 66: / Строка 66: @@
 == Разбиение на слагаемые ==
-Рассмотрим алгоритм получения номера в лексикографическом порядке данного разбиения на слагаемые числа <tex>N</tex>. Нужно помнить о том, что разбиения, отличающиеся только порядком слагаемых, считаются одинаковыми. Из всех разбиений, получаемых перестановками слагаемых, выберем то, где слагаемые упорядочены лексикографически, и будем строить его.
+Рассмотрим алгоритм получения номера, в лексикографическом порядке, по данному разбиению на слагаемые числа <tex>N</tex>. Нужно помнить о том, что разбиения, отличающиеся только порядком слагаемых, считаются одинаковыми. Из всех разбиений, получаемых перестановками слагаемых, выберем то, где слагаемые упорядочены лексикографически, и будем строить его.
 *<tex>\mathtt{numOfPart}</tex> {{---}} искомый номер разбиения
@@ Строка 87: / Строка 87: @@
-  '''int''' part2num(part: '''list<int>'''):
+  '''int''' part2num('''list<int>''' part):
-    numOfPart = 0
+    '''int''' numOfPart = 0, last = 0, sum = 0
     '''for''' i = 1 '''to''' part.size
       '''for''' j = last '''to''' part[i] - 1            <font color=green>// перебираем все элементы, лексикографически меньшие нашего, но большие или равные предыдущего</font>

@@ Строка 96: / Строка 96: @@
      '''return''' numOfPart <font color=green>// возвращаем ответ</font>
-Стоит отметить, что количество итераций вложенного цикла не более, чем <tex>N</tex>, так как всего количество возможных слагаемых {{---}} <tex>N</tex>, и ни какое из них цикл не обработает дважды, поскольку каждый раз начинает с <tex>last</tex>, которое больше чем любое из обработанных чисел. Поэтому асимптотика алгоритма {{---}} <tex>O(N)</tex>
+Стоит отметить, что количество итераций вложенного цикла не более, чем <tex>N</tex>, так как всего количество возможных слагаемых {{---}} <tex>N</tex>, и ни какое из них цикл не обработает дважды, поскольку каждый раз начинает с <tex>last</tex>, которое больше чем любое из обработанных чисел. Поэтому асимптотика алгоритма {{---}} <tex>O(N)</tex>.
 Асимптотика алгоритма {{---}} <tex> O (N)</tex> и <tex>O(N^2)</tex> на предподсчёт.