Реализации алгоритмов/Алгоритм Нарайаны: различия между версиями
Содержимое удалено Содержимое добавлено
Исправление форматирования, поправки к коду |
|||
Строка 4:
Во всех приведенных ниже реализациях <code>a</code> — массив, в котором в прямом порядке записана перестановка, а <code>n</code> — количество элементов в перестановке.
==[[w:C (язык программирования)|C]]==
<source lang="cpp">
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 NarayanaNextPermutation (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);
++j;
/* Шаг № 3 */
for (i = 0; i < (n - j + 1) >> 1; ++i)
swapItems(a, j + i, n - i - 1);
return j;
}
</source>
==
<source lang="pascal">
type T = integer;
function NarayanaNextPermutation
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
k := n - 2;
while (k >= 0) and (a[k] >= a[k + 1]) do
k := k - 1;
if k = -1 then
NarayanaNextPermutation := 0
else
{ Шаг № 2 }
l := n - 1;
while (l >= k + 1) and (a[k] >= a[l]) do
for i := k + 1 to (n + k) div 2 do
SwapItems(i, l)
end;
NarayanaNextPermutation := i
end;
</source>
==
===Вариант № 1===
<source lang="PHP">
function
$out = $a;
$k
while ($k >= 0 && $out[$k] >= $out[$k + 1]) {
}
if (-1 == $k) {
}
// Шаг № 2
$t = $n - 1;
while ($t >= 0 && $t >= $k + 1 && $out[$k] >= $out[$t]) {
}
$tmp = $out[$k];
$out[$k] = $out[$t];
$out[$t] = $tmp;
// Шаг № 3
for ($i = $k + 1; $i < ceil(($n + $k) / 2); ++$i) {
$tmp = $out[$i];
}
Строка 105 ⟶ 102 :
</source>
===Вариант № 2===
Вариант с выводом справа налево:
<source lang="PHP">
$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));
$
print $a = $x . $y;
print ‘<br/>’;
}
</source>
{{BookCat}}
|