How to generate all possible combinations using one value from each sub-array in PHP?

Question

I have an apparently easy task, but I'm stuck. I tried restructures and iterators, but no ideas struck me. They say a picture's worth a thousand words, so I'll show my 'picture' example array:

array (size=4)
  0 =>
    array (size=4)
      0 => int 1
      1 => int 2
      2 => int 3
      3 => int 4
  1 =>
    array (size=3)
      0 => string 'a' (length=1)
      1 => string 'b' (length=1)
      2 => string 'c' (length=1)
  2 =>
    array (size=3)
      0 => string 'X' (length=1)
      1 => string 'Y' (length=1)
      2 => string 'Z' (length=1)
  3 =>
    array (size=5)
      0 => string '!' (length=1)
      1 => string '"' (length=1)
      2 => string '#' (length=1)
      3 => string '$' (length=1)
      4 => string '%' (length=1)

The rules:

The array size and sub arrays sizes are random, and quite huge.
Only one value from any sub array can be used.
Results should be ordered from shortest string to longest.
Must be memory efficient, due to huge data being generated, results should be stored / compared offline, like a file or mysql db. But each at a time.

An example of the desired string combinations:

1
2
3
4
a
b
c
X ...
1a
1b
1c
2a
2b ...
aX!
aX" ...
1aX!
1aX" .......
4cZ%

I tried several iterators like How to generate in PHP all combinations of items in multiple arrays.

So the length of each row is between 1 and the number of elements in your array? Do you want all the possible combinations, or just a few, like 100? — Ethan, May 31 '17 at 08:31
All combinations, arrays sizes are random, can be up to 15000 rows in one element, can up to 50 elements in one Array. — ion, May 31 '17 at 08:37
There doesn't seem to be a succinct statement of the problem here. Are you able to summarise it in your first paragraph? — halfer, Jun 04 '17 at 09:03

score 0 · Accepted Answer · answered Jun 09 '17 at 10:40

In my case the solution was this recursive function, i toggled the $combine variable to first insert single values from the array, then set the combine to true, to combine all values from the database (except the ones containing the currently iterated value):

            function iterdb( $arrays, $i = 0, $combine = false ) {
                if ( ! isset( array_keys( $arrays )[ $i ] ) ) {
                    return false;
                }
                if ( $i == 0 && $combine === true ) {
                    //Adding empty option to obtain all combos
                    for ( $x = 0; $x < count( $arrays ); $x ++ ) {
                        $arrays[ $x ][] = preg_replace( '`=[^\&]+`', '=', $arrays[ $x ][0] );
                    }
                }

                $this->iterdb( $arrays, $i + 1, $combine );//Call iteration on each following array
                $transactions = array();
                sort( $arrays[ $i ] );
                $this->log( 'Iterating array ' . $i . ' using combine ' . ( $combine ? 'True' : 'False' ) );
                foreach ( $arrays[ array_keys( $arrays )[ $i ] ] as $v ) {
                    if ( $this->counter > 0 ) {
                        if ( $combine === false ) {
                            $transactions[] = "INSERT IGNORE INTO scout_queries (scout,query) VALUES ('" . $this->Class . "','$v')";
                        } else {
                            $tmp = $this->queries->find( array(
                                'scout = :scout and query NOT LIKE :query',
                                ':scout' => $this->Class,
                                ':query' => '%' . ( array_values( explode( '=', $v ) )[0] ) . '%'
                            ), array( 'order' => 'CHAR_LENGTH(query) DESC' ) );

                            foreach ( $tmp as $t ) {
                                $transactions[] = "INSERT IGNORE INTO scout_queries (scout,query) VALUES ('" . $this->Class . "','" . $t->query . "&$v')";
                                $transactions   = $this->saveTransactions( $transactions );
                            }
                        }

                    }
                    $transactions = $this->saveTransactions( $transactions, true );
                }


                if ( $i == 0 && $combine === false ) {
                    return $this->iterdb( $arrays, 0, true );
                }
            }

How to generate all possible combinations using one value from each sub-array in PHP?

1 Answers1