Реализации алгоритмов/Алгоритм Нарайаны: различия между версиями
Содержимое удалено Содержимое добавлено
Исправление форматирования, поправки к коду |
Нет описания правки |
||
Строка 14: | Строка 14: | ||
} |
} |
||
int |
int nextPermutation (T *a, int n) { |
||
int i, j, l; |
int i, j, l; |
||
/* Шаг № 1 */ |
/* Шаг № 1 */ |
||
Строка 35: | Строка 35: | ||
type T = integer; |
type T = integer; |
||
function |
function NextPermutation (var a: array of T; n: integer): integer; |
||
var i, k, l: integer; |
var i, k, l: integer; |
||
procedure SwapItems (index_1, index_2: word); |
procedure SwapItems (index_1, index_2: word); |
||
Строка 50: | Строка 50: | ||
k := k - 1; |
k := k - 1; |
||
if k = -1 then |
if k = -1 then |
||
NextPermutation := 0 |
|||
else |
else |
||
begin |
begin |
||
Строка 64: | Строка 64: | ||
SwapItems(i, l) |
SwapItems(i, l) |
||
end; |
end; |
||
NextPermutation := i |
|||
end |
end |
||
end; |
end; |
||
Строка 72: | Строка 72: | ||
===Вариант № 1=== |
===Вариант № 1=== |
||
<source lang="PHP"> |
<source lang="PHP"> |
||
function |
function nextPermutation ($a, $n) { |
||
$out = $a; |
$out = $a; |
||
// Шаг № 1 |
// Шаг № 1 |
Версия от 20:48, 25 апреля 2017
Алгори́тм Нарайа́ны — нерекурсивный алгоритм, генерирующий по данной перестановке следующую за ней в лексикографическом порядке перестановку.
Во всех приведенных ниже реализациях a
— массив, в котором в прямом порядке записана перестановка, а n
— количество элементов в перестановке.
C
typedef int T;
void swapItems (T *array, unsigned index_1, unsigned index_2) {
T temp = array[index_1];
array[index_1] = array[index_2];
array[index_2] = temp;
}
int nextPermutation (T *a, int n) {
int i, j, l;
/* Шаг № 1 */
for (j = n - 2; j >= 0 && a[j] >= a[j + 1]; --j);
/* Шаг № 2 */
if (j == -1)
return 0;
for (l = n - 1; a[j] >= a[l]; --l);
swapItems(a, l, j);
++j;
/* Шаг № 3 */
for (i = 0; i < (n - j + 1) >> 1; ++i)
swapItems(a, j + i, n - i - 1);
return j;
}
Pascal
type T = integer;
function NextPermutation (var a: array of T; n: integer): integer;
var i, k, l: integer;
procedure SwapItems (index_1, index_2: word);
var temp: T;
begin
temp := a[index_1];
a[index_1] := a[index_2];
a[index_2] := temp
end;
begin
{ Шаг № 1 }
k := n - 2;
while (k >= 0) and (a[k] >= a[k + 1]) do
k := k - 1;
if k = -1 then
NextPermutation := 0
else
begin
{ Шаг № 2 }
l := n - 1;
while (l >= k + 1) and (a[k] >= a[l]) do
l := l - 1;
SwapItems(k, l);
{ Шаг № 3 }
for i := k + 1 to (n + k) div 2 do
begin
l := n + k - i;
SwapItems(i, l)
end;
NextPermutation := i
end
end;
PHP
Вариант № 1
function nextPermutation ($a, $n) {
$out = $a;
// Шаг № 1
$k = $n - 2;
while ($k >= 0 && $out[$k] >= $out[$k + 1]) {
--$k;
}
if (-1 == $k) {
return false;
}
// Шаг № 2
$t = $n - 1;
while ($t >= 0 && $t >= $k + 1 && $out[$k] >= $out[$t]) {
--$t;
}
$tmp = $out[$k];
$out[$k] = $out[$t];
$out[$t] = $tmp;
// Шаг № 3
for ($i = $k + 1; $i < ceil(($n + $k) / 2); ++$i) {
$t = $n + $k - $i;
$tmp = $out[$i];
$out[$i] = $out[$t];
$out[$t] = $tmp;
}
return $out;
}
Вариант № 2
Вариант с выводом справа налево:
$b = "123456789";
$a = strrev($b);
while ($a !=$b) {
$i = 0;
while($a[$i] > $a[$i - 1]) {
$i++;
}
$j = 0;
while($a[$j] < $a[$i]) {
++$j;
}
$c = $a[$j];
$a[$j] = $a[$i];
$a[$i] = $c;
$x = strrev(substr($a, 0, $i));
$y = substr($a, $i);
print $a = $x . $y;
print ‘<br/>’;
}