| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Перестановки |
| Автор: Sheff 7.11.2002, 09:04 |
| Люди добрые, нужно вывести юзеру все варианты перестановок элементов массива. Например если массив такой: 0,1,2 Прога выводит: 0,1,2 0,2,1 1,0,2 1,2,0 2,1,0 2,0,1 Таких выводов будет (к-во эл. в массиве)!(факториал) Знаю, чайнический вопрос, но что-то не выходит ничего. У кого какие идеи, мне кажется тут рекурсией надо работать, но вот как ... |
| Автор: neutrino 7.11.2002, 18:25 |
| Тема обсуждалась: http://www.forum.vingrad.ru/cgi-bin/newforum/ikonboard.cgi?act=ST;f=13;t=709 П.С. Если у тебя будет массив н-ой длины. Его надо взять в порядке убывания. Потом воспользоваться "пузырьковой" сортировкой (в порядке возрaстания) и на каждом шагу сортировки распечатывать массив. |
| Автор: Sheff 13.11.2002, 02:16 | ||
Хм, попробовал, от не выдаёт всё перестановки, тока часть  |
| Автор: neutrino 14.11.2002, 03:25 |
| Да, и правда не выходит. Я ошибался. Можно воспользоваться таким алгоритмом: Я думаю ты знаешь что такое ротация. Но, конечно если ее реализовать такую, какая она есть для массива, это будет не очень эффективно. Так создай в памяти два одинаковых массива, чтобы они физически были расположены один за другим (12341234). Если ты будешь давать адрес на m больший чем адрес начала (первого элемента) массива, и будешь читать то же количество элементов, то получишь ротацию на m элементов. Далее ты делаешь ротацию n-1 (n-длина массива) раз всего массива, и на каждой ротации вызываешь рекурсивно еще раз эту же процедуру ротации, только со второго (третьего, четвертого и т.д. в следуюших шагах рекурсии) элемента и на один элемент меньше чем на предыдушем шаге рекурсии. Это должно работать. По крайней мере я проверил для массива из 3-х и 4-х элементов (на бумаге). Дома попробую написать прогу (буду писать на С, если хочешь на паскале, то дай знать на мыло, а лучше кинь SMS:+97255426544). P.F. Это можно и итеративно сделать. |
| Автор: Sheff 14.11.2002, 04:07 |
| К сожалению я не знаю, что такое ротация, но я вот знаю, что перестановки можно реализовать рекурсией, но вот как именно ? |
| Автор: neutrino 14.11.2002, 18:18 |
| Ротация это вот что: А={1,2,3,4} ротация на 2 элемента влево: А={3,4,1,2} (Аналог в АСМ работает с битами в числе ROR и ROL) Я предлагаю вместо того, чтобы переприсваивать элементы, сделать ротацию так: ты используешь на n-1 больше элементов и строишь неполную копию массива идущую сразу после массива. Короче говоря: А={1,2,3,4,1,2,3} //len(A)=n+n-1 Если тебе надо сделать ротацию на м элементов, ты читаешь н элементов с указателя (А+m): m=2; А+=m; А[0]=3; А[1]=4; А[2]=1; А[3]=2; Вот тебе и ротация!!! |
| Автор: neutrino 14.11.2002, 18:30 |
| Мой метод решения основывается на вышепредложенном алгоритме реализации ротации. Он не претендует на звание самого эффективного по временной сложности и количеству необходимой памяти алгоритма. Наверняка можно придумать что-нибудь побыстрее/меньше. Вооbще задачу надо представить как дерево: |А[1]=2|А[2]=3 |А[0]=1|А[1]=3|А[2]=2 | | |А[1]=2|А[2]=3 |А[0]=2|А[1]=3|А[2]=1 | | |А[1]=1|А[2]=2 |А[0]=3|А[1]=2|А[2]=1 Поэтому, как раз, и 3! вариантов (если ты перемножешь 3*2*1 - количество веток). |
| Автор: neutrino 14.11.2002, 19:43 |
| Это описание работы моего алгоритма (на примере массива {1,2,3,4}): на смом верхнем шаге рекурсии имеем: 1,2,3,4 "копируем" n-1 элементов: 1,2,3,4,1,2,3 пишем первый символ (1) передаем массив 2,3,4 на уровень ниже на втором уровне рекурсии имеем: 2,3,4 "копируем" элементы: 2,3,4,2,3 выводим первый символ (2) передаем массив 3,4 на уровень ниже на третьем уровне рекурсии имеем: 3,4 "копируем": 3,4,3 выводим первый символ (3) передаем массив 4 на уровень ниже на четвертом уровне имеем: 4 выводим (4) и #13, #10 переходим на уровень выше, т.к. цифр нет на третьем уровне делаем ротацию: 4,3 выводим первый символ (4) (вот тут надо выводить еще все цифры до этого, их надо запомнить в массив) передаем массив 3 на уровень ниже на четвертом уровне имеем: 3 выводим (3) и #13, #10 переходим на уровень выше, т.к. цифр нет на третьем уровне можно было сделать только одну ротацию, переходим на уровень выше на втором уровне делаем ротацию: 3,4,2 выводим первый элемент (3) передаем массив 3,4,2 на уровень ниже ............ ............ ............ и т.д. Думаю алгоритм понятен. |
| Автор: podval 14.11.2002, 22:59 |
| Хватит мучиться! http://algolist.manual.ru/maths/combinat/permutations.php Больше добавить нечего. |
| Автор: neutrino 15.11.2002, 00:18 | ||
2Podval: Во-первых, почему мучиться? Ведь если не решать самому такие задачи, ни к чему не придешь. Во-вторых:
Надо было развивать идею об упорядочивании, все таки... Хотя и мои алгоритм работает. И еще можно составить дерево. Только, по-моему сложновастенько получится. ;) |