Web

Применение комбинации элементов в массивах PHP

У меня есть массив из 7 чисел (1,2,3,4,5,6,7), и я хочу выбрать 5 из них следующим образом:

(1,2,3,4,5), (1,2,3,4,6), (1,2,3,4,7).

Обратите внимание, что (1,2,3,4,5) равно (4,5,3,1,2), поэтому только одно из них должно быть включено в вывод. Я хотел бы узнать, есть ли функция в PHP или какой-либо алгоритм, который может это сделать? Я понятия не имею, с чего начать. Можете ли вы мне помочь? Я хочу, чтобы все комбинации из 7 заданных чисел (они взяты из массива) были помещены в 5 слотов, не обращая внимания на порядок.

 

Ответ 1

Вы можете использовать решение, найденное здесь http://stereofrog.com/blok/on/070910

Если ссылка не работает, вот код...

class Combinations implements Iterator {

    protected $c = null;

    protected $s = null;

    protected $n = 0;

    protected $k = 0;

    protected $pos = 0;

    function __construct($s, $k) {

        if(is_array($s)) {

            $this->s = array_values($s);

            $this->n = count($this->s);

        } else {

            $this->s = (string) $s;

            $this->n = strlen($this->s);

        }

        $this->k = $k;

        $this->rewind();

    }

    function key() {

        return $this->pos;

    }

    function current() {

        $r = array();

        for($i = 0; $i < $this->k; $i++)

            $r[] = $this->s[$this->c[$i]];

        return is_array($this->s) ? $r : implode('', $r);

    }

    function next() {

        if($this->_next())

            $this->pos++;

        else

            $this->pos = -1;

    }

    function rewind() {

        $this->c = range(0, $this->k);

        $this->pos = 0;

    }

    function valid() {

        return $this->pos >= 0;

    }

 

    protected function _next() {

        $i = $this->k - 1;

        while ($i >= 0 && $this->c[$i] == $this->n - $this->k + $i)

            $i--;

        if($i < 0)

            return false;

        $this->c[$i]++;

        while($i++ < $this->k - 1)

            $this->c[$i] = $this->c[$i - 1] + 1;

        return true;

    }

}

 

foreach(new Combinations("1234567", 5) as $substring)

    echo $substring, ' ';

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

12345 12346 12347 12356 12357 12367 12456 12457 12467 12567 13456 13457 13467 13567 14567 23456 23457 23467 23567 24567 34567

 

Ответ 2

php код:

<?php

echo "<pre>";

$test = array("test_1","test_2","test_3");

// получить комбинацию

$return = uniqueCombination($test);

//сортировка

sort($return);

// вывод

print_r(array_map(function($v){ return implode(",", $v); }, $return));

function uniqueCombination($in, $minLength = 1, $max = 2000) {

    $count = count($in);

    $members = pow(2, $count);

    $return = array();

    for($i = 0; $i < $members; $i ++) {

        $b = sprintf("%0" . $count . "b", $i);

        $out = array();

        for($j = 0; $j < $count; $j ++) {

            $b{$j} == '1' and $out[] = $in[$j];

        }

        count($out) >= $minLength && count($out) <= $max and $return[] = $out;

        }

    return $return;

}

?>

 

Вывод:

Array (

    [0] => test_1

    [1] => test_2

    [2] => test_3

    [3] => test_1,test_2

    [4] => test_1,test_3

    [5] => test_2,test_3

    [6] => test_1,test_2,test_3

)

 

Ответ 3

Библиотека «Math_Combinatorics» в репозитории «PEAR» делает именно то, что вы хотите. Пакет, который возвращает все комбинации и перестановки, без повторений, заданного множества и размера подмножества. Ассоциативные массивы сохраняются:

require_once 'Math/Combinatorics.php';

$combinatorics = new Math_Combinatorics;

$input = array(1, 2, 3, 4, 5, 6, 7);

