Поиск всех возможных комбинаций строк с ограничениями - PullRequest
Новая
       8

Поиск всех возможных комбинаций строк с ограничениями

0 голосов
/ 25 мая 2018

Мне нужна помощь в создании алгоритма в PHP, который, учитывая массив алфавитов (представленный в виде строк) и массив группировок этих алфавитов (также массив строк), возвращает массив массивов всех возможных комбинацийстроки на основе этих группировок.Следующий пример прояснит это -

Если входной массив равен ['A', 'B', 'C'], а группировки ['AB', 'BC'], то возвращаемый результат:

  1. Без каких-либо ограничений будет [['A','B','C'], ['AB,'C'], ['A','BC'], ['AC','B'], ['ABC']]
  2. С ограничениями группировок должно быть [['A','B','C'], ['AB,'C'], ['A','BC']]

Причина этого в том, что ни 'ABC', ни 'AC' не допускаются группировки, и идея заключается в том, что группировкидолжно существовать, только если они принадлежат указанному массиву.В этом случае, поскольку «AB» и «BC» являются единственно возможными группировками, выходные данные содержат их.Первый вывод был только для демонстрационных целей, но алгоритм должен произвести второй вывод.Единственное другое ограничение заключается в том, что в одной комбинации не может быть повторяющихся алфавитов.Поэтому следующий вывод НЕ верен:

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

, так как «B» является дубликатом в ['AB','BC']

Подобный вопрос, который я нашел, был здесь, за исключением того, что нет никаких ограничений на то, какие числа можно сгруппировать в «Результат» в этом вопросе.

Я прошу прощения, если я сделал это звучит запутанно, но я обязательно уточню, если у вас есть какие-либо вопросы.

Ответы [ 2 ]

0 голосов
/ 25 мая 2018

Вы можете использовать ответ из поста, который вы связали.Я адаптировал его для вас: 

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

Это печатает: 

[A], [BC]
[AB], [C]
[A], [B], [C]
0 голосов
/ 25 мая 2018

Самый простой подход к созданию таких разделов - рекурсивный (я думаю).

Сначала представьте ограничения в виде логической (или 0/1) 2-й матрицы.Для вашего случая граф имеет соединения (ребра) A-B и B-C, а матрица смежности - [[0,1,0][1,0,1],[0,1,0]]

Начните с пустого массива.На каждом уровне рекурсии добавьте следующий элемент (A, затем B, затем C) во все возможные группы и в отдельную группу.

(В таких языках, как C, я бы использовал битовые маски для каждой группы, чтобы быстро определить с помощью операции bit-OR, позволяет ли группа добавить текущий элемент) 

  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]]
...