Web

Как выполнить перестановки для любых наборов чисел

У меня есть числа от 0 до 8. Я хотел бы получить в результате все возможные наборы этих чисел, каждый набор должен использовать все числа, каждое число может встречаться только один раз в наборе. Я бы хотел увидеть решение на PHP, которое могло бы вывести результат. Или, по крайней мере, хотелось бы немного освежить теорию комбинаторики, так как я ее давно забыл. По какой формуле можно вычислить количество перестановок?

Примеры множеств:

  • 0-1-2-3-4-5-6-7-8

  • 0-1-2-3-4-5-6-8-7

  • 0-1-2-3-4-5-8-6-7

  • 0-1-2-3-4-8-5-6-7

  • 0-1-2-3-8-4-5-6-7

  • 0-1-2-8-3-4-5-6-7

  • и так и далее...

 

 Ответ 1

Вот ваша формула перестановок:

nPk = n!/(n-k)!

 В вашем случае у вас 9 записей, и вы хотите выбрать все из них, это 9P9 = 9! = 362880.

pc_permute(array(0, 1, 2, 3, 4, 5, 7, 8));

 Функция, которая выполняет перестановки:

function pc_permute($items, $perms = array( )) {

    if (empty($items)) { 

        print join(' ', $perms) . "\n";

    }  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);

         }

    }

}

 

 Ответ 2

Начиная с версии PHP 5.5, вы можете использовать генераторы. Генераторы экономят много памяти и работают намного быстрее (более чем в два раза, по сравнению с pc_permute()). Так что если у вас есть шанс установить PHP 5.5, вам определенно нужны Генераторы.

function permutations(array $elements) {

    if (count($elements) <= 1) {

        yield $elements;

    } else {

        foreach (permutations(array_slice($elements, 1)) as $permutation) {

            foreach (range(0, count($elements) - 1) as $i) {

                yield array_merge(

                    array_slice($permutation, 0, $i),

                    [$elements[0]],

                    array_slice($permutation, $i)

                );

            }

        }

    }

}

Применение:

$list = ['a', 'b', 'c'];

foreach (permutations($list) as $permutation) {

    echo implode(',', $permutation) . PHP_EOL;

}

 Вывод будет таким:

a,b,c

b,a,c

b,c,a

a,c,b 

c,a,b

c,b,a

 

Ответ 3

Поскольку этот вопрос часто появляется в результатах поиска Google, вот модифицированная версия принятого ответа, которая возвращает все комбинации в массив и передает их в качестве возвращаемого значения функции.

function pc_permute($items, $perms = array( )) {

    if (empty($items)) {

        $return = array($perms);

    }  else {

        $return = array();

        for ($i = count($items) - 1; $i >= 0; --$i) {

             $newitems = $items;

             $newperms = $perms;

         list($foo) = array_splice($newitems, $i, 1);

             array_unshift($newperms, $foo);

             $return = array_merge($return, pc_permute($newitems, $newperms));

         }

    }

    return $return;

}

Применение:

$value = array('1', '2', '3');

print_r(pc_permute($value));

 

 

Ответ 4

Вот еще один вариант решения данной задачи:

function combination_number($k,$n){

    $n = intval($n);

    $k = intval($k);

    if ($k > $n){

        return 0;

    } elseif ($n == $k) {

        return 1;

    } else {

        if ($k >= $n - $k){

            $l = $k+1;

            for ($i = $l+1 ; $i <= $n ; $i++)

                $l *= $i;

            $m = 1;

            for ($i = 2 ; $i <= $n-$k ; $i++)

                $m *= $i;

        } else {

            $l = ($n-$k) + 1;

            for ($i = $l+1 ; $i <= $n ; $i++)

                $l *= $i;

            $m = 1;

            for ($i = 2 ; $i <= $k ; $i++)

                $m *= $i;            

        }

    }

    return $l/$m;

}

 

function array_combination($le, $set){

 

    $lk = combination_number($le, count($set));

    $ret = array_fill(0, $lk, array_fill(0, $le, '') );

 

    $temp = array();

    for ($i = 0 ; $i < $le ; $i++)

        $temp[$i] = $i;

    $ret[0] = $temp;

    for ($i = 1 ; $i < $lk ; $i++){

        if ($temp[$le-1] != count($set)-1){

            $temp[$le-1]++;

        } else {

            $od = -1;

            for ($j = $le-2 ; $j >= 0 ; $j--)

                if ($temp[$j]+1 != $temp[$j+1]){

                    $od = $j;

                    break;

                }

            if ($od == -1)

                break;

            $temp[$od]++;

            for ($j = $od+1 ; $j < $le ; $j++)    

                $temp[$j] = $temp[$od]+$j-$od;

        }

        $ret[$i] = $temp;

    }

    for ($i = 0 ; $i < $lk ; $i++)

        for ($j = 0 ; $j < $le ; $j++)

            $ret[$i][$j] = $set[$ret[$i][$j]];   

 

    return $ret;

}

 Вот как им пользоваться:

Чтобы получить количество комбинаций:

combination_number(3,10); // возвращает количество комбинаций набора из десяти элементов.

Чтобы получить все возможные комбинации:

$mySet = array("A","B","C","D","E","F");

array_combination(3, $mySet); // возвращает все возможные комбинации из 3 элементов шестиэлементного множества.



Ответ 5