$output = $combinatorics->combinations($input, 5); // 5 is the subset size

 

// 1,2,3,4,5

// 1,2,3,4,6

// 1,2,3,4,7

// 1,2,3,5,6

// 1,2,3,5,7

// 1,2,3,6,7

// 1,2,4,5,6

// 1,2,4,5,7

// 1,2,4,6,7

// 1,2,5,6,7

// 1,3,4,5,6

// 1,3,4,5,7

// 1,3,4,6,7

// 1,3,5,6,7

// 1,4,5,6,7

// 2,3,4,5,6

// 2,3,4,5,7

// 2,3,4,6,7

// 2,3,5,6,7

// 2,4,5,6,7

// 3,4,5,6,7

 

Ответ 4

Еще одно решение, основанное на стеке. Оно очень быстрое, но потребляет много памяти. Надеюсь, это кому-нибудь поможет. Подробнее:

function _combine($numbers, $length) {

    $combinations = array();

    $stack = array();

    // все комбинации могут быть упорядочены

    sort($numbers);

    // запуск

    array_push($stack, array(

        'store' => array(),

        'options' => $numbers,

    ));

    while (true) {

        // открыть элемент

        $item = array_pop($stack);

        // конец стека

        if (!$item) {

            break;

        }

       // действительное хранилище

        if ($length <= count($item['store'])) {

            $combinations[] = $item['store'];

            continue;

        }

        // обход, когда опций недостаточно

        if (count($item['store']) + count($item['options']) < $length) {

            continue;

        }

        foreach ($item['options'] as $index => $n) {

            $newStore = $item['store'];

            $newStore[] = $n;

            // каждая комбинация может быть упорядочена

            // поэтому принимаем только варианты, которые больше, чем максимальное число вариантов

            $newOptions = array_slice($item['options'], $index + 1);

            // вставляем новые элементы

            array_push($stack, array(

                'store' => $newStore,

                'options' => $newOptions,

            ));

        }

    }

    return $combinations;

}

 

 Ответ 5

Улучшаем предыдущий ответ, чтобы он работал и с ассоциативным массивом:

function uniqueCombination($values, $minLength = 1, $maxLength = 2000) {

    $count = count($values);

    $size = pow(2, $count);

    $keys = array_keys($values);

    $return = [];

    for($i = 0; $i < $size; $i ++) {

        $b = sprintf("%0" . $count . "b", $i);

        $out = [];

        for($j = 0; $j < $count; $j ++) {

            if ($b[$j] == '1') {

                $out[$keys[$j]] = $values[$keys[$j]];

            }

        }

        if (count($out) >= $minLength && count($out) <= $maxLength) {

             $return[] = $out;

        }

    }

    return $return;

}

 Например:

