Любителям алгоритмов: как построить конструктивную биекцию между натуральными числами и наборами по k чисел из n?

Question

[0xC0CAC01A]

Имеются числа от 0 до n-1. Нужно пронумеровать все уникальные (с точностью до перестановки) наборы из них по k чиселб k<n. И получить с временной сложностью О(1) набор по номеру. Память тоже O(1).

Пример: n=6, k=4, наборов С(n,k)

0 -> 0123

1 -> 0124

2 -> 0125

3 -> 0134

3 -> 0135

4 -> 0145

5 -> 0234

6 -> 0235

7 -> 0245

8 -> 0345

9 -> 1234

10 -> 1235

11 -> 1245

12 -> 1345

13 -> 2345

Comments

[btd]

А время на построение нумерации учитывается?

[0xC0CAC01A]

Учитывается. Её строить не надо, она должна быть задана формулой. А то ведь n может быть и двадцатизначным числом.

[MikhailEdoshin]

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

Answer 1

[btd]

Мне кажется будет достаточно прибавлять 1 с использованием сложения по модулю n.

Answer 2

[asm0dey]

А в чем проблема создать свою имплементацию Map, у которой будет перепреоделен метод add(): число как строку, ее как charArray, дальше отсортировать и добавить.

Comments

[0xC0CAC01A]

Не наш метод. Как эта Map будет выглядеть при n=10^20?

[asm0dey]

Насколько я понимаю, избежать хоть какого-нибудь уровня обертки над массивом не получится…

[agmt]

Массив — сложность создания и не спортивно. Как я понял, большинство согласно, что O(1) ко времени не получится, а вот память надо бы экономить.

Answer 3

[qrazydraqon]

Сдаётся мне, получить O(1) не получится ни по n, ни по k. Потому что уже для получения первой цифры по номеру надо уметь определять, в каком из интервалов вида (f(n,k,x),g(n,k,x)] лежит этот номер, где f(n,k,x) = C(n-x-1,k-1), g(n,k,x) = f(n,k,x)+C(n-x-2,k-1). Быстро не вычислить.

Comments

[qrazydraqon]

Это, конечно, не доказывает невозможности соорудить быстро вычисляемое отображение, но даёт основания полагать, что оно будет очень замороченным (и, скорее всего, не с лексико-графическим упорядочением).

[0xC0CAC01A]

а упорядочения не надо

[qrazydraqon]

Под упорядочением имелось в виду искомое отображение, которые вводит порядок на наборах из k чисел.

[agmt]

Как-то так. А факториалы считать — долго. Хотя, думаю, выделить место под k чисел (для хранения всех C(n-x, k-x)) вполне реально. Впрочем, если можно было бы обойтись без перебора.

Answer 4

[MikhailEdoshin]

Есть готовые способы нумерации сочетаний, кстати. Множество сочетаний рекурсивно разбивается на части, мощность которых известна, номер формируется тоже рекурсивно. Подробно объяснить не могу, сам не понимаю :) Смотрю в Дискретный анализ Романовского, с. 50.

Comments

[MikhailEdoshin]

Т. е. «сходил в библиотеку, взял справочник по красным шарам» :)

[agmt]

Так qrazydraqon описал идею со сложностью O(n*k) при условии размещения в памяти вычисленных перестановок O(n*k): сначала последовательно выбирается первое число (перебором), затем второе уже при n=n-1, k=k-1 и т.д.

А идея основана на том (по крайней мере, я так вывел), что каждое число встречается ровно С(n-1,k-1) раз и до такого же номера соответствующий набор будет начинаться с нулевого элемента. В исходном примере каждое число встречается 5! / 2!3! = 10, т.е. 0..9 номера будут у наборов, начинающихся с «0». У следующих C(n-2,k-1) = 4! / 1!3! = 4 номеров первым числом будет «1». Ну и так далее по рекурсии.

А дальше, в зависимости от величин n и k можно либо хранить перестановки в памяти, либо нет.

[MikhailEdoshin]

Да, там по формуле примерно такая сложность и выходит.

Answer 5

[Mercury13]

Это делается динамическим программированием за сложность O(nk) по процессору и памяти.

Answer 6

[dansheb]

О НУМЕРАЦИИ ПЕРЕСТАНОВОК И СОЧЕТАНИЙ ДЛЯ ОРГАНИЗАЦ...