Реализации алгоритмов/Алгоритм Нарайаны: различия между версиями

Содержимое удалено Содержимое добавлено
Исправление форматирования, поправки к коду
Строка 4:
Во всех приведенных ниже реализациях <code>a</code> — массив, в котором в прямом порядке записана перестановка, а <code>n</code> — количество элементов в перестановке.
 
==[[w:C (язык программирования)|C]]==
== C ==
<source lang="cpp">
typedef int T;
int NarayanaNextPerm (int *a, int n)
{
int i, j, l;
 
void swapItems (T *array, unsigned index_1, unsigned index_2) {
//Шаг 1
T temp = array[index_1];
for (j = n - 2; j >= 0 && a[j] >= a[j + 1]; j--);
array[index_1] = array[index_2];
array[index_2] = temp;
}
 
int NarayanaNextPermutation (T *a, int n) {
//Шаг 2
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);
 
for swapItems(l = n - 1; a[j], >= a[l];, l--j);
++j;
 
/* Шаг № 3 */
swap(&a[l], &a[j]);
for (i = 0; i < (n - j + 1) >> 1; ++i)
 
swapItems(a, j + i, n - i - 1);
j++;
 
//Шаг 3
for (i = 0; i < (n - j + 1) / 2; i++)
swap(&a[j + i], &a[n - i - 1]);
 
return j;
}
</source>
 
=== [[w:Паскаль =(язык программирования)|Pascal]]==
<source lang="pascal">
type T = integer;
function NarayanaNextPerm(var a: array of integer; n: integer): integer;
 
var
function NarayanaNextPermutation i,(var k,a: t,array tmpof 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
 
NarayanaNextPermutation := 0
if k = -1 then begin
else
NarayanaNextPerm := 0;
Exit;begin
{ Шаг № 2 }
end;
l := n - 1;
 
while (l >= k + 1) and (a[k] >= a[l]) do
//Шаг 2
t l := nl - 1;
while (t >= k + 1) and SwapItems(a[k], >= a[t]l) do;
t := t - 1;{ Шаг № 3 }
for i := k + 1 to (n + k) div 2 do
tmp := a[k];
a[k] := a[t]; begin
a[t] l := tmpn + k - i;
SwapItems(i, l)
 
end;
//Шаг 3
NarayanaNextPermutation := i
for i := k + 1 to (n + k) div 2 do begin
t := n + k - i;end
tmp := a[i];
a[i] := a[t];
a[t] := tmp;
end;
NarayanaNextPerm := i;
end;
</source>
 
=== [[w:PHP =|PHP]]==
===Вариант № 1===
<source lang="PHP">
function narayanaNarayanaNextPermutation ($ina, $n) {
$out = $a;
{
$out // =Шаг $in;№ 1
$k = $n - 2;
while ($k >= 0 && $out[$k] >= $out[$k + 1]) {
{--$k;
$k--;
}
if (-1 == $k) {
 
ifreturn (-1 == $k)false;
{
return false;
}
// Шаг № 2
 
$t = $n - 1;
while ($t >= 0 && $t >= $k + 1 && $out[$k] >= $out[$t]) {
{--$t;
$t--;
}
$tmp = $out[$k];
 
$tmp = $out[$k];
$out[$k] = $out[$t];
$out[$t] = $tmp;
// Шаг № 3
 
for ($i = $k + 1; $i < ceil(($n + $k) / 2); ++$i) {
//Шаг 3
for ($it = $k + 1; $i < ceil(($n + $k) / 2);- $i++);
$tmp = $out[$i];
{
$t = $n + $kout[$i] -= $iout[$t];
$tmp = $out[$it] = $tmp;
$out[$i] = $out[$t];
$out[$t] = $tmp;
}
 
Строка 105 ⟶ 102 :
</source>
 
===Вариант № 2===
{{BookCat}}
 
 
=== PHP ===
Вариант с выводом справа налево:
<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];
$j++;
$a[$j] = $a[$i];
}
$a[$i] = $c;
 
$x = strrev(substr($a, 0, $i));
$c=$a[$j];
$a[$j]y = substr($a[, $i]);
$a[$i]=$c;
 
$x=strrev(substr($a, 0, $i));
$y=substr($a, $i);
 
print $a=$x.$y;
print ‘<br/>’;
 
print $a = $x . $y;
print ‘<br/>’;
}
</source>
 
{{BookCat}}