# PHP Find All (somewhat) Unique Combinations of an Array

Viewed   121 times

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!

2

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 (  => Array (  => 20
 => 20
 => 22 )
 => Array (  => 20
 => 20
 => 24 )
 => Array (  => 20
 => 22
 => 24 )
 => Array (  => 20
 => 22
 => 24 ) )
``````
Wednesday, November 2, 2022

4

I had a similar requirement some years ago. I do not remember why and I no longer have the code but I do remember the algorithm. For me this was a one-off exercise so I wanted an easy code. I did not care about efficiency.

I will assume one-based arrays because it makes for a marginally easier explanation. Since VBA supports one-based arrays, this should be OK although it is an easy adjustment to zero-based arrays if that is what you want.

AllFields(1 To NumFields) holds the names.

Have a Loop: For Inx = 1 To 2^NumFields - 1

Within the loop consider Inx as a binary number with bits numbered 1 to NumFields. For each N between 1 and NumFields, if bit N is one include AllFields(N) in this combination.

This loop generates the 2^NumFields - 1 combinations:

``````Names: A B C

Inx:          001 010 011 100 101 110 111

CombinationS:   C  B   BC A   A C AB  ABC
``````

The only difficulty with VBA is getting the value of Bit N.

Extra section

With everyone having at go at implementing bits of my algorithm, I thought I had better show how I would have done it.

I have filled an array of test data with an nasty set of field names since we have not been told what characters might be in a name.

The subroutine GenerateCombinations does the business. I am a fan of recursion but I do not think my algorithm is complicated enough to justify its use in this case. I return the result in a jagged array which I prefer to concatenation. The output of GenerateCombinations is output to the immediate window to demonstrate its output.

``````Option Explicit
``````

This routine demonstrates GenerateCombinations

``````Sub Test()

Dim InxComb As Integer
Dim InxResult As Integer
Dim TestData() As Variant
Dim Result() As Variant

TestData = Array("A A", "B,B", "C|C", "D;D", "E:E", "F.F", "G/G")

Call GenerateCombinations(TestData, Result)

For InxResult = 0 To UBound(Result)
Debug.Print Right("  " & InxResult + 1, 3) & " ";
For InxComb = 0 To UBound(Result(InxResult))
Debug.Print "[" & Result(InxResult)(InxComb) & "] ";
Next
Debug.Print
Next

End Sub
``````

``````Sub GenerateCombinations(ByRef AllFields() As Variant, _
ByRef Result() As Variant)

Dim InxResultCrnt As Integer
Dim InxField As Integer
Dim InxResult As Integer
Dim I As Integer
Dim NumFields As Integer
Dim Powers() As Integer
Dim ResultCrnt() As String

NumFields = UBound(AllFields) - LBound(AllFields) + 1

ReDim Result(0 To 2 ^ NumFields - 2)  ' one entry per combination
ReDim Powers(0 To NumFields - 1)          ' one entry per field name

' Generate powers used for extracting bits from InxResult
For InxField = 0 To NumFields - 1
Powers(InxField) = 2 ^ InxField
Next

For InxResult = 0 To 2 ^ NumFields - 2
' Size ResultCrnt to the max number of fields per combination
' Build this loop's combination in ResultCrnt
ReDim ResultCrnt(0 To NumFields - 1)
InxResultCrnt = -1
For InxField = 0 To NumFields - 1
If ((InxResult + 1) And Powers(InxField)) <> 0 Then
' This field required in this combination
InxResultCrnt = InxResultCrnt + 1
ResultCrnt(InxResultCrnt) = AllFields(InxField)
End If
Next
ReDim Preserve ResultCrnt(0 To InxResultCrnt)
' Store this loop's combination in return array
Result(InxResult) = ResultCrnt
Next

End Sub
``````
Tuesday, October 11, 2022

3

A recursive solution.

``````<?php
function combination(\$remaining, \$current, \$combinations) {
\$e = array_shift(\$remaining);
\$combinations[\$current][] = \$e;

if(empty(\$remaining)) {
print_r(\$combinations);
return;
}

combination(\$remaining, \$current, \$combinations);
// 6 Limit remove for all solutions
if (\$current < 6) {
combination(\$remaining, \$current + 1, \$combinations);
}
}

\$remaining = range(0, 23);

combination(\$remaining, 0, array());
``````

If you want to store all solutions for [0,23] you're gonna have a bad time.

Friday, August 19, 2022

4

Simplest solution : binary conversion, no recursion

``````for(int i = 0; i < 16: ++i) {
printf("%u%u%u%u", i/8%2, i/4%2, i/2%2, i%2);
}
``````

See MOHAMED's answer for a recursive version of this loop

Binary recursion used by the following solutions

