Для желающих напрячь мозги :)

Вот скоммуниздил с форума на "диком востоке" ,урл не скажу, т.к. там есть ответ на 1 вопрос, форум поисковиками не индексируется так что можете не искать где оно ;D

>Автор: **********(***.**.***.**) - **.**.**** (**:**)  


>Требуется (быстрый!) алгоритм, преобразующий размещение k элементов из множества
>n элементов в его порядковый номер. Частный случай k=5, n=32, напр.:
>1,2,3,4,5 = 1 1,2,3,4,6 = 2 .... 1,2,3,4,32 = 28 1,2,3,5,6 = 29 .... 28,29,30,31,32 = 201376

>типа function f(a:array[1..5]of byte):longint

>Также желателен обратный алгоритм. Желательно универсальный для всех k,n или в
>частности для k=5, n=32. Очень не хочется напрягать мозги :-) - и так куча работы.
>Может кто сталкивался или где-то есть информация по этому поводу?

от себя добавлю: 1,2,3,4,5 и 1,2,5,3,4 суть одно и тоже, обратный алгоритм существует, хотя и не очень быстрый, но намного быстрее чем перебор всех вариантов.

Цитата Zzzaraza, 06.04.02, 10:55:40

от себя добавлю: 1,2,3,4,5 и 1,2,5,3,4 суть одно и тоже, обратный алгоритм существует, хотя и не очень быстрый, но намного быстрее чем перебор всех вариантов.

Если "одно и то же", то это сочетания, а не размещения - предлагаю полиадическую систему счисления:
Основание системы (например, для предложенного варианта) : ( 32, 31, 30, 29, 28 )
1. Текущее сочетание упорядочивается по возрастанию;
2. Неиспользованные еще числа (вначале - от 1 до 32) нумеруются от 0;
3. Текущий разряд (вначале - младший) заполняется номером текущего числа
4. Если остались необработанные элементы сочетания - goto 2
Все! 8)
Доказательство корректности преобразования и разработку обратного алгоритма оставляю читателю в качестве домашнего задания.
Цветы в машину!

Сообщение отредактировано: volatile - 17.04.02, 21:51

Судя по количеству ответов, народ не очень сильно любит напрягать мозги :-)

2Faust: полиадическая система - это конечно интересно, возможно так оно и будет, но вот только основание никак не 32, 31, 30, 29, 28


>Судя по количеству ответов, народ не очень сильно любит напрягать мозги  

н-да, похоже на то, ладно тоды ответ на 1 вопрос:

дополнительно создаем матрицу S(k,n) сумм (одна для любых k и n)
   
/I    1    2    3    4    5    6 ... k
j
1     0    0    0    0    0    0
2     1    1    1    1    1    1    
3     1    2    3    4    5    6
4     1    3    6    10   15   21
5     1    4    10   20   35   56
.    
.
n-k   1    27   378  3654 27405 169911
n-k+1 1    28   406  4060 31465 201376

т.е. S(i,j)=S(i-1,j)+S(i,j-1)

дальше идут сами вычисления порядкового номера комбинации:

записываем, начиная с наибольшего,
например

i     1  2  3 4 5
M(i)  32 27 5 2 1

находим разницу между максимально допустимым значением I-того элемента и его значением

M(i)=n-k+M(i)-1

для k=5, n=32
I     1  2  3  4  5
M(i)  27 23 2  0  0

порядковый номер комбинации равен

//Э-ээ, математически писать долго, т.е. вообще не знаю как ,
//поэтому на васике:

num=1
for i=1 to k
for j=M(i) to 1 step –1
 num=num+S(i,j)
next j
next I

или так:
num=1
for I=1 to k
  num=num+S(i+1,n-k)-S(i+1,n-k-M(i))
next I

все просто до безобразия ;D

Цитата Zzzaraza, 30.04.02, 10:23:26

но вот только основание никак не 32, 31, 30, 29, 28

:oЭто почему же, позвольте Вас спросить? И не "32, 31, 30, 29, 28", а "( 32, 31, 30, 29, 28 )" - разница есть.
Кстати, приведенная тобой матрица - это треугольник Паскаля.
Судя по всему, сам ты мозгов не напрягал , а просто воспользовался чужими :

Сообщение отредактировано: volatile - 30.04.02, 08:44

> Это почему же, позвольте Вас спросить? И не "32, 31, 30, 29, 28", а "( 32, 31, 30, 29, 28 )" - разница есть.

О, sorry скобычки забыл поставить ;D

>Кстати, приведенная тобой матрица - это треугольник Паскаля.

случайное совпадение, адназначна ;D, я ж не виноват что родился позже Паскаля ;D, да и не треугольник у меня, а прямоугольник, и начинается с нуля. Вот!

>Судя по всему, сам ты мозгов не напрягал    , а просто воспользовался чужими  

Т-эээкс похоже обвинили в плагиате..., ну что тут скажешь...., да ради бога...... , найдешь похожее решение, ткни меня носом ;D ;D ;D ;D ;D ;D ;D ;D ;D ;D ;D ;D ;D ;D ;D ;D