print_r(uniqueCombination([

    'a' => 'xyz',

    'b' => 'pqr',

]);

Результат:

Array (

    [0] => Array  (

            [b] => pqr

        )

    [1] => Array  (

            [a] => xyz

        )

    [2] => Array  (

            [a] => xyz

            [b] => pqr

        )

)

Код по-прежнему будет работать и для неассоциативных массивов:

print_r(uniqueCombination(['a', 'b']);

Результат:

Array (

    [0] => Array  (

            [1] => b

        )

    [1] => Array  (

            [0] => a

        )

    [2] => Array  (

            [0] => a

            [1] => b

        )

)

 

 

Ответ 6

Новое решение, оптимизирующее скорость и память для алгоритма комбинирования.

Задача: генерировать комбинации K чисел из массива чисел. Новое решение будет использовать K операторов 'for'. Один 'for' для одного числа. Например: $K = 5 означает, что используется 5 операторов 'for'.

$total = count($array);

$i0 = -1;

for ($i1 = $i0 + 1; $i1 < $total; $i1++) {

    for ($i2 = $i1 + 1; $i2 < $total; $i2++) {

        for ($i3 = $i2 + 1; $i3 < $total; $i3++) {

            for ($i4 = $i3 + 1; $i4 < $total; $i4++) {

                for ($i5 = $i4 + 1; $i5 < $total; $i5++) {

                    $record = array();

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

                        $t = "i$i";

                        $record[] = $array[$$t];

                    }

                    $callback($record);

                }

            }

        }

    }

}

И детализация кода, сгенерировавшего реальный код, который будет выполнен функцией eval():

function combine($array, $k, $callback) {

    $total = count($array);

    $init = '

        $i0 = -1;

    ';

    $sample = '

        for($i{current} = $i{previous} + 1; $i{current} < $total; $i{current}++ ) {

            {body}

        }

    ';

    $do = '

        $record = array();

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

            $t = "i$i";

            $record[] = $array[$$t];

        }

        $callback($record);

    ';

    $for = '';

    for ($i = $k; $i >= 1; $i--) {

        switch ($i) {

            case $k:

                $for = str_replace(['{current}', '{previous}', '{body}'], [$i, $i - 1, $do], $sample);

                break;

            case 1:

                $for = $init . str_replace(['{current}', '{previous}', '{body}'], [$i, $i - 1, $for], $sample);

                break;

            default:

                $for = str_replace(['{current}', '{previous}', '{body}'], [$i, $i - 1, $for], $sample);

                break;

        }

    }

    // выполнение

    eval($for);

}

Как объединить K чисел массива:

$k = 5;

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

$callback = function ($record) {

    echo implode($record) . "\n";

};

combine($array, $k, $callback);

 

Ответ 7

Мне нужна была объединяющая функция, включающая подмножества, поэтому я взял предыдущий ответ и изменил его для своих нужд. Если передать в функцию [1,2,3,4], она вернет все уникальные комбинации и подмножества, отсортированные следующим образом:

[

  [1,2,3,4], [1,2,3], [1,2,4], [1,3,4], [2,3,4], [1,2], [1,3], [1,4], [2,3], [2,4], [3,4], [1], [2], [3], [4]

]

Вот функция:

function get_combinations_with_length( $numbers, $length ){

    $result = array();

    $stack = array();

    // все комбинации могут быть упорядочены

    sort($numbers);

    // запуск

    array_push($stack, array(

        'store' => array(),

        'options' => $numbers,

    ));

    while (true) {

        // открыть элемент

        $item = array_pop($stack);

        // конец стека

        if (!$item) break;

        // действительное хранилище

        if ($length <= count($item['store'])) {

            $result[] = $item['store'];

            continue;

        }

        // обход, когда опций недостаточно

        if (count($item['store']) + count($item['options']) < $length) {

            continue;

        }

        foreach ($item['options'] as $i=>$n) {

            $newStore = $item['store'];

            $newStore[] = $n;

            // каждая комбинация может быть упорядочена, поэтому принимайте только те варианты, которые больше, чем номера индексов в массиве

            $newOptions = array_slice($item['options'], $i + 1);

            // array_unshift для сортировки по числам, array_push для обратной сортировки

            array_unshift($stack, array(

                'store' => $newStore,

                'options' => $newOptions,

            ));

        }

    }

    return $result;

}

 

function get_all_combinations( $numbers ){

    $length = count($numbers);

    $result = [];

    while ($length > 0) {

        $result = array_merge($result, get_combinations_with_length( $numbers, $length ));

        $length--;

    }

    return $result;

}

 

$numbers = [1,2,3,4];

$result = get_all_combinations($numbers);

echo 'START: '.json_encode( $numbers ).'<br><br>';

echo 'RESULT: '.json_encode( $result ).'<br><br>';

echo '('.count($result).' combination subsets found)';

 

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

Web

Как экранировать строки в SQL Server с помощью PHP

Web

Как узнать, установлен ли флажок в PHP

Web

PHP – статические свойства

Web

PHP + curl, пример кода HTTP POST