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

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,  все отлично, спасибо.