16

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

示例可以说字符串或数组是： 

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（死链接）

4

2 回答 2

24

看看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
于 2009-08-10T17:25:05.087 回答
15

如果您正在寻找这样的东西是如何工作的，这就是我在没有使用二进制文件的 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;
}
于 2013-06-12T19:53:42.620 回答