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

Получение атрибута href элемента A

Web

Как удалить куки

Web

Замена диакритических знаков php

Система тестирования на PHP: что это и как это сделать
Web

Система тестирования на PHP: что это и как это сделать