将采用数字或单词并找到所有可能组合的算法

Question

我正在寻找一种算法,它将采用数字或单词并找到它们的所有可能变体,并让我定义要一起查找的值.

示例假设字符串或数组是:

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(死链接)

Answer 1

看看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

Answer 2

如果你正在寻找这样的东西是如何工作的,这就是我用没有使用二进制文件的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;
}