php - PHP查找数组的所有（有点）唯一组合

Question

我整天都在研究 PHP 数组排列/组合问题.. 仍然无法弄清楚：/

如果我有一个像这样的数组：

20 //key being 0    
20 //key being 1    
22 //key being 2    
24 //key being 3

我需要这样的组合：

20, 20, 22 //keys being 0 1 2    
20, 20, 24 //keys being 0 1 3    
20, 22, 24 //keys being 0 2 3
20, 22, 24 //keys being 1 2 3

我目前拥有的代码给了我：

20, 22, 24

因为它不想重复 20 次……但这就是我所需要的！

这是我的代码。直接从php递归得到字符串的所有可能

function getCombinations($base,$n){

$baselen = count($base);
if($baselen == 0){
    return;
}
    if($n == 1){
        $return = array();
        foreach($base as $b){
            $return[] = array($b);
        }
        return $return;
    }else{
        //get one level lower combinations
        $oneLevelLower = getCombinations($base,$n-1);

        //for every one level lower combinations add one element to them that the last element of a combination is preceeded by the element which follows it in base array if there is none, does not add
        $newCombs = array();

        foreach($oneLevelLower as $oll){

            $lastEl = $oll[$n-2];
            $found = false;
            foreach($base as  $key => $b){
                if($b == $lastEl){
                    $found = true;
                    continue;
                    //last element found

                }
                if($found == true){
                        //add to combinations with last element
                        if($key < $baselen){

                            $tmp = $oll;
                            $newCombination = array_slice($tmp,0);
                            $newCombination[]=$b;
                            $newCombs[] = array_slice($newCombination,0);
                        }

                }
            }

        }

    }

    return $newCombs;


}

我一直在玩这($b == $lastEl)条线，没有运气

================

我已经看过的问题与创建内存不足错误的问题不同！：

• 如何在没有顺序重复的情况下获得 PHP 中的所有排列？
• 排列 - 所有可能的数字集
• PHP 中的组合、配置和排列
• PHP数组组合
• 获取 PHP 数组的所有排列？
• PHP：如何获得一维数组的所有可能组合？
• 从此数组中仅选择唯一的数组值
• 获取 PHP 数组的所有排列？
• PHP：如何获得一维数组的所有可能组合？
• 从此数组中仅选择唯一的数组值
• 如何在没有顺序重复的情况下获得 PHP 中的所有排列？
• 从 n 返回 k 个元素的所有组合的算法
• 在数组中查找总和等于给定数字的元素的组合和
• PHP 中的组合、配置和排列
• PHP数组组合
• php递归获取字符串的所有可能性
• 如何在 PHP 中返回数组的排列？
• 排列 - 所有可能的数字集
• 使用 MySQL 的 PHP 中的子集和问题
• 从过滤掉任何重复对的数组中查找唯一的值组合
• 查找字符串的所有唯一排列而不生成重复项
• 生成所有唯一排列
• 恰好k个整数的子集总和？

我已经用 12 个项目的数组尝试了其中一些算法，但最终内存不足。然而，我目前使用的算法并没有给我一个内存不足的错误....但是..我需要那些重复的！

Answer 1

如果您不介意使用几个全局变量，您可以在 PHP 中执行此操作（从JavaScript版本翻译）：

<?PHP
$result = array(); 
$combination = array();

function combinations(array $myArray, $choose) {
  global $result, $combination;

  $n = count($myArray);

  function inner ($start, $choose_, $arr, $n) {
    global $result, $combination;

    if ($choose_ == 0) array_push($result,$combination);
    else for ($i = $start; $i <= $n - $choose_; ++$i) {
           array_push($combination, $arr[$i]);
           inner($i + 1, $choose_ - 1, $arr, $n);
           array_pop($combination);
         }
  }
  inner(0, $choose, $myArray, $n);
  return $result;
}

print_r(combinations(array(20,20,22,24), 3));
?>

输出：

Array ( [0] => Array ( [0] => 20 
                       [1] => 20 
                       [2] => 22 ) 
        [1] => Array ( [0] => 20 
                       [1] => 20 
                       [2] => 24 ) 
        [2] => Array ( [0] => 20 
                       [1] => 22 
                       [2] => 24 ) 
        [3] => Array ( [0] => 20 
                       [1] => 22 
                       [2] => 24 ) ) 

Answer 2

pear 包 Math_Combinatorics 使这类问题变得相当容易。它需要的代码相对较少，简单明了，而且很容易阅读。

$ cat code/php/test.php
<?php
$input = array(20, 20, 22, 24);

require_once 'Math/Combinatorics.php';

$c = new Math_Combinatorics;
$combinations = $c->combinations($input, 3);
for ($i = 0; $i < count($combinations); $i++) {
  $vals = array_values($combinations[$i]);
  $s = implode($vals, ", ");
  print $s . "\n";
}
?>

$ php code/php/test.php
20, 20, 22
20, 20, 24
20, 22, 24
20, 22, 24

如果我必须把它打包成一个函数，我会做这样的事情。

