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!

I think these are permutations, not combinations. And maybe not even that. — Waleed Khan, Aug 28 '12 at 13:59
Sure seems to me a good candidate for a recursive permutation algorithm, although including each original string independently as a result is a slight departure from a "pure" permutation. The recursive terminating case would be when you have only two elements, and the recursive part would be the nth element followed by the recursive perms of the n+1th and remaining elements. Be careful, though, because permutation computations can go through the roof quickly! Good luck! — David W, Aug 28 '12 at 14:02

score 3 · Answer 1 · answered Aug 28 '12 at 14:39

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

I should point out that the last time I competently used PHP was about four years ago, so if my approach sucks and there's a better way to do what I did, please let me know! — nneonneo, Aug 28 '12 at 14:41

score 1 · Answer 2 · answered Aug 28 '12 at 15:28

Here is my implementation which I have written for quite some time using basic mathematical definiton of combination and permutation. Maybe this could help.

<?php
/**
 * Generate all the combinations of $num elements in the given array
 *
 * @param array  $array   Given array
 * @param int    $num     Number of elements ot chossen
 * @param int    $start   Starter of the iteration
 * @return array          Result array
 */
function combine($array, $num, $start = 0) {

    static $level = 1;

    static $result = array();

    $cnt = count($array);

    $results = array();

    for($i = $start;$i < $cnt;$i++) {
        if($level < $num ) {
            $result[] = $array[$i];
            $start++;
            $level++;
            $results = array_merge($results, combine($array, $num, $start));
            $level--;
            array_pop($result);
        }
        else {
            $result[] = $array[$i];
            $results[] = $result;
            array_pop($result);
        }
    }

    return $results;
}

/**
 * Generate all the permutations of the elements in the given array
 */
function permute($array) {

    $results = array();

    $cnt = count($array);

    for($i=0;$i<$cnt;$i++) {
        $first = array_shift($array);

        if(count($array) > 2 ) {
            $tmp = permute($array);
        }
        elseif(count($array) == 2) {
            $array_ = $array;
            krsort($array_);
            $tmp = array($array, $array_);
        }
        elseif(count($array) == 1) {
            $tmp = array($array);
        }
        elseif(count($array) == 0) {
            $tmp = array(array());
        }

        foreach($tmp as $k => $t) {
            array_unshift($t, $first);
            $tmp[$k] = $t;
        }

        $results = array_merge($results, $tmp);

        array_push($array, $first);
    }

    return $results;
}

$strings = array('T', 'O', 'RS');
$strings_count = count($strings);


$combinations = array();
for ($i = 1; $i <= $strings_count; $i++) {
  $combination = combine($strings, $i, 0);
  $combinations = array_merge($combinations, $combination);
}

$permutations = array();
foreach($combinations as $combination) {
  $permutation = permute($combination);
  $permutations = array_merge($permutations, $permutation);
}

print_r($combinations);
print_r($permutations);

Just a heads up, the `combine()` function is expecting the `$array` to be numerically and sequentially indexed. Perhaps an `array_values()` could eliminate that concern. More work would be required if the keys were an important part of the combination. — Stoutie, Oct 29 '13 at 04:38

score 0 · Answer 3 · answered Aug 28 '12 at 14:39

Here's my naive recursive implementation:

<?php
// Lists all ways to choose X from an array
function choose($x, array $arr) {
    $ret = array();
    if ($x === 0) {
        // I don't think this will come up.
        return array();
    } else if ($x === 1) {
        foreach ($arr as $val) {
            $ret[] = array($val);
        }
    } else {
        $already_chosen = choose($x - 1, $arr);
        for ($i = 0, $size_i = sizeof($arr); $i < $size_i; $i++) {
            for ($j = 0, $size_j = sizeof($already_chosen); $j < $size_j; $j++) {
                if (!in_array($arr[$i], $already_chosen[$j])) {
                    $ret[] = array_merge(
                        array($arr[$i]),
                        $already_chosen[$j]
                    );
                }
            }
        }
    }
    return $ret;
}

function choose_all($arr) {
    for ($i = 1, $size = sizeof($arr); $i <= $size; $i++) {
        foreach (choose($i, $arr) as $val) {
            echo implode(":", $val).PHP_EOL;
        }
    }
}

choose_all(array(
    "A",
    "B",
));
echo "--".PHP_EOL;
choose_all(array(
    "ABC",
    "Z",
));
echo "--".PHP_EOL;
choose_all(array(
    'T',
    'O',
    'RS'
));

(No idea what I did, of course)

http://codepad.org/5OKhsCJg

Works, yes; not knowing what you did, a bit troubling. Nevertheless, I get the feeling that real-world algorithm implementations often fall into this category... — nneonneo, Aug 28 '12 at 14:46

score -2 · Answer 4 · answered Aug 28 '12 at 14:06

-2

What you require over the array is essentially a cartesian product. This is an aspect of set mathematics and is common in database systems as well as formal modelling languages. There will be a number of implementation solutions if you google this term for PHP.

(I've never done any PHP directly which is why I don't want to post you an incorrect (or hacky) solution, but hopefully this will help lead you down the correct path)!

answered Aug 28 '12 at 14:06

absentmindeduk

136
1
10

1

Actually, no, he isn't asking for a Cartesian product. It is a kind of permutation where omissions are permitted. – nneonneo Aug 28 '12 at 14:19
I'm not quite sure I follow what you mean? It doesn't say omissions are permitted and from the comment (I don't actually need duplicates, but I don't want the make things more difficult), that suggests to me that a cartesian product would be better... – absentmindeduk Aug 28 '12 at 14:46
What sets are you taking the product of? – nneonneo Aug 28 '12 at 14:47
each individual array element in this case forms 'a set' – absentmindeduk Aug 28 '12 at 14:50
Nope. That just generates subsets. We want ordered subsets. – nneonneo Aug 28 '12 at 15:17

Generate all possible combinations using a set of strings

4 Answers4

Linked