PHP Find All (somewhat) Unique Combinations of an Array

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

GenerateCombinations does the business.

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
    ' Discard unused trailing entries
    ReDim Preserve ResultCrnt(0 To InxResultCrnt)
    ' Store this loop's combination in return array
    Result(InxResult) = ResultCrnt
  Next

End Sub

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[4], 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[5] = {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[5] = {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);