3

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!

2
  • I think these are permutations, not combinations. And maybe not even that. Aug 28, 2012 at 13:59
  • 2
    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, 2012 at 14:02

4 Answers 4

3

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"
}
1
  • 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, 2012 at 14:41
1

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);
1
  • 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, 2013 at 4:38
0

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

1
  • 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, 2012 at 14:46
-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)!

5
  • 1
    Actually, no, he isn't asking for a Cartesian product. It is a kind of permutation where omissions are permitted.
    – nneonneo
    Aug 28, 2012 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... Aug 28, 2012 at 14:46
  • What sets are you taking the product of?
    – nneonneo
    Aug 28, 2012 at 14:47
  • each individual array element in this case forms 'a set' Aug 28, 2012 at 14:50
  • Nope. That just generates subsets. We want ordered subsets.
    – nneonneo
    Aug 28, 2012 at 15:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.