8
\$\begingroup\$

I am trying to make a script that generates every possible combination from an array of elements. I have found a script that does it, but it is too intensive and takes extremely long to generate anything that has more than 7 elements inside the array.

I am trying to achieve, where from an array of:

array("Quick", "Brown", "Fox");

I would get a result of:

Quick Brown Fox
Quick Fox Brown
Brown Quick Fox
Brown Fox Quick
Fox Quick Brown
Fox Brown Quick

As you can see, that a single word never repeats itself, and there are only unique generations, as well as it always uses all elements of the array, so it never returns less elements than the length of array.

Here is the code that I am currently using:

function f_($n) { 
    if($n<2) { return 1; } 
    for($x = 2;$n-1>1;$x*=$n--); 
    return $x; 
} 


function array_restore($r) { 
    $clean = array(); 
    if(is_array($r)) { 
        foreach($r as $k) { 
            $clean[] = $k; 
        } 
    }     

    return $clean; 
} 

function connect($arr){
    $back = "";
    foreach($arr as $a){
        if($back != ""){
            $back .= " ";
        }

        $back .= $a;
    }
    return $back;
}

function cmb($v) { 
    $str = count($v); 
    $tot = f_($str);

    $combo = array(); 
    for($i=0;$i<$tot*8;$i++) { 
        shuffle($v);
        $sf = connect($v);
        if(!in_array($sf, $combo)){
            $combo[] = $sf;     
        }
    } 

    $x = array_unique($combo); 
    return array_restore($x); 
} 

var_dump(cmb(array("Quick", "Brown", "Fox")));

EDIT: I found a bit better algorithm, seems like its impossible to make anything even quicker, so I will have to find a different way to approach my problem.

function pc_permute($items, $perms = array( )) {
    $back = array();
    if (empty($items)) { 
        $back[] = join(' ', $perms);
    } else {
        for ($i = count($items) - 1; $i >= 0; --$i) {
             $newitems = $items;
             $newperms = $perms;
             list($foo) = array_splice($newitems, $i, 1);
             array_unshift($newperms, $foo);
             $back = array_merge($back, pc_permute($newitems, $newperms));
         }
    }
    return $back;
}
\$\endgroup\$
5
\$\begingroup\$

Your method chooses a word combination at random, then checks if that combination has been discovered previously. The first few combinations are discovered quickly, but last few take much longer. Once you have found 99.9% of the unique rows, it will take on average 1000 tries to find the next unique row. You also give up too soon, leaving some combinations undiscovered.

For n different words, there are n! (n factorial) unique combinations. So for your 8-word example:

    array("Quick", "Brown", "Fox", "Jumped", "Over", "The", "Lazy", "Dog")

there are 8! or exactly 40,320 combinations. When I ran your code, I got only 40,305 rows, in random order, with 15 combinations missing. (and it took 4 minutes!) My version (below) runs in 400ms and produces the rows in the order you desire, i.e. all the "Quick" rows first etc.

My algorithm doesn't make use of random guesses; it uses some loops and recursion to generate all the combinations deterministically.

    // For an array of n words, return an array of n! strings, each containing the words in a different order.
    function wordcombos ($words) {
        if ( count($words) <= 1 ) {
            $result = $words;
        } else {
            $result = array();
            for ( $i = 0; $i < count($words); ++$i ) {
                $firstword = $words[$i];
                $remainingwords = array();
                for ( $j = 0; $j < count($words); ++$j ) {
                    if ( $i <> $j ) $remainingwords[] = $words[$j];
                }
                $combos = wordcombos($remainingwords);
                for ( $j = 0; $j < count($combos); ++$j ) {
                    $result[] = $firstword . ' ' . $combos[$j];
                }
            }
        }
        return $result;
    }
\$\endgroup\$
  • \$\begingroup\$ The second version that I posted is still a bit quicker. \$\endgroup\$ – Vilsol Dec 16 '14 at 0:22
  • \$\begingroup\$ @vilsol - For 8 words, on my IIS/PHP 5.3 server, I find your getAllCombos version is slightly slower than the original code at 241 sec, but it does produce the correct 40,320 rows. The original code is slightly faster at 199 sec, but 10 or 20 (it's random) of the row are missing! My version runs in 0.3 sec. That is over 500 times faster than the other two versions. \$\endgroup\$ – Tom Robinson Dec 16 '14 at 3:25
  • \$\begingroup\$ Sorry I got the versions mixed up. @vilsol's pc_permute version is indeed very fast (0.5s). It is rtainc's getAllCombos I was referring to above. \$\endgroup\$ – Tom Robinson Dec 16 '14 at 18:10
2
\$\begingroup\$
function getAllCombos($arr) {
    $combinations = array();
    $words = sizeof($arr);
    $combos = 1;
    for($i = $words; $i > 0; $i--) {
        $combos *= $i;
    }
    while(sizeof($combinations) < $combos) {
        shuffle($arr);
        $combo = implode(" ", $arr);
        if(!in_array($combo, $combinations)) {
            $combinations[] = $combo;
        }
    }
    return $combinations;
}

Output

[0] => "Quick Brown Fox"
[1] => "Quick Fox Brown"
[2] => "Fox Quick Brown"
[3] => "Brown Fox Quick"
[4] => "Fox Brown Quick"
[5] => "Brown Quick Fox"
\$\endgroup\$
  • \$\begingroup\$ This is just code dump. Please add some explanation why this is better. \$\endgroup\$ – janos Dec 15 '14 at 21:25
  • 1
    \$\begingroup\$ @janos It is slightly faster than the original code, and much more compact. If I find one which is substantially faster, I will edit the post. \$\endgroup\$ – rtainc Dec 15 '14 at 21:32
  • 2
    \$\begingroup\$ I'm not sure this would be very efficient with a larger array, you're just continuiously in a loop until shuffle() eventually gives you a unique combination, this just seems like pure luck. A more "definate/exact" method would be preferable to be honest. \$\endgroup\$ – Adrian Dec 16 '14 at 9:44
1
\$\begingroup\$

I've created this:

function insertWord($words,$index,$word)
{
  array_splice($words,$index,0,$word);
  return implode(' ',$words);
}

function allOrders($words)
{
  if (count($words) <= 1) return $words;
  $word   = array_pop($words);
  $orders = allOrders($words);
  foreach ($orders as $order) {
    $order = explode(' ',$order);
    $size  = count($order);
    for ($index = 0;$index <= $size;$index++) {
      $result[] = insertWord($order,$index,$word);
    }
  }
  return $result;
}

The basic algorithm:

  1. Remove one word from the list of words.
  2. Find all possible sequences of words in the list that remains, by recursion.
  3. Insert the removed word in all possible places in the found list of sequences.

It executes about twice as fast as the method of Tom Robinson, and it's simpler.

\$\endgroup\$
  • \$\begingroup\$ Both our algorithms, along with pc_permute, do the job properly, with recursion. (My PHP was a bit rusty so I forgot to use foreach.) Your code produces: Fox Brown Quick; Brown Fox Quick; Brown Quick Fox; Fox Quick Brown; Quick Fox Brown; Quick Brown Fox. Try adjusting the code so the sequence is Quick Brown Fox; Quick Fox Brown ... as in the original question. \$\endgroup\$ – Tom Robinson Dec 17 '14 at 16:51
  • \$\begingroup\$ It's not the foreach that makes my algorithm faster, it's the efficient usage of arrays, lowering the number of operations needed. You can alter the sequence, to what's in the original question, by replacing array_pop() with array_shift(). \$\endgroup\$ – KIKO Software Dec 17 '14 at 22:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.