Generate every unique combination using all elements from array
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) &lt;= 1 ) {
            $result = $words;
        } else {
            $result = array();
            for ( $i = 0; $i &lt; count($words); ++$i ) {
                $firstword = $words[$i];
                $remainingwords = array();
                for ( $j = 0; $j &lt; count($words); ++$j ) {
                    if ( $i &lt;&gt; $j ) $remainingwords[] = $words[$j];
                }
                $combos = wordcombos($remainingwords);
                for ( $j = 0; $j &lt; count($combos); ++$j ) {
                    $result[] = $firstword . ' ' . $combos[$j];
                }
            }
        }
        return $result;
    }