Generating ordered (weighted) combinations of arbitrary length in PHP

Question

Given a list of common words sorted in order of predominance of use, is it possible to form phrases of arbitrary length (any desired number of words) in the 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 will be created:

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 

It is easy to implement for combinations of 2 or 3 words (given length) for any number of elements, but can this be done for an arbitrary length? I want to implement this in PHP, but a pseudo code or even a summary of the algorithm would be very appreciated!

Answer 1

Here's a recursive function, which may be what you need. The idea is to, when specifying the length and the letter, first generate all sequences that are one letter shorter that do not include this letter. Add a new letter at the end, and you have the first part of the sequence that includes this letter. Then move the new letter to the left. Go through each sequence of letters, including the new one, to the right.

So, if you have the gene (5, d), it starts with

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

then when it is done with ac combinations it will do

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

then when it was done with d as the 4th letter, it would move it to the third

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

Answer 2

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

I have not studied the code if it is good or not. But it looks like he is doing what you want.

Answer 3

I don’t know what this term means for what you are trying to calculate, but it’s not combinations or even permutations, it’s a kind of permutation with repetition.

Below I have attached some slightly adapted code from the closest thing that I was lying around, something like this, a line-breaker in LPC. For a, b, c it generates

 abc bac bca acb cab cba 

It can probably be modified to provide the desired repetition behavior.

 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 to report your problem is that entering elements of N requires a set of all paths of length N in a fully connected self-connected graph with input elements as nodes.

Answer 4

I assume that when you say this easily for a fixed length, you use m nested loops, where m is the length of the sequence (2 and 3 in your examples).

You can use recursion as follows:

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 another element to the end of the array, and when you press the end of the recursion, print the contents of the array:

 // 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, name it like this: generate (6, array ())