Я перенес на Python код из предыдущего ответа, приведенный здесь (с использованием генераторов). Его преимущество перед решениями, опубликованными до сих пор, заключается в том, что он позволяет задавать r (размер перестановки).

function permutations($pool, $r = null) {

    $n = count($pool);

    if ($r == null) {

        $r = $n;

    }

     if ($r > $n) {

        return;

    }

    $indices = range(0, $n - 1);

    $cycles = range($n, $n - $r + 1, -1); // обратный отсчет

    yield array_slice($pool, 0, $r);

    if ($n <= 0) {

        return;

    }

    while (true) {

        $exit_early = false;

        for ($i = $r;$i--;$i >= 0) {

            $cycles[$i]-= 1;

            if ($cycles[$i] == 0) {

                // Переместите все, что находится в индексе $i, в конец, все сдвиньте назад

                if ($i < count($indices)) {

                    $removed = array_splice($indices, $i, 1);

                    array_push($indices, $removed[0]);

                }

                $cycles[$i] = $n - $i;

            } else {

                $j = $cycles[$i];

                // Swap indices $i & -$j.

                $i_val = $indices[$i];

                $neg_j_val = $indices[count($indices) - $j];

                $indices[$i] = $neg_j_val;

                $indices[count($indices) - $j] = $i_val;

                $result = [];

                $counter = 0;

                foreach ($indices as $indx) {

                    array_push($result, $pool[$indx]);

                    $counter++;

                    if ($counter == $r) break;

                }

                yield $result;

                $exit_early = true;

                break;

            }

        }

        if (!$exit_early) {

            break; // Внешний цикл while

        }

    }

}

Это работает для меня! Пример использования:

$result = iterator_to_array(permutations([1, 2, 3, 4], 3));

foreach ($result as $row) {

    print implode(", ", $row) . "\n";

}



Ответ 6

Это моя версия класса. Этот класс строит и возвращает перестановочный массив в качестве результата:

class Permutation {

    private $result;

     public function getResult() {

        return $this->result;

    }

     public function permute($source, $permutated=array()) {

        if (empty($permutated)){

            $this->result = array();

        }

        if (empty($source)){

            $this->result[] = $permutated;

        } else {

            for($i=0; $i<count($source); $i++){

                $new_permutated = $permutated;

                $new_permutated[] = $source[$i];

                $new_source =    array_merge(array_slice($source,0,$i),array_slice($source,$i+1));

                $this->permute($new_source, $new_permutated);

            }

        }

        return $this;

    }

}

 

$arr = array(1,2,3,4,5);

$p = new Permutation();

print_r($p->permute($arr)->getResult());



Ответ 7

// вызов функции

print_r(combinations([1,2,3,4,5,6,7,8,9,10,11,12,13]));

/**

 * @param $mainArray

 * @param int $size - optional

 * @param array $combinations - optional

 * @return mixed

 */

function combinations($mainArray, $size = 3, $combinations = []) {

    if (empty($combinations)) {

        $combinations = $mainArray;

    }

    if ($size == 1) {

        return str_replace('-','',$combinations);;

    }

    $newCombination = array();

    foreach ($mainArray as $key => $val){

        foreach ($combinations as $char) {

            if(in_array($val, explode('-', $char))){

                continue;

            }

            $newCombination[] = $val . '-' . $char;

        }

    }

    return combinations($mainArray, $size - 1, $newCombination);

Следующее решение:

function sampling($chars, $size, $combinations = array()) {

    # если это первая итерация, то первый набор 

    # комбинаций совпадает с набором символов

    if (empty($combinations)) {

        $combinations = $chars;

    }

    # we're done if we're at size 1

    if ($size == 1) {

        return $combinations;

    }

    # инициализировать массив, чтобы поместить в него новые значения

    $new_combinations = array();

    # перебираем существующие комбинации и набор символов для создания строк

    foreach ($combinations as $combination) {

        foreach ($chars as $char) {

            $new_combinations[] = $combination .'-'. $char ; 

        }

    }

    # снова вызвать ту же функцию для следующей итерации

    return $this->sampling($chars, $size - 1, $new_combinations);

}

function array_has_dupes($array) {

   return count($array) !== count(array_unique($array));

}   

function total() {

    // Генерировать стоимость билета

    $arrfinal = array();

    // комбинации

    $chars = array(1,2,3,4,5,6,7,8,9,10,11,12,13); // для 10 цифр

    $combinations = $this->sampling($chars, 3);

    //print_r($combinations); //exit;

    foreach($combinations as $key => $val) {

        $arr = explode('-', $val);//str_split($val);

        if(!$this->array_has_dupes($arr)){

            $arrfinal[] = str_replace('-', '', $val);

        }

    }

  echo '<pre>'; print_r($arrfinal); echo '</pre>';

}

 

Схожие статьи

Что такое локальное хранилище и как его используют в программировании
Web

Что такое локальное хранилище и как его используют в программировании

Все, что нужно знать об атаке на WordPress — меры предосторожности
Web

Все, что нужно знать об атаке на WordPress — меры предосторожности

Адаптивный дизайн. Делаем сайты для любых устройств своими руками
Web

Адаптивный дизайн. Делаем сайты для любых устройств своими руками

Как правильно выбрать имя домена для своего сайта? Лучшие примеры
Web

Как правильно выбрать имя домена для своего сайта? Лучшие примеры

×