Форум: Форум PHPФорум ApacheФорум Регулярные ВыраженияФорум MySQLHTML+CSS+JavaScriptФорум FlashРазное
Новые темы: 0000000
Самоучитель PHP 5 / 6 (3 издание). Авторы: Кузнецов М.В., Симдянов И.В. MySQL 5. В подлиннике. Авторы: Кузнецов М.В., Симдянов И.В. Объектно-ориентированное программирование на PHP. Авторы: Кузнецов М.В., Симдянов И.В. PHP Puzzles. Авторы: Кузнецов М.В., Симдянов И.В. Самоучитель MySQL 5. Авторы: Кузнецов М.В., Симдянов И.В.
ВСЕ НАШИ КНИГИ

Форум PHP

Выбрать другой форум

 

Здравствуйте, Посетитель!

вид форума:
Линейный форум Структурный форум

тема: Как добиться полного разнообразия чисел?
 
 автор: Владимир55   (04.10.2009 в 01:32)   письмо автору
 
 

Есть числа в диапазоне от единицы до некоего числа, расположенные по возростанию (это индексы массива). Меняя эти числа местами, можно добиться изменения порядка считывания массива.

Как перебрать все варианты перестановки чисел?

  Ответить  
 
 автор: Саня   (04.10.2009 в 12:13)   письмо автору
 
   для: Владимир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);
}

Исходный алгоритм на си.

  Ответить