PHP查找数组的所有(某种程度上)唯一组合 - PHP Find All (somewhat) Unique Combinations of an Array

我整天都在看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没有顺序重复?
从n
查找数组中元素的组合和，其和等于给定数字
如何在PHP返回数组的排列?
排列-所有可能的数字集合
从数组中找到唯一的值组合，过滤掉任何重复的对
查找字符串的所有唯一排列而不生成重复
生成所有唯一的排列
恰好k个整数的子集和?

我已经尝试了这些算法中的一些与12项的数组，并最终耗尽内存。然而，我目前使用的算法不会给我一个内存不足的错误....但. .我需要那些副本!

如果你不介意使用几个全局变量，你可以在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 ) )

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

为什么不直接使用二进制呢?至少它很简单，很容易理解每一行代码是做什么的，像这样?这是我在一个项目中为自己写的一个函数，我认为它非常整洁!

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

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

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，调用梳子(2,3)将产生:

0 1
0 2
1 2

它给你索引位置，所以很容易通过索引指向数组元素。

Edit:输入梳子失败(30,5)。不知道为什么，有人知道吗?

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

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;
}

这个想法很简单。假设你知道如何排列，那么如果你把这些排列保存在一个集合中，它就变成了一个组合。Set按定义处理重复的值。Php中与Set或HashSet对应的对象是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;
      }