k = 0;
для i от 0 до факториал( n )[INDENT]обменять_местами( a[k], a[(k+1) mod n] );
k = (k+1) mod n;
[/INDENT]
Алгоритм перестановки элементов множества
Здравствуйте!
Возникла необходимость получить все возможные варианты от перестановки некоторого числа элементов. Например, кол-во всех возможных вариантов от перестановки 5 элементов это 5! (факториал пяти). Есть ли алгоритмы с помощью которых можно получить все возможные варианты перестановки ?
Возникла необходимость получить все возможные варианты от перестановки некоторого числа элементов. Например, кол-во всех возможных вариантов от перестановки 5 элементов это 5! (факториал пяти). Есть ли алгоритмы с помощью которых можно получить все возможные варианты перестановки ?
Если я не ошибаюсь, факториал 5! это 120
по-моему, это не так уж проблематично..
Да, всего 120 возможных вариантов перестановки 5 элементов, но возможно ли с помощью некоего алгоритма получить все возможные варианты перестановки ?
Хм, даж не знаю. У вас как с программированием, писали уже знаменитую программу "Hello world", иначе я думаю вам не помогут мои рассуждения на тему как умножить 5*4*3*2*1 с помошью нескольких переменных
#include <stdio.h>
int main(void){
int a=5,b=1;
while(a>1){
b=b*a;
a--;
}
printf ("Hello world: %d",b);
return 1;
}
Цитата:
#include <stdio.h>
int main(void){
int a=5,b=1;
while(a>1){
b=b*a;
a--;
}
printf ("Hello world: %d",b);
return 1;
}
2palevo060 читай внимательней задачу..
нужно НЕ 5! посчитать. а отобразить все перестановки 5 елементов.. т.е.
12345
12354
12543
......
нужно НЕ 5! посчитать. а отобразить все перестановки 5 елементов.. т.е.
12345
12354
12543
......
Вы меня не понимаете)
Возьмем а, б, в - это 3 символа, 3! = 6
Вот все возможные варианты
a б в
а в б
б в a
б a в
в а б
в б а
Но вот если элементов 5 это уже становится проблемой
Вы поняли мою мысль ?
Возьмем а, б, в - это 3 символа, 3! = 6
Вот все возможные варианты
a б в
а в б
б в a
б a в
в а б
в б а
Но вот если элементов 5 это уже становится проблемой
Вы поняли мою мысль ?
O_O опс... извиняюсь :o
Цитата:
Вы поняли мою мысль ?
теперь да :D
хм.. литр пива мешает думать. но все же попробую.. Ограничиваемся пока максимум 9тью символами
1. Давай для начала возьмем исключительно цифры, тут как-бы все просто. Берем максимальную цифру и на чинаем перебор от 0 до (max+1)*10^max. Получая очередное число смотрим присутсвуют ли внем все наши цифры что надо елси да - вариант нашей перестановки.
2. Нужно оптимизировать. так как цифр у нас(например 5), то перебо нужен начинать с 10000. Допускаем, что цифры - 0 у нас нету. Например если цифры 12345, то перебираем от 10000 до 60000.
3. С цифрами все ясно. Теперь возьмом любые символы. Например а б в г д Строим соответсвие. 1 - а, 2 - б, 3 - в, 4 -г, 5 - д. Выполняя Переьор с п.2 и заменяя цифру на соответсвующий символ можем получить все персетановки.
Как конкретно реализовывать уже зависит от языка.. Думаю идея понятна.. Хотя она совсем не оптимальна. Просто мозг отказывается думать
1. Давай для начала возьмем исключительно цифры, тут как-бы все просто. Берем максимальную цифру и на чинаем перебор от 0 до (max+1)*10^max. Получая очередное число смотрим присутсвуют ли внем все наши цифры что надо елси да - вариант нашей перестановки.
2. Нужно оптимизировать. так как цифр у нас(например 5), то перебо нужен начинать с 10000. Допускаем, что цифры - 0 у нас нету. Например если цифры 12345, то перебираем от 10000 до 60000.
3. С цифрами все ясно. Теперь возьмом любые символы. Например а б в г д Строим соответсвие. 1 - а, 2 - б, 3 - в, 4 -г, 5 - д. Выполняя Переьор с п.2 и заменяя цифру на соответсвующий символ можем получить все персетановки.
Как конкретно реализовывать уже зависит от языка.. Думаю идея понятна.. Хотя она совсем не оптимальна. Просто мозг отказывается думать
Хм, я без литров, но мучаюсь на проектиком, так что мозг тож не хочет думать, но вот что я уменя надумалось, попробую объяснить.
берем буквы.
а б в с
теперь меняем букву (а) с соседней и получается
б [COLOR="Red"]а[/COLOR] в с
теперь снова меняем букву (а) с соседней и получается
б в [COLOR="Red"]а[/COLOR] с
теперь снова меняем букву (а) с соседней и получается
б в с [COLOR="Red"]а[/COLOR]
теперь меняем букву (б) с соседней и получается
в [COLOR="Red"]б[/COLOR] с а
теперь снова меняем букву (б) с соседней и получается
в с [COLOR="Red"]б[/COLOR] а
в с а [COLOR="Red"]б[/COLOR]
с [COLOR="Red"]в[/COLOR] а б
с а [COLOR="Red"]в[/COLOR] б
с а б [COLOR="Red"]в[/COLOR]
а [COLOR="Red"]с[/COLOR] б в
а б [COLOR="Red"]с[/COLOR] в
берем буквы.
Цитата:
а б в с
теперь меняем букву (а) с соседней и получается
б [COLOR="Red"]а[/COLOR] в с
теперь снова меняем букву (а) с соседней и получается
б в [COLOR="Red"]а[/COLOR] с
теперь снова меняем букву (а) с соседней и получается
б в с [COLOR="Red"]а[/COLOR]
теперь меняем букву (б) с соседней и получается
в [COLOR="Red"]б[/COLOR] с а
теперь снова меняем букву (б) с соседней и получается
в с [COLOR="Red"]б[/COLOR] а
в с а [COLOR="Red"]б[/COLOR]
с [COLOR="Red"]в[/COLOR] а б
с а [COLOR="Red"]в[/COLOR] б
с а б [COLOR="Red"]в[/COLOR]
а [COLOR="Red"]с[/COLOR] б в
а б [COLOR="Red"]с[/COLOR] в
и так далее. У меня на листке получилось 12 вариантоф
Точно не уверен, но насколько помню - делалось это циклической перестановкой элементов.
Имеем n элементов в массиве a (нумерация с нуля). Алгоритм напишу на абстрактном псевдоязыке:
Думаю, тут всё должно быть понятно. Единственное - операция mod n - это остаток от деления на n (в паскале так и будет mod, в сях это оператор %).
Имеем n элементов в массиве a (нумерация с нуля). Алгоритм напишу на абстрактном псевдоязыке:
Код:
Думаю, тут всё должно быть понятно. Единственное - операция mod n - это остаток от деления на n (в паскале так и будет mod, в сях это оператор %).
Вот здесь обсуждался такой же вопрос: forum.codenet.ru/showthread.php?p=214469#post214469
Большое спасибо за ответы и ссылки! :)