Кто встречался, может знает как называется алгоритм?
Смысл такой:
Для определенного количества k находится перестановка всех чисел от 1 до k, нужно получить номер, зная строчку k (т.е. зная 1,2 возвращается 4,  1,2,3 - 7).
к может быть любым.
Вход: k, перестановка от 1 до k чисел
Выход: номер
Необходимо реализовать такую функцию.
номер/k
1    1
2    2
3    3
4    1,2
5    1,3
6    2,3
7    1,2,3
Вообщем, если кто знает как сделать please help. 

Число сочетаний из k элементов по n равно с(k,n)=k!/((k-n)!k!)
Пример k=3
3 перестановки из одного элемента
3 перестановки из двух элементов
1 перестановка из одного элемента

Поэтому можно так делать алгоритм:
1) просуммировать с(k,1)+c(k,2)+c(k,3)+...+c(k,<число элементов в введённой перестановке - 1>)
2) прибавить к полученной сумме номер введённой перестановки среди перестановок из <число элементов в введённой перестановке> элементов 

nworm, а номер введённой перестановки среди перестановок из <число элементов в введённой перестановке> искать как перебором лучше? 

Это сообщение отредактировал(а) javas - 31.5.2006, 00:14

javas
У меня получился такой алгоритм (сразу оговорюсь, он возвращает несколько иные результаты).
Возьмем, например, последовательность 1,2,3. Будем считать, что каждому числу в последовательности соответствует значимый бит, причем номер бита и определяется самим числом в последовательности.
Короче говоря, для последовательности 1,2,3 получим 0111 (биты нумеруем справа налево). А, например, для последовательности 2,3 получим 0110 (раз единица отсутствует в последовательности, значит первый бит = 0). Остается перейти к десятичной записи:

1       0001    1
 2      0010    2
12      0011    3
  3     0100    4
1 3     0101    5
 23     0110    6
123     0111    7
   4    1000    8
1  4    1001    9
 2 4    1010    10
12 4    1011    11
  34    1100    12
1 34    1101    13
 234    1110    14
1234    1111    15

 

Aloha,  судя по твоему алгоритму, если на входе 
1,2 - на выходе 2^0+2^1 = 3;
1,2,3,4 ->    2^0+2^1+2^2+2^3 = 16
100,5 ->  2^99 + 2^4 =  633825300114114700748351602688 +16
По-моему, ты гений. 

осталось добавить что это производится в системе счисления с основанием k 

Алгоритм, предложенный Aloha ничего, но оказывается не то, куча ненужных перестановок, если мне нужно значени 100000, 10 ->сложновато, там хранятся перестановки типа 1,2,3,....99999 - этого не тот все таки порядок, nworm  правильно предложил, но как эффективно найти номер введённой перестановки среди перестановок из <число элементов в введённой перестановке>  

Это сообщение отредактировал(а) javas - 31.5.2006, 09:50

Объясню наглядно.
Дано: числа от 1 до 100 000
нужно найти номер перестановки 2, 3000, 60000, 3 - порядок не важен, главное, чтобы это была уникальная комбинация

Нам известы комбинации для чисел от 1 до 3 - это радует.

С(100 000, 1) + С(100 000,2) + С(100 000,3) = 100 000 + (10^5)!/2!/(10^5-2)! +(10^5)!/3!/(10^5-3)!
Все остальные комбинации для 4 нужно искать, причем порядок неважен, главное, чтобы было понятно, что все комбинации переберутся. 

javas, я же тебе сказал что именно надо учитывать для получения ПРАВИЛЬНОГО номера. 
 

Akina, Объясни наглядо, я не понял. 

javas
Алгоритм, о котором идет речь, должен удовлетворять как минимум одному условию. А именно, соответствие между перестановкой и ее номером должно быть взаимнооднозначным. В противном случае теряется всякий смысл такого алгоритма. Еще неплохо было бы иметь возможность обратного преобразования для данного алгоритма. Число перестановок из k элементов (по рассматриваемой схеме) равно (2^k) - 1. Например, для чисел 1,2,3,4 число перестановок равно 15, а для чисел от 1 до 100 000 их будет (2^100 000) - 1.  И мне кажется, от этого никуда не деться (в противном случае соответствие уже не будет взаимнооднозначным). Может добавите какие-нибудь дополнительные подробности к задаче. Вдруг это поможет размышлениям.
 

Прошу прощения, не понял, что здесь называют перестановками.
Как понимать "перестановка 1,3 среди k элементов"?
Обычно, под перестановками понимают упорядоченные последовательности из _всех_ элементов множества, поэтому их k! (факториал). Я знаю два способа записи перестановок, но ни один из них не соответствует, тому, что здесь вижу. 

Канечно нужна взаимооднозначность, в твоем алгоритме она есть, но суть алгоритма в том, что количество комбинаций k(1,3,8,5) = 4 намного меньше N (числа 1,2,3.....10000) = 10 000. Т.е., k имет определенную разумную грань, не нужно перебирать весь объем множества.
Например k = 1..5 вообщем небольшое количество, т.е. будет перебираться количество чисел от 1 числа до 5 чисел. 
для чисел 1,2,3,4б5.
1
2
3
4
5
12
13
14
15
...
123
{над комбинациеей перебора либо как у тебя нужно подумать, главное, чтобы не было повторов}
124
125
...
Т.е. одназначность нужна, хотя бы для малых k, чтобы номер был не безбашенным.

Добавлено @ 11:19 
nostromo,  называй как хочешь, пусть будут комбинации без повторов.

Добавлено @ 11:32 
Aloha, зная комбинацию, нужно получить номер, но зная номер нет необходимости получать комбинацию.
1    1
2    2
3    3
4    1,2
5    1,3
6    2,3
7    1,2,3

зная 1,2 -> N=4, но не нужно, зная N=4 получить 1,2 

А, это упорядоченные подмножества, или "размещения".
Тогда Akina ошибся, и их не 2^k (число всех подмножеств), а гораздо меньше (кажется, красивой замкнутой формулы нет). 

Я немного ошибся
с(k,n)=k!/((k-n)!n!).
А по задаче вопрос:
"перестановки" 123 и 321 различаются?
Может ли быть так, что какая-то "перестановка" пропускается?