PHP Find All (somewhat) Unique Combinations of an

2019-01-14 18:45发布

站内文章 / PHP

66 0

女痞

女 | 书童

私信

可以将文章内容翻译成中文,广告屏蔽插件可能会导致该功能失效(如失效，请关闭广告屏蔽插件后再试):

问题:

I've been looking at PHP array permutation / combination questions all day.. and still can't figure it out :/

If I have an array like:

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

I need combinations like:

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

The code I currently have gives me:

20, 22, 24

because it doesn't want to repeat 20... but that's what I need!

Here is the code I have. it is directly from Php recursion to get all possibilities of strings

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;


}

I've been playing around with the ($b == $lastEl) line, with no luck

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

Questions I've already looked at, and are not the same OR that created an out of memory error!:

How can I get all permutations in PHP without sequential duplicates?
Permutations - all possible sets of numbers
Combinations, Dispositions and Permutations in PHP
PHP array combinations
Get all permutations of a PHP array?
PHP: How to get all possible combinations of 1D array?
Select only unique array values from this array
Get all permutations of a PHP array?
PHP: How to get all possible combinations of 1D array?
Select only unique array values from this array
How can I get all permutations in PHP without sequential duplicates?
Algorithm to return all combinations of k elements from n
Find combination(s) sum of element(s) in array whose sum equal to a given number
Combinations, Dispositions and Permutations in PHP
PHP array combinations
Php recursion to get all possibilities of strings
How to return permutations of an array in PHP?
Permutations - all possible sets of numbers
Subset-sum problem in PHP with MySQL
Find unique combinations of values from arrays filtering out any duplicate pairs
Finding all the unique permutations of a string without generating duplicates
Generate all unique permutations
Subset sum for exactly k integers?

I've tried some of these algorithms with an array of 12 items, and end up running out of memory. However the algorithm that I'm currently using doesn't give me an out of memory error.... BUT.. I need those duplicates!

回答1:

If you don't mind using a couple of global variables, you could do this in PHP (translated from a version in 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));
?>

OUTPUT:

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

回答2:

The pear package Math_Combinatorics makes this kind of problem fairly easy. It takes relatively little code, it's simple and straightforward, and it's pretty easy to read.

$ 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

If I had to package this as a function, I'd do something like this.

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

That will return an array of arrays. To get the text . . .

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

回答3:

If you are looking unique combinations, which from your test case of 4 choose 3: 0 1 2 0 1 3 0 2 3 1 2 3

then your problem falls under the binomial coefficient.

I have written a class in C# to handle common functions for working with the binomial coefficient which is categorized by the formula n! / (n! * (n-k)!), where n is the number of items and k is the number to group them by. It performs the following tasks:

Outputs all the K-indexes in a nice format for any N choose K to a file. The K-indexes can be substituted with more descriptive strings or letters.
Converts the K-indexes to the proper lexicographic index or rank of an entry in the sorted binomial coefficient table. This technique is much faster than older published techniques that rely on iteration. It does this by using a mathematical property inherent in Pascal's Triangle and is very efficient compared to iterating over the set.
Converts the index in a sorted binomial coefficient table to the corresponding K-indexes. I believe it is also faster than older iterative solutions.
Uses Mark Dominus method to calculate the binomial coefficient, which is much less likely to overflow and works with larger numbers.
The class is written in .NET C# and provides a way to manage the objects related to the problem (if any) by using a generic list. The constructor of this class takes a bool value called InitTable that when true will create a generic list to hold the objects to be managed. If this value is false, then it will not create the table. The table does not need to be created in order to use the 4 above methods. Accessor methods are provided to access the table.
There is an associated test class which shows how to use the class and its methods. It has been extensively tested with 2 cases and there are no known bugs.

To read about this class and download the code, see Tablizing The Binomial Coeffieicent.

The following tested code will iterate through each unique combination:

public void Test10Choose5()
{
   String S;
   int Loop;
   int N = 10;  // Total number of elements in the set.
   int K = 5;  // Total number of elements in each group.
   // Create the bin coeff object required to get all
   // the combos for this N choose K combination.
   BinCoeff<int> BC = new BinCoeff<int>(N, K, false);
   int NumCombos = BinCoeff<int>.GetBinCoeff(N, K);
   // The Kindexes array specifies the indexes for a lexigraphic element.
   int[] KIndexes = new int[K];
   StringBuilder SB = new StringBuilder();
   // Loop thru all the combinations for this N choose K case.
   for (int Combo = 0; Combo < NumCombos; Combo++)
   {
      // Get the k-indexes for this combination.  
      BC.GetKIndexes(Combo, KIndexes);
      // Verify that the Kindexes returned can be used to retrive the
      // rank or lexigraphic order of the KIndexes in the table.
      int Val = BC.GetIndex(true, KIndexes);
      if (Val != Combo)
      {
         S = "Val of " + Val.ToString() + " != Combo Value of " + Combo.ToString();
         Console.WriteLine(S);
      }
      SB.Remove(0, SB.Length);
      for (Loop = 0; Loop < K; Loop++)
      {
         SB.Append(KIndexes[Loop].ToString());
         if (Loop < K - 1)
            SB.Append(" ");
      }
      S = "KIndexes = " + SB.ToString();
      Console.WriteLine(S);
   }
}

You should be able to port this class over fairly easily to PHP. You probably will not have to port over the generic part of the class to accomplish your goals. Depending on the number of combinations you are working with, you might need to use a bigger word size than 4 byte ints. You should define an array or list with your objects of interest and then simply index that array with each element in the k-indexes.

回答4:

The Idea is simple. Suppose you know how to permute, then if you save these permutations in a set it becomes a combinations. Set by definition takes care of the duplicate values. The Php euqivalent of Set or HashSet is SplObjectStorage and ArrayList is Array. It should not be hard to rewrite. I have an implementation in 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;
      }

回答5:

Why not just use binary? At least then its simple and very easy to understand what each line of code does like this? Here's a function i wrote for myself in a project which i think is pretty neat!

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

For your example, this outputs:

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

回答6:

Had the same problem and found a different and bitwise, faster solution:

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

This one generates all size m combinations of the integers from 0 to n-1, so for example m = 2, n = 3 and calling comb(2, 3) will produce:

0 1
0 2
1 2

It gives you index positions, so it's easy to point to array elements by index.

Edit: Fails with input comb(30, 5). Have no idea why, anyone any idea?

回答7:

Cleaned up Adi Bradfield's sugestion using strrev and for/foreach loops, and only get unique results.

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