Вопрос по permutation, php, combinatorics – Получить все перестановки массива PHP?

19

Имеется массив строк PHP, например:

<code>['peter', 'paul', 'mary']
</code>

Как сгенерировать все возможные перестановки элементов этого массива? т.е .:

<code>peter-paul-mary
peter-mary-paul
paul-peter-mary
paul-mary-peter
mary-peter-paul
mary-paul-peter
</code>
@Andreyco, чтобы проверить, существует ли веб-форма из трех полей в таблице с одним столбцом. ohho
Я думаю, что вы имеете в виду перестановку, а не комбинацию. Jack
Это операция с экспоненциальным временем выполнения. Когда у вас есть 10 элементов в массиве, вы попадете в тысячи перестановок. Когда это будет 20, вы, вероятно, окажетесь в миллионах. GordonM
Для чего тебе это? Это слишком дорого, я думаю ... Должно быть что-то более умное ... Andreyco
Привет! Есть библиотека PHP, которая делает все, что вам нужно, используя генераторы и / или итераторы. Найдите библиотеку здесь:github.com/drupol/phpermutations  Дайте мне знать, если вам нужна помощь. Pol Dellaiera

Ваш Ответ

5   ответов
0

ов:

function permuteArray(array $input) {
    $input = array_values($input);

    // permutation of 1 value is the same value
    if (count($input) === 1) {
        return array($input);
    }

    // to permute multiple values, pick a value to put in the front and 
    // permute the rest; repeat this with all values of the original array
    $result = [];
    for ($i = 0; $i < count($input); $i++) {
        $copy  = $input;
        $value = array_splice($copy, $i, 1);
        foreach (permuteArray($copy) as $permutation) {
            array_unshift($permutation, $value[0]);
            $result[] = $permutation;
        }
    }

    return $result;
}

Этот алгоритм хорош и поучителен, как бы вы делали это на бумаге, но в остальном он очень неэффективен, поскольку он вычисляет одни и те же перестановки несколько раз. Нельзя сказать, что это очень непрактично для расчета перестановок больших массивов, поскольку пространство и количество вычислений растут в геометрической прогрессии.

7

что вам нужно, то есть, без выделения дополнительной памяти. В нем хранятся результирующие перестановки массива $ results. Я довольно уверен, что это быстрый способ решить задачу.

<?php
function computePermutations($array) {
    $result = [];

    $recurse = function($array, $start_i = 0) use (&$result, &$recurse) {
        if ($start_i === count($array)-1) {
            array_push($result, $array);
        }

        for ($i = $start_i; $i < count($array); $i++) {
            //Swap array value at $i and $start_i
            $t = $array[$i]; $array[$i] = $array[$start_i]; $array[$start_i] = $t;

            //Recurse
            $recurse($array, $start_i + 1);

            //Restore old order
            $t = $array[$i]; $array[$i] = $array[$start_i]; $array[$start_i] = $t;
        }
    };

    $recurse($array);

    return $result;
}


$results = computePermutations(array('foo', 'bar', 'baz'));
print_r($results);

Это работает в PHP & gt; 5.4. Я использовал анонимную функцию для рекурсии, чтобы поддерживать интерфейс основной функции в чистоте.

14
function pc_permute($items, $perms = array()) {
    if (empty($items)) { 
        echo join(' ', $perms) . "<br />";
    } else {
        for ($i = count($items) - 1; $i >= 0; --$i) {
             $newitems = $items;
             $newperms = $perms;
             list($foo) = array_splice($newitems, $i, 1);
             array_unshift($newperms, $foo);
             pc_permute($newitems, $newperms);
         }
    }
}

$arr = array('peter', 'paul', 'mary');

pc_permute($arr);

function pc_next_permutation($p, $size) {
    // slide down the array looking for where we're smaller than the next guy
    for ($i = $size - 1; $p[$i] >= $p[$i+1]; --$i) { }

    // if this doesn't occur, we've finished our permutations
    // the array is reversed: (1, 2, 3, 4) => (4, 3, 2, 1)
    if ($i == -1) { return false; }

    // slide down the array looking for a bigger number than what we found before
    for ($j = $size; $p[$j] <= $p[$i]; --$j) { }

    // swap them
    $tmp = $p[$i]; $p[$i] = $p[$j]; $p[$j] = $tmp;

    // now reverse the elements in between by swapping the ends
    for (++$i, $j = $size; $i < $j; ++$i, --$j) {
         $tmp = $p[$i]; $p[$i] = $p[$j]; $p[$j] = $tmp;
    }

    return $p;
}

