Алгоритм, который будет принимать числа или слова и находить все возможные комбинации

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

Пример позволяет сказать, что строка или массив:

cat  
dog  
fish

тогда результаты для значения 2 могут быть:

cat dog  
cat fish  
dog cat  
dog fish  
fish cat  
fish dog

Таким образом, результаты из набора из 3 пунктов - это 6 возможных вариаций при совпадении 2 результатов
при совпадении 3 результатов это будет:

cat dog fish  
cat fish dog  
dog cat fish  
dog fish cat  
fish cat dog  
fish dog cat

... возможно, даже больше вариантов

Я нашел ссылку на Stackru на этот пример, который делает это, но это в javascript, мне интересно, если кто-нибудь знает, как это сделать в PHP, может быть, есть что-то уже построено?

http://www.merriampark.com/comb.htm (неработающая ссылка)

Источник

3 ответа

Решение

Take a look at http://pear.php.net/package/Math_Combinatorics

<?php
require_once 'Math/Combinatorics.php';
$words = array('cat', 'dog', 'fish');
$combinatorics = new Math_Combinatorics;
foreach($combinatorics->permutations($words, 2) as $p) {
  echo join(' ', $p), "\n"; 
}

печать

cat dog
dog cat
cat fish
fish cat
dog fish
fish dog
Источник

Если вы ищете, как что-то вроде этого работает, вот как я это сделал без библиотек php, использующих бинарный файл.

function search_get_combos($query){
$list = explode(" ", $query);
$bits = count($list); //bits of binary number equal to number of words in query;
//Convert decimal number to binary with set number of bits, and split into array
$dec = 1;
$binary = str_split(str_pad(decbin($dec), $bits, '0', STR_PAD_LEFT));
while($dec < pow(2, $bits)) {
    //Each 'word' is linked to a bit of the binary number.
    //Whenever the bit is '1' its added to the current term.
    $curterm = "";
    $i = 0;
    while($i < ($bits)){
        if($binary[$i] == 1) {
            $curterm .= $list[$i]." ";
        }
        $i++;
    }
    $terms[] = $curterm;
    //Count up by 1
    $dec++;
    $binary = str_split(str_pad(decbin($dec), $bits, '0', STR_PAD_LEFT));
}
return $terms;
}

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

Array
(
    [0] => fish 
    [1] => dog 
    [2] => dog fish 
    [3] => cat 
    [4] => cat fish 
    [5] => cat dog 
    [6] => cat dog fish 
)

Редактировать (больше уточнений)

Основная теория

Итак, во-первых, двоичные числа, как вы, вероятно, знаете, представляют собой строку из 1 и 0. Длина числа - это количество битов, которое оно имеет, например. число 011001 имеет 6 бит (цифры 25, если вы заинтересованы). Затем, если каждый бит числа соответствует одному из терминов, каждый раз, когда он считает, если бит равен 1, термин включается в вывод, тогда как если он равен 0, он игнорируется. Так что это основная теория того, что происходит.

Копаться в коде

У PHP нет возможности считать в двоичном формате, но вы можете преобразовать десятичные дроби в двоичные. Таким образом, эта функция на самом деле считает в десятичном виде и преобразует это в двоичный. Но так как количество битов важно, так как каждому члену нужен свой собственный бит, вам нужно добавить начальные 0, вот что делает этот бит: str_pad(decbin($dec), $bits, '0', STR_PAD_LEFT)

Теперь эта функция использует цикл while, но, поскольку количество циклов, необходимых для изменения цикла, зависит от количества терминов, необходимо выполнить некоторые математические операции. Если вы когда-либо работали с двоичным файлом, вы будете знать, что максимальное число, которое вы можете сделать, равно 2^n (где n - количество бит).

Я думаю, что это должно было покрыть все запутанные части функции, дайте мне знать, если я что-то пропустил.

Посмотри что происходит

Используйте следующий код для вывода используемой логики, это может иметь немного больше смысла, видя это таким образом!

function search_get_combos_demo($query){
    $list = explode(" ", $query);
    $bits = count($list);
    $dec = 1;
    while($dec < pow(2, $bits)) {
        $binary = str_split(str_pad(decbin($dec), $bits, '0', STR_PAD_LEFT));
        $curterm = "";
        $i = 0;
        while($i < ($bits)){
            if($binary[$i] == 1) {
                $curterm[] = $list[$i]." ";
            }
            $i++;
        }
        //-----DISPLAY PROCESS-----//
        echo "Iteration: $dec <table cellpadding=\"5\" border=\"1\"><tr>";
        foreach($binary as $b){
            echo "<td>$b</td>";
        }
        echo "</tr><tr>";
        foreach($list as $l){
            echo "<td>$l</td>";
        }
        echo "</tr></table>Output: ";
        foreach($curterm as $c){
            echo $c." ";
        }
        echo "<br><br>";
        //-----END DISPLAY PROCESS-----//
        $terms[] = $curterm;
        $dec++;
    }
    return $terms;
}
Источник

Вы можете попробовать этот открытый исходный код для этого. Он реализует итератор. Нажмите

Доступно на PHP, Java.

Вы должны продлить это.

Источник
Другие вопросы по тегам