Случайные неповторяющиеся

Байт · Регистрация: 24.12.2010

Author24 — интернет-сервис помощи студентам

Задача известная. Заполнить массив a[k] случайными НЕПОВТОРЯЮЩИМИСЯ числами из диапазона 1 - N
для k = N есть изящнейшее https://ru.wikipedia.org/wiki/... 1%81%D0%B0 в варианте Дуршенфильда. Оно записывается в 5 строк простого кода, и действительно с равной вероятностью генерирует случайные перестановки.
Предупреждение! Потенциально бесконечные алгоритмы типа "сгененрировать случайное и посмотреть, нет ли уже такого" не рассматриваются. Также не рассматриваются простые "тасовки". Они не дадут никогда равновероятности.
Однако, рассмотрим случай N > k.
Если больше не намного, можно создать массив a[N], применить к нему k раз вышеприведенный алгоритм и успокоиться.
А если намного? Памяти-то жалко!
И вот приснился буквально такой алгоритм. Можно псевдокодон на Си? Словами дольше...

C

int b[k+1]; // Массив интервалов
for(i=0; i<k; i++)
   b[i] = 1;
b[k] = 0;
for(i=0; i<N-k-1; i++) {
  m = rand()%(k+1);
  b[m]++;
}
a[0] = b[0];
for(i=1; i< k; i++)
  a[i] = a[i-1] + b[i];

Добавлено через 14 минут
Как будто и случайность, и неповторяемость обеспечены. Более того, в следующую ночь я увидел, что этот алгоритм обеспечивает N!/(N-k)! вариантов, что позволяет надеяться, что все варианты равновероятны.
Я прекрасно понимаю, что скорее всего изобрел велосипед. Но согласитесь, кататься на собственном изобретении много приятнее и полезнее, чем на самом супер-пупер раскрученном бренде.

Вопросы к знатокам.
Так ли правилен мой алгоритм?
Не очень нравится мне, что рандомов надо запрашивать N (без мелочи). Результат-то требует всего k случайностей.

Добавлено через 33 минуты
Да, совсем забыл, а это весьма существенно. После указанного в псевдокоде заполнения массив a подвергается тасованию Дуршенфильда. А без этого, конечно, ерунда получается.

Байт · 05.02.2020, 12:07 **[ТС]**

По сути дело сводится вот к чему. Есть уравнение в целых числах
X₁ + ,,,+ X_k+1 = N, X_i > 0
Количество решений таких уравнений известно M = $https://www.cyberforum.ru/cgi-bin/latex.cgi?C_{N-1}^k$
И надо выбрать случайное число Z из диапазона [1, M]. А по этому Z восстановить решение. То есть надо все эти решения как-то перенумеровать.
То, что число M может оказаться достаточно большим (не влезет в привычные типы) не является, имхо, серьезным препятствием.

Добавлено через 10 минут
На этом пути появилась любопытная идейка. А нельзя ли генерировать случайные перестановки вообще без всякого перемешивания?
тасование Фишера-Дуршенфильда. имеет сложность O(k). А тут дело пахнет O(1).
Перестановки перенумеровать, используя факториальную систему счисления.
Выбрать случайное число S в диапазоне [1, k!]. И по этому номеру восстановить перестановку.
Надо подумать. Уж больно все просто получается...

Добавлено через 31 минуту
Увы! Революции не случилось. (Может, оно и к лучшему

) Перевод числа в перестановку требует вычеркивания чисел из исходного набора. И таких вычеркиваний - k. Оценка O(k) остается.
Вот, нашел разговор 8-ми летней давности (что такое 8 лет для вечности!

)
Какое слово идет под номером 8798 в лексикографичекском порядке?

Но актуальности первой части поста это не снимает.

Байт · 05.02.2020, 18:28 **[ТС]**

Сообщение от Байт

А по этому Z восстановить решение. То есть надо все эти решения как-то перенумеровать.

Свет не без добрых людей
Нумерация сочетаний
Благодаря уважаемому jogano задачу можно решать решенной.

@Astra Makasheva · 10.02.2020, 08:30

Всем привет! Интересное решение, надо попробовать,) kstu

@Shamil1 · 12.02.2020, 16:42

Сообщение от Байт

Нумерация сочетаний

Я немного запутался.
По ссылке речь идёт о нумерации сочетаний. В этой теме, судя по тому, что при k = N требуется тасование, порядок имеет значение. Если так, то (вроде) проще пронумеровать размещения, чем нумеровать сочетания, а потом выбранное сочетание тасовать.

Сообщение от Байт

Если больше не намного, можно создать массив a[N], применить к нему k раз вышеприведенный алгоритм и успокоиться.

Не надо тасовать k раз. Тасуем один раз и берём первые k элементов.

Байт · 12.02.2020, 18:04 **[ТС]**

Сообщение от Shamil1

Не надо тасовать k раз.

Я имел в виду шаги алгоритма. То есть, не надо весь массив N тасовать. Делаем только k шагов (рандом, обмен). Остальные N-k нас не интересуют.

@ant-ares · 18.05.2020, 23:01

возможно я не уловил смысла вашей темы, но видимо речь идет о методах шифрования
в природе есть примеры иррациональных значений (например 2^1/2, 3^1/2, число Пи, основание натурального логарифма) обратите внимание на методы их точных вычислений; как мы знаем, это бесконечные непериодические десятичные дроби, позиция и значащая цифра в ней комбинация неповторяемая, но точно вычисляемая

