Кто встречался, может знает как называется алгоритм?
Смысл такой:
Для определенного количества 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 различаются?
Может ли быть так, что какая-то "перестановка" пропускается? 

Если речь идет о размещениях, то алгоритм подсчета номера размещения несколько иной и, к сожалению, гораздо более длинный... если окажется что речь о нем, опишу, а просто так барабанить пальцев жалко... 

nworm, 123 и 321 и 132 и 123... это одно и тоже, для них всех должен быть один номер N.
Akina, если все это называется размещением, то напиши пожалуйста.     

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

А это вообще сочетания, а не размещения. 

Хорошо, а второй вопрос:
Может ли быть так, что какая-то "перестановка" пропускается?  

 

нет любая перестановка должна быть, хотя бы для определенного количества k = 1..5. 

То есть может быть
"перестановка"=12345 k=53
и одноверменно
"перестановка"=12345 k=55?
Если так, то задача недостаточно формализована или я ещё её не понял (хорошо тогда ещё какие-то пояснения улышать).
 

nworm, нет не может быть для 1,2,3,4,5 разные k. 
Для всех k  1,2,3,4,5 - 1,3,2,4,5 и т.д. k =35 (к примеру).
Т.е. поясню
1    2    3    4    k
*                1
    *            2
        *        3
            *    4
*    *            5
*        *        6
*            *    7
    *    *        8
    *        *    9
        *    *    10
*    *    *        11
    *    *    *    12
*    *        *    13
*        *    *    14
Какая бы ни была перестановка для k=5 ({1,2},{2,1}), k=5;
Если для 2-х чисел я могу придумать какой-нибудь горе алгоритм, то для 3-х и далее никак в голову ничего не приходит.  


  

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

Присоединённый файл ( Кол-во скачиваний: 5 )
 vin.gif 2,13 Kb

Чего-то я нашёл, но надо протестировать на своих значениях.
http://forum.cgm.ru/tree?th=1011&mid=6...ev=&reveal=
Сам я это всё не проверял. 

javas, я могу предложить придуманный мною алгоритм перестановки 4х символов.   
К сожалению, исходник на СИ не сохранился. Но зато на бумажке остался алгоритм.   
Если к моему алгоритму применить рекурсию, то можно осуществлять перестановки > 4х символов.

Я поставил себе цель придумать алгоритм перестановки 4х символов.
С помощью которого можно было бы переставлять в дальнейшем любое количество символов.
Так же чтобы не было повторящихся комбинайций.

Для 2х и 3х символов не составило особого труда придумать алгоритм.
Но к сожалению, они все не подходили для перестановки > 3х символов.

Поломав голову ~2 недели, мне все таки удалось придумать свой алгоритм перестановки 4х символов.
Потом в интернете я нашел несколько алгоритмов. Что подтверждает мою любимую фразу:
"Что есть как минимум 2 способа решения проблемы/задачи или выхода из ситуации..."

В дальнейшем я хотел с помощью рекурсии расширить кругозор своего алгоритма.
Чтобы можно было осуществлять перестановки > 4х символов. С рекурсиями пока не дружу.   

Была мысль перестановки > 4х символов с определенным количеством соимволов в одной комбинации.
Ранний пример, есть 4 символа. И нужно произвести перебор так, чтобы в одной комбинации было 4 символа. Что я уже собственно и зделал.
А теперь, есть 7 символов, но нужно чтобы в одной комбинации было 4 символа.
Данную мысль пока не реализовываю. Потому-что нужно разобраться с рекурсией.

Без рекурсий будет просто не реально. Потому-что очень большая вложенность циклов.   
А так же количество символов в комбинации будет фиксировано.

Таким образом я хочу чтобы можно было задавать любое число как в количестве символов, так и
в количестве символов в одной комбинации.

Моим алгоритмом можно осуществлять перестановку больше 2х символов. Проверял для 3,4 и 5.
Дальше как-то лениво было. Хотелось по быстрее разобраться с рекурсией   


Aloha, а я когда решал свою задачу, думал, что число перестановок равно n! (факториал)
Следовательно, 4!=1*2*3*4=24 комбинациям. Я в ручную перебрал все комбинации для 4х символов.
И как не странно их оказалось 24   


javas, вы мой друг как-то странно скачите от одной задачи к другой. С начала сообщается,
что нужен алгоритм перестановки всех возможных комбинаций, а потом вдруг нужен алгоритм
всех возможных сочитаний.

Поясню.
1) Перестановки. Есть 1,2,3. Может быть 123, 321, 213 и так далее.
Комбинации могут быть состоящии только из 3х цифр.
2) Сочитания. Есть 1,2,3. Может быть 1, 3, 31, 12, 23 и т.д.
Комбинации начинаются с одной цифры и т.д.

Я придумал алгоритм для перестановки всех возможных комбинаций. Не важно цифра или буква. 

Присоединённый файл ( Кол-во скачиваний: 4 )
 alg.gif 4,35 Kb

Кнером
В исходном топике javas использовал термин перестановка, хотя по смыслу поста речь шла о сочетаниях (ну использовал и использовал, смысл задачи от этого не изменился).
Число сочетаний из k элементов по N равно с(k,N)=N!/((N-k)!k!) (на это указал nworm). Далее, если у нас есть последовательность из N уникальных элементов, то по условию задачи мы должны перебрать все сочетания из 1 элемента, 2 элементов и т.д. (такие пары, как, например {a,b} и {b,a} считаются неразличимыми, собственно, поэтому речь и идет о сочетаниях, а не о перестановках).
Общее число сочетаний, очевидно равно:
M = с(1,N) + с(2,N) + ... + с(N,N)
С другой стороны известно, что
с(0,N) + с(1,N) + ... + с(N,N) = 2^N
а так как с(0,N) = 1, то
M = 2^N - 1.

Это конечно здорово, но, по-видимому, вы различали комбинации типа 321 и 123. А нужно ли это было делать или нет – конечное слово за javas. Ведь он "заказчик".   

Это сообщение отредактировал(а) Aloha - 2.6.2006, 03:54

nworm,  все отлично, спасибо.