| |
|
|
| | Есть числа в диапазоне от единицы до некоего числа, расположенные по возростанию (это индексы массива). Меняя эти числа местами, можно добиться изменения порядка считывания массива.
Как перебрать все варианты перестановки чисел? | |
| |
|
|
| |
|
|
| |
для: Владимир55
(04.10.2009 в 01:32)
| | |
<pre><?
// меняем местами значения
function swap(&$a, &$b) {
$c = $a;
$a = $b;
$b = $c;
}
// количество перестановок = n!
function fact($n){
for ( $i = 1, $ret = 1; $i <= $n; $i++ ) {
$ret *= $i;
}
return $ret;
}
// вычисление следующей пермутации
function nextPerm(&$arr) {
$n = count($arr);
for ( $i = $n - 1; $i > 0; --$i ) {
if ( $arr[$i] > $arr[$i-1] ) {
for ( $j = $n - 1; $j > $i; --$j ) {
if ( $arr[$j] > $arr[$i-1] ) break;
}
swap($arr[$i-1], $arr[$j]);
break;
}
}
for ( $j = $n - 1; $j > $i; --$j, ++$i ) {
swap($arr[$i], $arr[$j]);
}
}
$arr = array(1, 2, 3, 4);
$n = fact(count($arr));
for ( $i = 0; $i < $n; $i++ ) {
nextPerm($arr);
print_r($arr);
}
|
Исходный алгоритм на си. | |
| |
|
|
