Generate every unique combination using all elements from array

Question

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;
}

Answer 1

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;
    }

Answer 2

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"

Answer 3

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.