Перестановка или permutation на php

19 Мар
2012

К сожалению, когда мне нужен был алгоритм перестановки на php, такового не нашлось на блоге. От того и появилось желание его разработать.
function permutation($arr) {
    if(is_array($arr)&&count($arr)>1) {
        foreach($arr as $k=>$v) {
            $answer[][]=$v;
        }
        do {
            foreach($arr as $k=>$v) {
                foreach($answer as $key=>$val) {
                    if(!in_array($v,$val)) {
                        $tmpArr[]=array_merge(array($v),$val);
                    }
                }
            }
            $answer=$tmpArr;
            unset($tmpArr);
        }while(count($answer[0])!=count($arr));
        return $answer;
    }else
        $answer=$arr;
    return $answer;
}
Данный алгоритм прост, он берет все элементы массива и делает их новыми элементами подмассива, за тем все повторяется, до тех пор, когда количество элементов новых массивов не будет совпадать с количеством элементов исходного массива. В итоге на выходе получаем массив всех перестановок элементов содержащий n! вложенных массивов.

Картиночка отображающая суть задачи
По материалам Хабрахабр.



загрузка...

Комментарии:

Наверх