$set = split(' ', 'she sells seashells'); // like array('she', 'sells', 'seashells')
$size = count($set) - 1;
$perm = range(0, $size);
$j = 0;

do { 
     foreach ($perm as $i) { $perms[$j][] = $set[$i]; }
} while ($perm = pc_next_permutation($perm, $size) and ++$j);

foreach ($perms as $p) {
    print join(' ', $p) . "\n";
}

http://docstore.mik.ua/orelly/webprog/pcook/ch04_26.htm

Это хорошее решение, я проверяю его, а также делюсь с другими, спасибо, братан.
Я в конечном итоге с помощьюpc_next_permutation() для лучших типов возврата. Спасибо! ohho
5

глядя. Приземлился, написав следующее, что делает работу.

С 8 элементами он работает довольно быстро (немного быстрее, чем примеры, которые я нашел в Интернете), но выходите за рамки этого, и время выполнения быстро нарастает. Если вам нужно только вывести результаты, это можно сделать быстрее, а использование памяти значительно сократится.

print_r(AllPermutations(array('peter', 'paul', 'mary')));

function AllPermutations($InArray, $InProcessedArray = array())
{
    $ReturnArray = array();
    foreach($InArray as $Key=>$value)
    {
        $CopyArray = $InProcessedArray;
        $CopyArray[$Key] = $value;
        $TempArray = array_diff_key($InArray, $CopyArray);
        if (count($TempArray) == 0)
        {
            $ReturnArray[] = $CopyArray;
        }
        else
        {
            $ReturnArray = array_merge($ReturnArray, AllPermutations($TempArray, $CopyArray));
        }
    }
    return $ReturnArray;
}

Обратите внимание, что количество перестановок является факториалом количества элементов в массиве. Для 3 предметов - 6 перестановок, для 4 - 24, для 5 - 120, для 6 - 720 и т. Д.

2

function pc_permute($items, $perms = [],&$ret = []) {
   if (empty($items)) {
       $ret[] = $perms;
   } else {
       for ($i = count($items) - 1; $i >= 0; --$i) {
           $newitems = $items;
           $newperms = $perms;
           list($foo) = array_splice($newitems, $i, 1);
           array_unshift($newperms, $foo);
           $this->pc_permute($newitems, $newperms,$ret);
       }
   }
   return $ret;
}

Это на самом деле вернет массив со всеми возможными перестановками.

$options = ['startx','starty','startz','endx','endy','endz'];
$x = $this->pc_permute($options);
var_dump($x);

  [0]=>
 array(6) {
    [0]=>
    string(6) "startx"
    [1]=>
    string(6) "starty"
    [2]=>
    string(6) "startz"
    [3]=>
    string(4) "endx"
    [4]=>
    string(4) "endy"
    [5]=>
    string(4) "endz"
  }
  [1]=>
  array(6) {
    [0]=>
    string(6) "starty"
    [1]=>
    string(6) "startx"
    [2]=>
    string(6) "startz"
    [3]=>
    string(4) "endx"
    [4]=>
    string(4) "endy"
    [5]=>
    string(4) "endz"
  }
  [2]=>
  array(6) {
    [0]=>
    string(6) "startx"
    [1]=>
    string(6) "startz"
    [2]=>
    string(6) "starty"
    [3]=>
    string(4) "endx"
    [4]=>
    string(4) "endy"
    [5]=>
    string(4) "endz"
  }
  [3]=>
  array(6) {
    [0]=>
    string(6) "startz"
    [1]=>
    string(6) "startx"
    [2]=>
    string(6) "starty"
    [3]=>
    string(4) "endx"
    [4]=>
    string(4) "endy"
    [5]=>
    string(4) "endz"
  }
  [4]=>
  array(6) {
    [0]=>
    string(6) "starty"
    [1]=>
    string(6) "startz"
    [2]=>
    string(6) "startx"
    [3]=>
    string(4) "endx"
    [4]=>
    string(4) "endy"
    [5]=>
    string(4) "endz"
  }
  [5]=>
  array(6) {
    [0]=>
    string(6) "startz"
    [1]=>
    string(6) "starty"
    [2]=>
    string(6) "startx"
    [3]=>
    string(4) "endx"
    [4]=>
    string(4) "endy"
    [5]=>
    string(4) "endz"
  }
  [6]=> ................ a lot more

Я нашел немного более полезным вернуть массив вместо строки. Тогда дело за приложением использования, как обработать результаты (присоединиться к ним или что-то еще).

Похожие вопросы