Добавлено через 30 минут
еще могу посоветовать обратить внимание на методы комбинаторики, но думаю с этого вы начали в первую очередь

Байт · 18.05.2020, 23:06 **[ТС]**

Сообщение от ant-ares

видимо речь идет о методах шифрования

Ни в коем случае. Чистая комбинаторика, и ничего больше.

@Le69uS · 19.05.2020, 09:44

Сообщение от Байт

Как будто и случайность, и неповторяемость обеспечены.

Не понял почему неповторяемость обеспечена? Может поподробнее прокомментируете код?

Байт · 19.05.2020, 10:49 **[ТС]**

Сообщение от Le69uS

почему неповторяемость обеспечена?

Я же генерирую не сами числа, а расстояния между ними. Которые всегда больше нуля.

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	05.02.2020, 12:07 [ТС]	2
	По сути дело сводится вот к чему. Есть уравнение в целых числах X₁ + ,,,+ X_k+1 = N, X_i > 0 Количество решений таких уравнений известно M = $https://www.cyberforum.ru/cgi-bin/latex.cgi?C_{N-1}^k$ И надо выбрать случайное число Z из диапазона [1, M]. А по этому Z восстановить решение. То есть надо все эти решения как-то перенумеровать. То, что число M может оказаться достаточно большим (не влезет в привычные типы) не является, имхо, серьезным препятствием. Добавлено через 10 минут На этом пути появилась любопытная идейка. А нельзя ли генерировать случайные перестановки вообще без всякого перемешивания? тасование Фишера-Дуршенфильда. имеет сложность O(k). А тут дело пахнет O(1). Перестановки перенумеровать, используя факториальную систему счисления. Выбрать случайное число S в диапазоне [1, k!]. И по этому номеру восстановить перестановку. Надо подумать. Уж больно все просто получается... Добавлено через 31 минуту Увы! Революции не случилось. (Может, оно и к лучшему) Перевод числа в перестановку требует вычеркивания чисел из исходного набора. И таких вычеркиваний - k. Оценка O(k) остается. Вот, нашел разговор 8-ми летней давности (что такое 8 лет для вечности!) Какое слово идет под номером 8798 в лексикографичекском порядке? Но актуальности первой части поста это не снимает. 0

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	05.02.2020, 18:28 [ТС]	3
	Сообщение от Байт А по этому Z восстановить решение. То есть надо все эти решения как-то перенумеровать. Свет не без добрых людей Нумерация сочетаний Благодаря уважаемому jogano задачу можно решать решенной. 0

@Astra Makasheva 0 / 0 / 0 Регистрация: 10.02.2020 Сообщений: 1
	10.02.2020, 08:30	4
	Всем привет! Интересное решение, надо попробовать,) kstu 0

@Shamil1 Модератор 3051 / 2193 / 459 Регистрация: 26.03.2015 Сообщений: 8,470
	12.02.2020, 16:42	5
	Сообщение от Байт Нумерация сочетаний Я немного запутался. По ссылке речь идёт о нумерации сочетаний. В этой теме, судя по тому, что при k = N требуется тасование, порядок имеет значение. Если так, то (вроде) проще пронумеровать размещения, чем нумеровать сочетания, а потом выбранное сочетание тасовать. Сообщение от Байт Если больше не намного, можно создать массив a[N], применить к нему k раз вышеприведенный алгоритм и успокоиться. Не надо тасовать k раз. Тасуем один раз и берём первые k элементов. 1

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	12.02.2020, 18:04 [ТС]	6
	Сообщение от Shamil1 Не надо тасовать k раз. Я имел в виду шаги алгоритма. То есть, не надо весь массив N тасовать. Делаем только k шагов (рандом, обмен). Остальные N-k нас не интересуют. 1

@ant-ares 18 / 9 / 4 Регистрация: 22.04.2016 Сообщений: 296
	18.05.2020, 23:01	7
	возможно я не уловил смысла вашей темы, но видимо речь идет о методах шифрования в природе есть примеры иррациональных значений (например 2^1/2, 3^1/2, число Пи, основание натурального логарифма) обратите внимание на методы их точных вычислений; как мы знаем, это бесконечные непериодические десятичные дроби, позиция и значащая цифра в ней комбинация неповторяемая, но точно вычисляемая Добавлено через 30 минут еще могу посоветовать обратить внимание на методы комбинаторики, но думаю с этого вы начали в первую очередь 0

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	18.05.2020, 23:06 [ТС]	8
	Сообщение от ant-ares видимо речь идет о методах шифрования Ни в коем случае. Чистая комбинаторика, и ничего больше. 0

@Le69uS 8 / 8 / 3 Регистрация: 04.12.2014 Сообщений: 49
	19.05.2020, 09:44	9
	Сообщение от Байт Как будто и случайность, и неповторяемость обеспечены. Не понял почему неповторяемость обеспечена? Может поподробнее прокомментируете код? 0

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	19.05.2020, 10:49 [ТС]	10
	Сообщение от Le69uS почему неповторяемость обеспечена? Я же генерирую не сами числа, а расстояния между ними. Которые всегда больше нуля. 0