function combinations($arr, $num_at_a_time) 
{
    include_once 'Math/Combinatorics.php';

    if (count($arr) < $num_at_a_time) {
        $arr_count = count($arr);
        trigger_error(
            "Cannot take $arr_count elements $num_at_a_time " 
            ."at a time.", E_USER_ERROR
        );
    }

    $c = new Math_Combinatorics;
    $combinations = $c->combinations($arr, $num_at_a_time);

    $return = array();
    for ($i = 0; $i < count($combinations); $i++) {
        $values = array_values($combinations[$i]);
        $return[$i] = $values;
    }
    return $return;
}

这将返回一个数组数组。获取文本。. .

<?php
  include_once('combinations.php');

  $input = array(20, 20, 22, 24);
  $output = combinations($input, 3);

  foreach ($output as $row) {
      print implode($row, ", ").PHP_EOL;
  }
?>
20, 20, 22
20, 20, 24
20, 22, 24
20, 22, 24

Answer 3

为什么不只使用二进制？至少那么它简单且很容易理解每​​一行代码的作用是这样的吗？这是我在一个项目中为自己编写的一个函数，我认为它非常简洁！

function search_get_combos($array){
$bits = count($array); //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[] = $array[$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] => Array
        (
            [0] => 24 
        )
    [1] => Array
        (
            [0] => 22 
        )
    [2] => Array
        (
            [0] => 22 
            [1] => 24 
        )
    [3] => Array
        (
            [0] => 20 
        )
    [4] => Array
        (
            [0] => 20 
            [1] => 24 
        )
    [5] => Array
        (
            [0] => 20 
            [1] => 22 
        )
    [6] => Array
        (
            [0] => 20 
            [1] => 22 
            [2] => 24 
        )
    [7] => Array
        (
            [0] => 20 
        )
    [8] => Array
        (
            [0] => 20 
            [1] => 24 
        )
    [9] => Array
        (
            [0] => 20 
            [1] => 22 
        )
    [10] => Array
        (
            [0] => 20 
            [1] => 22 
            [2] => 24 
        )
    [11] => Array
        (
            [0] => 20 
            [1] => 20 
        )
    [12] => Array
        (
            [0] => 20 
            [1] => 20 
            [2] => 24 
        )
    [13] => Array
        (
            [0] => 20 
            [1] => 20 
            [2] => 22 
        )
    [14] => Array
        (
            [0] => 20 
            [1] => 20 
            [2] => 22 
            [3] => 24 
        )
)

Answer 4

使用 strrev 和 for/foreach 循环清理了 Adi Bradfield 的建议，并且只得到独特的结果。

function search_get_combos($array = array()) {
sort($array);
$terms = array();

for ($dec = 1; $dec < pow(2, count($array)); $dec++) {
    $curterm = array();
    foreach (str_split(strrev(decbin($dec))) as $i => $bit) {
        if ($bit) {
            $curterm[] = $array[$i];
        }
    }
    if (!in_array($curterm, $terms)) {
        $terms[] = $curterm;
    }
}

return $terms;
}

Answer 5

遇到了同样的问题，并找到了一个不同的、按位更快的解决方案：

function bitprint($u) {
    $s = array();
    for ($n=0; $u; $n++, $u >>= 1){
        if ($u&1){
            $s [] = $n;
        }
    }
    return $s;
}
function bitcount($u) {
    for ($n=0; $u; $n++, $u = $u&($u-1));
    return $n;
}
function comb($c,$n) {
    $s = array();
    for ($u=0; $u<1<<$n; $u++){
        if (bitcount($u) == $c){
            $s [] = bitprint($u);
        }
    }
    return $s;
}

这会生成从 0 到 n-1 的所有大小为 m 的整数组合，因此例如 m = 2, n = 3 并调用 comb(2, 3) 将产生：

0 1
0 2
1 2

它为您提供索引位置，因此很容易通过索引指向数组元素。

编辑：输入 comb(30, 5) 失败。不知道为什么，有人知道吗？

Answer 6

这个想法很简单。假设你知道如何排列，那么如果你将这些排列保存在一个集合中，它就会变成一个组合。按定义设置会处理重复值。Set 或 HashSet 的 Php 等价物是 SplObjectStorage，而 ArrayList 是 Array。重写应该不难。我有一个Java实现：

public static HashSet<ArrayList<Integer>> permuteWithoutDuplicate(ArrayList<Integer> input){
          if(input.size()==1){
              HashSet<ArrayList<Integer>> b=new HashSet<ArrayList<Integer>>();
              b.add(input);
              return b;
          }
          HashSet<ArrayList<Integer>>ret= new HashSet<ArrayList<Integer>>();
          int len=input.size();
          for(int i=0;i<len;i++){
              Integer a = input.remove(i);
              HashSet<ArrayList<Integer>>temp=permuteWithoutDuplicate(new ArrayList<Integer>(input));
              for(ArrayList<Integer> t:temp)
                  t.add(a);
              ret.addAll(temp);
              input.add(i, a);
          }
          return ret;
      }