|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Ruslan Shevelyov 2:5020/9481.21 21 May 2002 17:58:46
To : Alexandre Kotelkov
Subject : получить перестановки
--------------------------------------------------------------------------------
AK> е поaeскажет ли кто более-менее эффективный алгоритм получения всех
AK> возможных перестановок чисел от 1 aeо n?
Первый способ:
---------------- 'shen.txt' begins here ----------------
2.2.1. Hапечатать все перестановки чисел 1..n (то есть пос-
ледовательности длины n, в которые каждое из чисел 1..n входит
по одному разу).
Решение. Перестановки будем хранить в массиве x[1],...,
x[n] и печатать в лексикографическом порядке. (Первой при этом
будет перестановка <1 2...n>, последней - <n...2 1>.) Для сос-
тавления алгоритма перехода к следующей перестановке зададимся
вопросом: в каком случае k-ый член перестановки можно увеличить,
не меняя предыдущих? Ответ: если он меньше какого-либо из следу-
ющих членов (членов с номерами больше k). Мы должны найти на-
ибольшее k, при котором это так, т. е. такое k, что x[k] <
x[k+1] > ... > x[n]. После этого x[k] нужно увеличить мини-
мальным возможным способом, т. е. найти среди x[k+1], ..., x[n]
наименьшее число, большее его. Поменяв x[k] с ним, остается рас-
положить числа с номерами k+1, ..., n так, чтобы перестановка
была наименьшей, то есть в возрастающем порядке. Это облегчается
тем, что они уже расположены в убывающем порядке.
Алгоритм перехода к следующей перестановке.
{<x[1],...,x[n-1], x[n]> <> <n,...,2, 1>.}
k:=n-1;
{последовательность справа от k убывающая: x[k+1] >...> x[n]}
while x[k] > x[k+1] do begin
k:=k-1;
end;
{x[k] < x[k+1] > ... > x[n]}
t:=k+1;
{t <=n, x[k+1] > ... > x[t] > x[k]}
while (t < n) and (x[t+1] > x[k]) do begin
t:=t+1;
end;
{x[k+1] > ... > x[t] > x[k] > x[t+1] > ... > x[n]}
... обменять x[k] и x[t]
{x[k+1] > ... > x[n]}
... переставить участок x[k+1] ... x[n] в обратном порядке
Замечание. Программа имеет знакомый дефект: если t = n, то
x[t+1] не определено.
---------------- 'shen.txt' ends here ----------------
Второй способ (рекурсия):
---------------- 'magic2.c' begins here ----------------
#include <stdio.h>
#define size 9
int x[size];
/* int count = 0; */
void process(){
/* skipped */
}
void swap (int* arr, int sz){
int curr, i, tmp;
if (sz == 1){process(); return;}
/* findmin */
curr = 0;
for (i=1; i<sz; i++)
if (arr[i] < arr[curr]) curr = i;
tmp = arr[curr]; arr[curr] = arr[0]; arr[0] = tmp;
while (1){
/* recursion */
swap (arr+1, sz-1);
curr = 0;
for (i=1; i<sz; i++)
if (arr[i] > arr[0]){
curr = i; break;
}
if (curr == 0) return;
for (i=1; i<sz; i++)
if (arr[i] > arr[0] && arr[i] < arr[curr])
curr = i;
tmp = arr[curr]; arr[curr] = arr[0]; arr[0] = tmp;
}
}
main(){
int i;
printf ("\n\n\n");
for (i=0; i<size; i++) x[i] = i+1;
swap (x, size);
/* printf ("Listed %d Magic Squares\n", count); */
return 0;
}
---------------- 'magic2.c' ends here ----------------
Комментарии:
swap(addr, q) следует читать как "построить и обработать
в порядке возрастания все перестановки из q int'ов,
записанных начиная с адреса addr"; swap вытаскивает
(в порядке возрастания) в addr[0] все числа, записанные
в addr[1]...addr[q-1], каждый раз вызывая swap(addr+1, q-1);
process() осуществляет обработку перестановки, записанной в x[];
извините за корявость кода -- программа писалась на скорую руку.
WBR...
---
* Origin: Cosmo Canyon Station (2:5020/9481.21)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
получить перестановки