Люди добрые, нужно вывести юзеру все варианты перестановок элементов массива. Например если массив такой:
0,1,2
Прога выводит:
0,1,2
0,2,1
1,0,2
1,2,0
2,1,0
2,0,1
Таких выводов будет (к-во эл. в массиве)!(факториал)
Знаю, чайнический вопрос, но что-то не выходит ничего.
У кого какие идеи, мне кажется тут рекурсией надо работать, но вот как ...

Тема обсуждалась: http://www.forum.vingrad.ru/cgi-bin....3;t=709

П.С. Если у тебя будет массив н-ой длины. Его надо взять в порядке убывания. Потом воспользоваться "пузырьковой" сортировкой (в порядке возрaстания) и на каждом шагу сортировки распечатывать массив.

Цитата(neutrino @ 07.11.2002, 10:25)

Тема обсуждалась: http://www.forum.vingrad.ru/cgi-bin....3;t=709 П.С. Если у тебя будет массив н-ой длины. Его надо взять в порядке убывания. Потом воспользоваться "пузырьковой" сортировкой (в порядке возрaстания) и на каждом шагу сортировки распечатывать массив.

Хм, попробовал, от не выдаёт всё перестановки, тока часть

Да, и правда не выходит. Я ошибался. Можно воспользоваться таким алгоритмом:
Я думаю ты знаешь что такое ротация. Но, конечно если ее реализовать такую, какая она есть для массива, это будет не очень эффективно. Так создай в памяти два одинаковых массива, чтобы они физически были расположены один за другим (12341234). Если ты будешь давать адрес на m больший чем адрес начала (первого элемента) массива, и будешь читать то же количество элементов, то получишь ротацию на m элементов. Далее ты делаешь ротацию n-1 (n-длина массива) раз всего массива, и на каждой ротации вызываешь рекурсивно еще раз эту же процедуру ротации, только со второго (третьего, четвертого и т.д. в следуюших шагах рекурсии) элемента и на один элемент меньше чем на предыдушем шаге рекурсии. Это должно работать. По крайней мере я проверил для массива из 3-х и 4-х элементов (на бумаге). Дома попробую написать прогу (буду писать на С, если хочешь на паскале, то дай знать на мыло, а лучше кинь SMS:+97255426544).
P.F. Это можно и итеративно сделать.

К сожалению я не знаю, что такое ротация, но я вот знаю, что перестановки можно реализовать рекурсией, но вот как именно ?

Ротация это вот что:
А={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;
Вот тебе и ротация!!!

Мой метод решения основывается на вышепредложенном алгоритме реализации ротации. Он не претендует на звание самого эффективного по временной сложности и количеству необходимой памяти алгоритма. Наверняка можно придумать что-нибудь побыстрее/меньше. Воо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 - количество веток).

Это описание работы моего алгоритма (на примере массива {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 на уровень ниже
............
............
............
и т.д.
Думаю алгоритм понятен.

Хватит мучиться!
http://algolist.manual.ru/maths/combinat/permutations.php
Больше добавить нечего.

2Podval: Во-первых, почему мучиться? Ведь если не решать самому такие задачи, ни к чему не придешь. Во-вторых:

Цитата

Мы должны найти наибольшее i, при котором это так, т.е. такое i, что X[i]<X[i+1]>...>X[N] (если такого i нет, то перестановка последняя). После этого X[i] нужно увеличить минимально возможным способом, т.е. найти среди X[i+1],...,X[N] наименьшее число, большее его. Поменяв X[i] с ним, остается расположить числа с номерами i+1,...,N так, чтобы перестановка была наименьшей, то есть в возрастающем порядке. Это облегчается тем, что они уже расположены в убывающем порядке:

Надо было развивать идею об упорядочивании, все таки... Хотя и мои алгоритм работает. И еще можно составить дерево. Только, по-моему сложновастенько получится. ;)