Finding All Possible Combinations of Strings with Restrictions

Question

I need help with creating an algorithm in PHP that, given an array of alphabets (represented as strings) and an array of groupings of those alphabets (also an array of strings), returns an array of arrays of all possible combinations of strings based on those groupings. The following example will make it clear -

If the input array is ['A', 'B', 'C'] and the groupings are ['AB', 'BC'] the returned output:

Without any restrictions would be [['A','B','C'], ['AB,'C'], ['A','BC'], ['AC','B'], ['ABC']]
With the restrictions of the groupings should be [['A','B','C'], ['AB,'C'], ['A','BC']]

The reason for this is because neither 'ABC' nor 'AC' are allowed groupings and the idea is that the groupings should only exist if they belong to the specified array. In this case, since 'AB' and 'BC' are the only possible groupings, the output contains them. The first output was just for demonstration purposes, but the algorithm should produce the second output. The only other restriction is that there can't be duplicate alphabets in a single combination. So the following output is NOT correct:

[['A','B','C'], ['AB,'C'], ['A','BC'], ['AB','BC'], ['AC','B'], ['ABC']]

since 'B' is a duplicate in ['AB','BC']

A similar question I found was here, except that there are no restrictions on which numbers can be grouped together in the "Result" in this question.

I apologize if I made it sound confusing but I'll be sure to clarify if you have any questions.

And `['A','B','C']` is allowed in the output because? Also, is your program expected to examine the groupings and detect illegal entries. Also, the typical terminology is to call your "array of alphabets" *an alphabet*, and each member of the alphabet a *symbol*. — Jim Mischel, May 25 '18 at 03:09
Please give 3-4 more examples with expected output. This is very confusing. — nice_dev, May 25 '18 at 07:15

score 0 · Answer 1 · answered May 25 '18 at 07:58

The simplest approach to generate such partitions is recursive (I think).

At first, represent restrictions as boolean (or 0/1) 2d matrix. For your case graph has connections (edges) A-B and B-C and adjacency matrix is [[0,1,0][1,0,1],[0,1,0]]

Start from empty array. At every recursion level add next element (A, then B, then C) into all possible groups and into separate group.

(In languages like C I'd use bit masks for every group to determine quickly with bit-OR operation whether a group allows to add current element)

  First level:   add A and get:   
              [[A]]
  Second level:  add B both in existing group and in separate one: 
              [[A, B]],                [[A],[B]]
  Third Level:  you add C only with:  
              [[A, B], C],       [[A],[B, C]], [[A],[B], [C]]

score 0 · Answer 2 · answered May 25 '18 at 11:59

You can use the answer from the post you linked. I adapted it for you:

function generate_groups($collection) {
    if (count($collection) == 1) {
        yield [$collection];
        return;
    }
    $first = $collection[0];
    foreach (generate_groups(array_slice($collection, 1)) as $smaller) {
        foreach (array_values($smaller) as $n => $subset) {
            yield array_merge(
                array_slice($smaller, 0, $n),
                [array_merge([$first], $subset)],
                array_slice($smaller, $n+1)
            );
        }
        yield array_merge([[$first]], $smaller);
    }
}

$input = ['A', 'B', 'C'];
$groupings = ['AB', 'BC'];

foreach (generate_groups($input) as $groups) {
    $are_groups_ok = true;
    foreach ($groups as $group) {
        $compact = implode($group);
        if (strlen($compact) != 1 and !in_array($compact, $groupings)) {
            $are_groups_ok = false;
        }
    }
    if ($are_groups_ok) {
        echo "[" . implode("], [", array_map("implode", $groups)) . "]\n";
    }
}

This prints:

[A], [BC]
[AB], [C]
[A], [B], [C]

Finding All Possible Combinations of Strings with Restrictions

2 Answers2