Generating Ordered (Weighted) Combinations of Arbitrary Length in PHP

Question

Given a list of common words, sorted in order of prevalence of use, is it possible to form word combinations of an arbitrary length (any desired number of words) in order of the 'most common' sequences. For example,if the most common words are 'a, b, c' then for combinations of length two, the following would be generated:

aa
ab
ba
bb
ac
bc
ca
cb
cc

Here is the correct list for length 3:

aaa
aab
aba
abb
baa
bab
bba
bbb
aac
abc
bac
bbc
aca
acb
bca
bcb
acc
bcc
caa
cab
cba
cbb
cac
cbc
cca
ccb
ccc

This is simple to implement for combinations of 2 or 3 words (set length) for any number of elements, but can this be done for arbitrary lengths? I want to implement this in PHP, but pseudocode or even a summary of the algorithm would be much appreciated!

Answer 1

I googled for php permutations and got: http://www.php.happycodings.com/Algorithms/code21.html

I haven't looked into the code if it is good or not. But it seems to do what you want.

Answer 2

I don't know what the term is for what you're trying to calculate, but it's not combinations or even permutations, it's some sort of permutations-with-repetition.

Below I've enclosed some slightly-adapted code from the nearest thing I have lying around that does something like this, a string permutation generator in LPC. For a, b, c it generates

abc
bac
bca
acb
cab
cba

Probably it can be tweaked to enable the repetition behavior you want.

varargs mixed array permutations(mixed array list, int num) {
    mixed array out = ({});
    foreach(mixed item : permutations(list[1..], num - 1))
        for(int i = 0, int j = sizeof(item); i <= j; i++)
            out += ({ implode(item[0 .. i - 1] + ({ list[0] }) + item[i..], "") });
    if(num < sizeof(list))
        out += permutations(list[1..], num);
    return out;
}

FWIW, another way of stating your problem is that, for an input of N elements, you want the set of all paths of length N in a fully-connected, self-connected graph with the input elements as nodes.

Answer 3

Hi, I'm assuming that when saying it's easy for fixed length, you're using m nested loops, where m is the lenght of the sequence (2 and 3 in your examples).

You could use recursion like this:

Your words are numbered 0, 1, .. n, you need to generate all sequences of length m:

generate all sequences of length m:
{
    start with 0, and generate all sequences of length m-1
    start with 1, and generate all sequences of length m-1
    ...
    start with n, and generate all sequences of length m-1 
}

generate all sequences of length 0
{
    // nothing to do
}

How to implement this? Well, in each call you can push one more element to the end of the array, and when you hit the end of the recursion, print out array's contents:

// m is remaining length of sequence, elements is array with numbers so far
generate(m, elements)
{
    if (m == 0)
    {
        for j = 0 to elements.length print(words[j]);
    }
    else
    {
        for i = 0 to n - 1
        {
            generate(m-1, elements.push(i));
        }   
    }
}

And finally, call it like this: generate(6, array())

Answer 4

Here's a recursive function that might be what you need. The idea is, when given a length and a letter, to first generate all sequences that are one letter shorter that don't include that letter. Add the new letter to the end and you have the first part of the sequence that involves that letter. Then move the new letter to the left. Cycle through each sequence of letters including the new one to the right.

So if you had gen(5, d) It would start with

(aaaa)d
(aaab)d
...
(cccc)d

then when it got done with the a-c combinations it would do

(aaa)d(a)
...
(aaa)d(d)
(aab)d(d)
... 
(ccc)d(d)

then when it got done with d as the 4th letter it would move it to the 3rd

(aa)d(aa)

etc., etc.

<?php 
/** 
 * Word Combinations (version c) 6/22/2009 1:20:14 PM 
 * 
 * Based on pseudocode in answer provided by Erika: 
 *   http://stackoverflow.com/questions/1024471/generating-ordered-weighted-combinations-of-arbitrary-length-in-php/1028356#1028356 
 *   (direct link to Erika's answer) 
 * 
 * To see the results of this script, run it: 
 *   http://stage.dustinfineout.com/stackoverflow/20090622/word_combinations_c.php 
**/ 

init_generator(); 

function init_generator() { 
    global $words; 
    $words = array('a','b','c'); 
    generate_all(5);


} 

function generate_all($len){
    global $words;
    for($i = 0; $i < count($words); $i++){
        $res = generate($len, $i); 

     echo join("<br />", $res);  
     echo("<br/>");
    } 
}

function generate($len, $max_index = -1){ 
    global $words; 

    // WHEN max_index IS NEGATIVE, STARTING POSITION 
    if ($max_index < 0) { 
        $max_index = count($words) - 1; 
    } 

    $list = array(); 


    if ($len <= 0) { 
     $list[] = "";
        return $list; 
    } 

    if ($len == 1) { 

        if ($max_index >= 1) { 
      $add = generate(1, ($max_index - 1));
      foreach ($add as $addit) { 
                $list[] = $addit; 
            } 


        } 
     $list[] = $words[$max_index]; 
        return $list; 
    } 

    if($max_index == 0) { 
        $list[] = str_repeat($words[$max_index], $len); 
        return $list; 
    } 

    for ($i = 1; $i <= $len; $i++){ 
        $prefixes = generate(($len - $i), ($max_index - 1)); 
        $postfixes = generate(($i - 1), $max_index); 
        foreach ($prefixes as $pre){ 
      //print "prefix = $pre<br/>";
            foreach ($postfixes as $post){ 
       //print "postfix = $post<br/>";
                $list[] = ($pre . $words[$max_index] . $post); 
            } 
        } 
    } 
    return $list; 
} 

?>