``````          _ 000
_ 00 _/
/      _ 001
0        _ 010
_ 01 _/
_ 011
_ 100
_ 10 _/
/      _ 101
1        _ 110
_ 11 _/
_ 111
``````

Recursive solution using `char*` buffer, no binary conversion

``````void char_buffer_rec(char number, int n) {
if(n > 0) {
number[4-n] = '0';
char_buffer_rec(number, n - 1);
number[4-n] = '1';
char_buffer_rec(number, n - 1);
}
else {
printf("%sn", number);
}
}
``````

usage :

``````char number = {0};
char_buffer_rec(number, 4);
``````

Recursive solution using only `int`, no buffer, no binary conversion

``````void int_ten_rec(int number, int tenpower) {
if(tenpower > 0) {
int_ten_rec(number, tenpower/10);
int_ten_rec(number + tenpower, tenpower/10);
}
else {
printf("%04un", number);
}
}
``````

usage :

``````int_ten_rec(0, 1000);
``````

Another version of this solution replacing `tenpower` width `bitwidth`, replacing the printf `width` with a variable padding depending on the length variable. `length` could be defined as a new parameter, a program constant, etc.

``````void int_rec(int number, int bitwidth) {
static int length = bitwidth;
int i, n;
if(bitwidth > 0) {
int_rec(number, bitwidth-1);
/* n := 10^(bitwidth-2) */
for(i=0,n=1;i<bitwidth-1;++i,n*=10);
int_rec(number + n, bitwidth-1);
}
else {
/* i := number of digit in 'number' */
for(i=1,n=number;n>=10;++i,n/=10);
/* print (length-i) zeros */
for(n=i; n<length; ++n) printf("0");
printf("%un", number);
}
}
``````

usage :

``````int_rec(0, 4);
``````

Tree Solution, recursive using `char*` buffer, no binary conversion

``````struct Node {
int val;
struct Node *left, *right;
};

void build_tree(struct Node* tree, int n) {
if(n > 0) {
tree->left = (Node*)malloc(sizeof(Node));
tree->right= (Node*)malloc(sizeof(Node));
tree->left->val = 0;
build_tree(tree->left, n - 1);
tree->right->val = 1;
build_tree(tree->right, n - 1);
}
else {
tree->left = tree->right = NULL;
}
}

void print_tree(struct Node* tree, char* buffer, int index) {
if(tree->left != NULL && tree->right != NULL) {
sprintf(buffer+index, "%u", tree->val);
print_tree(tree->left, buffer, index+1);
sprintf(buffer+index, "%u", tree->val);
print_tree(tree->right, buffer, index+1);
}
else {
printf("%s%un", buffer, tree->val);
}
}
``````

usage :

``````    char buffer = {0};
Node* tree = (Node*)malloc(sizeof(Node));
tree->val = 0;
build_tree(tree, 4);
print_tree(tree, buffer, 0);
``````

But this would print an additional `0` at the begining of each line, to avoid this, build two smaller trees :

``````    Node* tree0 = (Node*)malloc(sizeof(Node));
Node* tree1 = (Node*)malloc(sizeof(Node));
tree0->val = 0;
tree1->val = 1;
build_tree(tree0, 3);
build_tree(tree1, 3);
print_tree(tree0, buffer, 0);
print_tree(tree1, buffer, 0);
``````

Recursive solution using int* array

``````#define MAX_LENGTH 32
int number[MAX_LENGTH];
void int_buffer_rec(int n, int length) {
if(n > 0) {
number[length - n] = 0;
int_buffer_rec(n - 1, length);
number[length - n] = 1;
int_buffer_rec(n - 1, length);
}
else {
for(int i = 0; i < length; ++i) {
printf("%u", number[i]);
}
printf("n");
}
}
``````

usage :

``````int_buffer_rec(4, 4);
``````
Thursday, September 15, 2022

2

Fast solution using recursion, probably not the best way to do it, but it gets the job done.

``````<?php

\$arr = array(1,2,3);
\$result = array();

function combinations(\$arr, \$level, &\$result, \$curr=array()) {
for(\$i = 0; \$i < count(\$arr); \$i++) {
\$new = array_merge(\$curr, array(\$arr[\$i]));
if(\$level == 1) {
sort(\$new);
if (!in_array(\$new, \$result)) {
\$result[] = \$new;
}
} else {
combinations(\$arr, \$level - 1, \$result, \$new);
}
}
}
for (\$i = 0; \$i<count(\$arr); \$i++) {
combinations(\$arr, \$i+1, \$result);
}

// TEST
foreach (\$result as \$arr) {
echo join(" ", \$arr) . '<br>';
}

?>
``````
Tuesday, August 9, 2022