Akina, если все это называется размещением, то напиши пожалуйста.
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Получение номера перестановки |
| Автор: javas 30.5.2006, 22:50 |
| Кто встречался, может знает как называется алгоритм? Смысл такой: Для определенного количества 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. |
| Автор: nworm 30.5.2006, 23:50 |
| Число сочетаний из 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) прибавить к полученной сумме номер введённой перестановки среди перестановок из <число элементов в введённой перестановке> элементов |
| Автор: javas 30.5.2006, 23:54 |
| nworm, а номер введённой перестановки среди перестановок из <число элементов в введённой перестановке> искать как перебором лучше? |
| Автор: Aloha 31.5.2006, 00:15 |
| 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 |
| Автор: javas 31.5.2006, 00:45 |
| 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 По-моему, ты гений. |
| Автор: Akina 31.5.2006, 09:34 |
| осталось добавить что это производится в системе счисления с основанием k |
| Автор: javas 31.5.2006, 09:49 |
| Алгоритм, предложенный Aloha ничего, но оказывается не то, куча ненужных перестановок, если мне нужно значени 100000, 10 ->сложновато, там хранятся перестановки типа 1,2,3,....99999 - этого не тот все таки порядок, nworm правильно предложил, но как эффективно найти номер введённой перестановки среди перестановок из <число элементов в введённой перестановке> |
| Автор: javas 31.5.2006, 10:25 |
| Объясню наглядно. Дано: числа от 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 нужно искать, причем порядок неважен, главное, чтобы было понятно, что все комбинации переберутся. |
| Автор: Akina 31.5.2006, 10:36 |
| javas, я же тебе сказал что именно надо учитывать для получения ПРАВИЛЬНОГО номера. |
| Автор: javas 31.5.2006, 10:41 |
| Akina, Объясни наглядо, я не понял. |
| Автор: Aloha 31.5.2006, 11:01 |
| javas Алгоритм, о котором идет речь, должен удовлетворять как минимум одному условию. А именно, соответствие между перестановкой и ее номером должно быть взаимнооднозначным. В противном случае теряется всякий смысл такого алгоритма. Еще неплохо было бы иметь возможность обратного преобразования для данного алгоритма. Число перестановок из k элементов (по рассматриваемой схеме) равно (2^k) - 1. Например, для чисел 1,2,3,4 число перестановок равно 15, а для чисел от 1 до 100 000 их будет (2^100 000) - 1. И мне кажется, от этого никуда не деться (в противном случае соответствие уже не будет взаимнооднозначным). Может добавите какие-нибудь дополнительные подробности к задаче. Вдруг это поможет размышлениям. |
| Автор: nostromo 31.5.2006, 11:12 |
| Прошу прощения, не понял, что здесь называют перестановками. Как понимать "перестановка 1,3 среди k элементов"? Обычно, под перестановками понимают упорядоченные последовательности из _всех_ элементов множества, поэтому их k! (факториал). Я знаю два способа записи перестановок, но ни один из них не соответствует, тому, что здесь вижу. |
| Автор: javas 31.5.2006, 11:18 |
| Канечно нужна взаимооднозначность, в твоем алгоритме она есть, но суть алгоритма в том, что количество комбинаций 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 |
| Автор: nostromo 31.5.2006, 11:58 | ||
А, это упорядоченные подмножества, или "размещения". Тогда Akina ошибся, и их не 2^k (число всех подмножеств), а гораздо меньше (кажется, красивой замкнутой формулы нет). |
| Автор: nworm 31.5.2006, 12:09 |
| Я немного ошибся с(k,n)=k!/((k-n)!n!). А по задаче вопрос: "перестановки" 123 и 321 различаются? Может ли быть так, что какая-то "перестановка" пропускается? |
| Автор: Akina 31.5.2006, 14:42 |
| Если речь идет о размещениях, то алгоритм подсчета номера размещения несколько иной и, к сожалению, гораздо более длинный... если окажется что речь о нем, опишу, а просто так барабанить пальцев жалко... |
| Автор: javas 31.5.2006, 15:44 |
| nworm, 123 и 321 и 132 и 123... это одно и тоже, для них всех должен быть один номер N. Akina, если все это называется размещением, то напиши пожалуйста. |
| Автор: Akina 31.5.2006, 17:42 | ||
А это вообще сочетания, а не размещения. |
| Автор: nworm 31.5.2006, 21:29 |
| Хорошо, а второй вопрос: Может ли быть так, что какая-то "перестановка" пропускается? |
| Автор: javas 31.5.2006, 21:43 |
| нет любая перестановка должна быть, хотя бы для определенного количества k = 1..5. |
| Автор: nworm 31.5.2006, 23:31 | ||
То есть может быть "перестановка"=12345 k=53 и одноверменно "перестановка"=12345 k=55? Если так, то задача недостаточно формализована или я ещё её не понял (хорошо тогда ещё какие-то пояснения улышать). |
| Автор: javas 1.6.2006, 00:21 |
| 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-х и далее никак в голову ничего не приходит.  |
| Автор: nworm 1.6.2006, 09:59 |
| Чего-то я нашёл, но надо протестировать на своих значениях. http://forum.cgm.ru/tree?th=1011&mid=6934&&rev=&reveal= Сам я это всё не проверял. |
| Автор: Кнером 2.6.2006, 02:51 | ||||||
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 и т.д. Комбинации начинаются с одной цифры и т.д. Я придумал алгоритм для перестановки всех возможных комбинаций. Не важно цифра или буква. |
| Автор: Aloha 2.6.2006, 03:49 | ||
| Кнером В исходном топике 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. Ведь он "заказчик". |
| Автор: javas 2.6.2006, 16:06 |
| nworm, все отлично, спасибо. |
