Generate all possible combinations

Question

I have an app where users can customize the product they are going to purchase by choosing options from a menu. This menu has many sections, and each section may have a list of checkboxes for multichoice, or radiobuttons when only one option can be selected. The user must select at least one option in each section. The menu structure is something like this:

$sections = array();

$sections[1] = array(
    'multichoice' => true,
    'options' => array('A','B','C')
);

$sections[2] = array(
    'multichoice' => false,
    'options' => array('A','B','C','D')
);

$sections[3] = array(
    'multichoice' => false,
    'options' => array('A','B')
);

$sections[4] = array(
    'multichoice' => true,
    'options' => array('A','B','C','D','E')
);

Example: Sandwich is the product. Type of bread is one "section" of choice. You may want light bread, dark bread, milk bread or vegan bread. Only one option can be chosen under this section. Now in the "salad" section, you may choose more than one type of salad to add to the bread.

Now, my boss asked for me to create a page listing all possible combinations in case the user is too lazy to build the product himself. So I must be able to generate a structure like this:

$combinations = array(
    array(
        1 => array('A','B'),
        2 => 'A',
        3 => 'A',
        4 => array('B','D','E')
    ),
    array(
        1 => array('A'),
        2 => 'B',
        3 => 'A',
        4 => array('A','B')
    )
// etc...
);

I have managed to find all possible combinations using a random approach, generating hashes for comparision with what has already been generated. This actually works, but runs very slowly (this is brute-force basically):

...

function generate(){
    $result = array();
    $ids = array();
    foreach($this->getSections() as $sect){
        $items = $this->getSectionOptions($sect['id']);
        if($sect['multi']=='N'){
            $item = $items[rand(0, count($items)-1)];
            $result[$sect['id']] = $item['id'];
            $ids[] = $item['id'];
        } else {
            $how_many = rand(1,count($items));
            shuffle($items);
            for($i=1;$i<=$how_many;$i++){
                $item = array_shift($items);
                $result[$sect['id']][] = $item['id'];
                $ids[] = $item['id'];
            }
        }
    }
    sort($ids);
    return array(
        'hash' => implode(',',$ids),
        'items' => $result
    );
}

function generateMany($attempts=1000){
    $result = array();
    $hashes = array();
    for($i=1;$i<=$attempts;$i++){
        $combine = $this->generate();
        if(!in_array($combine['hash'],$hashes)){
            $result[] = $combine['items'];
            $hashes[] = $combine['hash'];
        }
    }
    return $result;
}


...

I want your help to create something more precise and faster. Remember that each combination must have at least one option of each section. And also keep in mind that the order of options in multichoice sections is irrelevant, (i.e. E,B,A is the same as B,E,A)

Thanks

Answer 1

Thanks this was a puzzle really fun to do!

So how did I solve, recursion recursion recursion :D

I've started with the multi choice since it is the hardest one! (and actually it will solve also the mixing)

Explanation

To explain how I got it to work, lets take an example with choices A, B, C. We would have then the following combinations:

A B
A B C
A C
B
B C
C

If we take a look closer, we can see some how a pattern. Lets take the result list the first element (A)

B
B C
C
---
B
B C
C

Hmm, interesting... Now lets take again the first element (B)

C
---
C

It's a simple case but this will happen in any size case.

So I've made the recursion script to get to the end, then adding backwards, the iteration combination and duplicating it with the previous value.

And voila! this is it!

For the final mix where all the elements are demanded, I've made a very similar method, but it must contain 1 element of each

And it's quite fast!

Total time for 100000 iterations with 126 combinations: 14.410287857056 seconds

if you find any mistake ping me :D

Code

https://gist.github.com/MLoureiro/a0ecd1ef477e08b6b83a