php - Generate all possible combinations using a set of strings

Question

I'm trying to generate all possible combinations of a set of strings, using each string maximum once.

• The length of the output string isn't defined (the maximum length is the number of the given strings,since you can only use them once)
• For example, the stringset array('A','B') would generate A,B,AB,BA.
• For example, the stringset array('ABC', 'Z') would generate 'ABC','Z', 'ZABC' and 'ABCZ'.
• A stringset can have identical entries, and the output does't need te be unique.For example, the stringset array('A', 'A') would generate 'A', 'A','AA','AA'; (I don't actually need duplicates, but I don't want the make things more difficult)

I know that 2 strings have 4 combinations (2=>4) and 3=>15, 4=>64, 5=>325 ...

Since I'm not a programmer, I found it at least 'challenging'. Nested loops where soon too complicated. An easier solution could be finding a pattern in the indexes of array with strings. But this gives me duplicate use of the strings...

  $strings = array('T','O','RS');
  $num = 0;
  $stringcount = count($strings);
  $variations = array(0,1,4,15,64,325,1956,13699,109600,986409);

  for($i=0;$i<$variations[$stringcount];$i++){
    $index = base_convert($num, 10, $stringcount);
    $array_of_indexes = str_split($index);
    $out='';
    for($j=0;$j<count($array_of_indexes);$j++){
     $out .= $strings[$array_of_indexes[$j]];
    }
    echo $out . '<br />';
    $num++;
  }

Result: T O RS OT OO ORS RST RSO RSRS OTT OTO OTRS OOT OOO OORS

Not good, many duplicates + many valid combinations are not included

I know this solution is wrong in many ways, but I don't know where to start? Any Suggestions? Thx in Advance!

Answer 1

In mathematical terminology, you are asking for all possible nonempty ordered subsets of the input set. In the Online Encyclopedia of Integer Sequences, the number of such sequences appears as sequence A007526 - note that this sequence begins with 4, 15, 64, 325 exactly as you have discovered.

This problem admits a very short, efficient solution in Python, so I'm going to post that solution first:

def gen_nos(s):
    for i in sorted(s):
        yield i
        s.remove(i)
        for j in gen_nos(s):
            yield i+j
        s.add(i)

Example:

>>> list(gen_nos(set(['a', 'b', 'c'])))
['a', 'ab', 'abc', 'ac', 'acb', 'b', 'ba', 'bac', 'bc', 'bca', 'c', 'ca', 'cab', 'cb', 'cba']

Note that sorted is not strictly necessary; it just ensures that the output is lexicographically sorted (otherwise, the elements are iterated in set order, which is essentially arbitrary).

To convert this to PHP, we have to essentially use a recursive function with an extra array parameter to hold the result:

function gen_nos(&$set, &$results) {
    for($i=0; $i<count($set); $i++) {
        $results[] = $set[$i];
        $tempset = $set;
        array_splice($tempset, $i, 1);
        $tempresults = array();
        gen_nos($tempset, $tempresults);
        foreach($tempresults as $res) {
            $results[] = $set[$i] . $res;
        }
    }
}

Example:

$results = array();
$set = array("a", "b", "c");
gen_nos($set, $results);
var_dump($results);

produces

array(15) {
  [0]=>
  string(1) "a"
  [1]=>
  string(2) "ab"
  [2]=>
  string(3) "abc"
  [3]=>
  string(2) "ac"
  [4]=>
  string(3) "acb"
  [5]=>
  string(1) "b"
  [6]=>
  string(2) "ba"
  [7]=>
  string(3) "bac"
  [8]=>
  string(2) "bc"
  [9]=>
  string(3) "bca"
  [10]=>
  string(1) "c"
  [11]=>
  string(2) "ca"
  [12]=>
  string(3) "cab"
  [13]=>
  string(2) "cb"
  [14]=>
  string(3) "cba"
}