Вопрос по php, algorithm, permutation – алгоритм, который будет принимать цифры или слова и находить все возможные комбинации

14

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

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

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  

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

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

http://www.merriampark.com/comb.htm (мертвая ссылка)

ссылка на JavaScript не работает Timo Huovinen

Ваш Ответ

3   ответа
13

Если вы ищете, как что-то вроде этого работает, вот как я это сделал без библиотек 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 's. Длина числа - это числобиты это имеет, например. число011001 имеет 6 бит (цифры 25, если вы заинтересованы). Затем, если каждый бит числа соответствует одному из терминов, каждый раз, когда он считает, если бит равен 1, термин включается в вывод, тогда как если онs 0, он игнорируется. Так вот основная теория того, чтопроисходит

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

У PHP нет возможности считать в двоичном формате, но вы можете преобразовать десятичные числа в двоичные. Таким образом, эта функция на самом деле считает в десятичном виде и преобразует это в двоичный. Но так как количество битов важно, так как каждому члену нужен свой собственный бит, необходимо добавить начальный 0 's, вот что делает этот бит: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 ";
        foreach($binary as $b){
            echo "$b";
        }
        echo "";
        foreach($list as $l){
            echo "$l";
        }
        echo "Output: ";
        foreach($curterm as $c){
            echo $c." ";
        }
        echo "<br><br>";
        //-----END DISPLAY PROCESS-----//
        $terms[] = $curterm;
        $dec++;
    }
    return $terms;
}
Да! это определенно так. Timo Huovinen
StackOverflow хорош в этом смысле, он позволяет вам хранить фрагменты рабочего кода и делиться им со всеми, я часто получаю код, который не нужен ни в одном из моих активных проектов, но я могу вернуться к нему, настроить его и начинает жить снова. Timo Huovinen
@TimoHuovinen Проблема в том, что я подумал об этом, но теперь я должен это отменить, так какв моем коде стало лишним! Не берите в голову, я мог бы найти использование для этого однажды! Adi Bradfield
@TimoHuovinen Пятно на! Изящный нетне так ли? Adi Bradfield
23

Взгляни наhttp://pear.php.net/package/Math_Combinatorics

permutations($words, 2) as $p) {
  echo join(' ', $p), "\n"; 
}

печать

cat dog
dog cat
cat fish
fish cat
dog fish
fish dog
Это потрясающе, спасибо за информацию, знаете ли вы, в чем разница между этими двумя комбинациями $ и $ permutations в примере сценария? JasonDavis
Кстати, вы можете скопироватьMath_Combinatronics отВот на нём всё работаетс собственными Timo Huovinen
В перестановках учитывается порядок элементов, в комбинациях порядок не имеет значения. Например. (кошка, собака) и (собака, кошка) оба включены в результат перестановок (), в то время как результат комбинаций () будет включать только одну из них, вторая считается равной. VolkerK
Очень хорошая груша, яЯ буду использовать его в будущем. Alix Axel
0

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

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

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

Это ответ только для ссылок (и ссылки могут умереть). Пожалуйста, удалите этот ответ и оставьте комментарий. mickmackusa

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