digitorum.ru

Как меня найти

Профиль

icq: 4415944

Нахождение всех перестановок массива

php

По всему интернету разбросано полно примеров как это сделать. Причем пример один и тот же и везде он не лишен мелкого бага с нотисами.  

Notice: Undefined offset: -1 in...

 

Исходник можно посмотреть по ссылке http://docstore....

В общем код, который использую я:

<?php
	// получить "следующую" перестановку (она же pc_next_permutation во всех примерах)
	function permutation_next($p, $size) {
		// проходим массив сверху вниз в поисках числа, которое меньше следующего
		for ($i = $size - 1; ($i >= 0 && $p[$i] >= $p[$i+1]); --$i) { }
		// если такого нет, прекращаем перестановки
		// массив перевернут: (1, 2, 3, 4) => (4, 3, 2, 1)
		if ($i == -1) { 
			return false; 
		}
		// проходим массив сверху вниз в поисках числа,
		// превосходящего найденное ранее
		for ($j = $size; $p[$j] <= $p[$i]; --$j) { }
		// переставляем их
		$tmp = $p[$i]; 
		$p[$i] = $p[$j]; 
		$p[$j] = $tmp;
		// теперь переворачиваем массив путем перестановки элементов,
		// начиная с конца
		for (++$i, $j = $size; $i < $j; ++$i, --$j) {
			$tmp = $p[$i]; 
			$p[$i] = $p[$j]; 
			$p[$j] = $tmp;
		}
		return $p;
	}
	
	// получить полный список перестановок
	function permutations_list($set = array()) {
		$size = count($set) - 1;
		$perm = range(0, $size);
		$j = 0;
		
		if($size > 0) {
			do {
				foreach ($perm as $i) { 
					$perms[$j][] = $set[$i]; 
				}
			} while (is_array($perm = permutation_next($perm, $size)) && ++$j);
		} else {
			$perms = array($set[0]);
		}
		return $perms;
	}

 

Использование:

<?php
	print_r(permutations_list(split(' ', 'she sells seashells')));