Я ищу некий алгоритм двумерной комбинации .. если это правильная формулировка. Я довольно опытный с PHP, но не с алгоритмами и продвинутой математикой, так что терпите меня, пожалуйста.
У меня есть набор элементов, которые я хочу объединить с другим набором элементов и рассчитать все возможные комбинации , чтобы впоследствии я мог их проанализировать. Количество элементов в наборах никогда не меняется, оба набора всегда имеют пять элементов:
$set1= array('A', 'B', 'C', 'D', 'E');
$set2= array('One', 'Two', 'Three', 'Four', 'Five');
Не знаю, является ли это правильной формулировкой, но я хотел бы видеть все комбинации предметов из набора 1, разделенные между предметами из набора 2 . Все элементы из обоих наборов должны использоваться только один раз для каждой возможности, и элементы набора 1 могут быть сгруппированы вместе в элементе набора 2, так что я получаю результирующий массив, который выглядит следующим образом (некоторые случайные значения в качестве примеров):
$possibilities= array(
0 => array(
'One' => array('A'),
'Two' => array('B'),
'Three' => array('C'),
'Four' => array('D'),
'Five' => array('E'),
),
1 => array(
'One' => array('A', 'B', 'C'),
'Two' => array('D'),
'Three' => array('E'),
'Four' => array(),
'Five' => array(),
),
2 => array(
'One' => array('C'),
'Two' => array(),
'Three' => array('A'),
'Four' => array('B'),
'Five' => array('D', 'E'),
),
3 => array(
'One' => array(),
'Two' => array(),
'Three' => array('A', 'B', 'C', 'D', 'E'),
'Four' => array(),
'Five' => array(),
),
);
и т. Д. Такого рода значения. Любые отзывы об этом приветствуются, в частности:
- Как кодировать что-то подобное в PHP ? Через рекурсивную функцию? Я использую алгоритм декартового произведения?
- Сколько комбинаций возможно? 5 ^ 10?
- В зависимости от предыдущего пункта: возможно ли работать с этими данными в режиме реального времени в веб-приложении? Если у меня есть 10 миллионов комбинаций, чем, я полагаю, мне, вероятно, нужно будет выполнить вычисления заранее, сохранить полученный анализ и поработать с ним во время выполнения приложения в реальном времени?
- Существуют некоторые ограничения (например, в наборе 2 элементов «Один», «Два» и «Три» всегда должен быть хотя бы один элемент из набора 1), но бесполезные комбинации будут отброшены в ходе последующего анализа, поэтому нет необходимости включать это в комбинированном алгоритме, разве он может сократить время вычисления, построив их в этой точке?
Мой вопрос может быть не очень ясным, поэтому просто спросите, нужно ли мне предоставить больше или лучшую информацию.
Заранее спасибо
Обновление 28-02-2012
Я попробовал PHP-реализации функций Power Set & Cartesian Product, которые я нашел в Интернете (Подобные вещи не в моих силах, чтобы попытаться написать код самостоятельно). Поэтому, когда я выполняю этот код:
$powerset= powerSet(array('A', 'B', 'C'));
$cartesian = cartesian(array(
'Set1' => $powerset,
'Set2' => array('One', 'Two', 'Three')
));
Это то, что функция powerSet помещает в $ powerset:
Array (
[0] => Array ()
[1] => Array (
[0] => A
)
[2] => Array (
[0] => B
)
[3] => Array (
[0] => B
[1] => A
)
...
И это то, что возвращает декартова функция:
Array (
[0] => Array (
[Set1] => Array ()
[Set2] => One
)
[1] => Array (
[Set1] => Array (
[0] => A
)
[Set2] => One
)
[2] => Array (
[Set1] => Array (
[0] => B
)
[Set2] => One
)
[3] => Array (
[Set1] => Array (
[0] => B
[1] => A
)
[Set2] => One
)
...
Так что это вроде как то, что я хотел, но не самая сложная часть. Он рассматривает комбинации «индивидуально» и не распределяет Set1 в Set2, следя за тем, чтобы все элементы Set1 использовались для всех трех элементов Set2.
- Я неправильно истолковал использование этих двух функций? Я полагаю, что я не совсем правильно понимаю, как объединить Power Set и Cartesian Product для достижения моего результата. Должен ли я вызывать функцию powerSet () внутри функции cartesian ()?
- Может быть, эти специфические функции PHP не совсем соответствуют моей цели? Я нашел их здесь:
Другое обновление: устранение проблемы без программирования.
Эта проблема связана с инструментом анализа, который я создаю для стратегической игры. Каждый раз, когда инструмент используется, игроки могут выбрать 5 различных юнитов из большой коллекции юнитов. Эти единицы могут быть объединены с другими (статическими) объектами (назовем эти «пулы») различными способами. У юнитов есть характеристики, которые могут улучшать или не улучшать стратегию игрока, если они объединены с определенными пулами. Например:
- Единица А любит быть в бассейне 1, но ненавидит быть в бассейне 2
- Подразделение B ненавидит находиться в бассейне 1, если только там не находится Подразделение A
- и т.д ..
Цель инструмента - найти лучшие комбинации, какие юниты входят в какой пул. Вот правила:
- Всегда есть 5 разных юнитов, выбранных из коллекции из 50. Все эти юниты имеют разные характеристики.
- Всегда есть 5 одинаковых пулов.Они имеют разные характеристики, но пулы не выбираются из большой коллекции, они всегда одинаковы.
- Каждый пул может содержать несколько единиц, от 0 до 5.
- Каждая единица можетбыть только в одном пуле.
Ввод:
- Список из 5 переменных единиц: A, B, C, D, E
- Список из 5 статических пулов: Pool1, Pool2, Pool3, Pool4, Pool5
Вывод должен быть, все возможные комбинации между этими двумя списками ,на основании вышеупомянутых правил.Некоторые примеры:
Комбинация 1
- Пул 1: A
- Пул 2: B
- Пул 3: C
- Пул 4: D
- Пул 5: E
Комбинация 2
- Пул 1: A, B, C
- Пул 2: D
- Пул 3: E
- Пул 4:
- Пул 5:
Комбинация 3
- Пул 1: C
- Пул 2:
- Пул 3: A
- Пул 4: B
- Пул 5: D, E
Комбинация 4
- Пул 1:
- Пул 2:
- Пул 3: A, B, C, D, E
- Пул 4:
- Пул 5:
и т. Д. *
Итак что я хотел бы сделать это:
- Возьмите все возможные комбинации юнитов и пулов, которые существуют.
- Пройдите их и назначьте комбинации "стратегическое значение", основанное на синергии между юнитами и пулами.
- Возьмите 10 лучших комбинаций, которые имеют наибольшее «стратегическое значение»
Шаг 2 и 3 не проблема. У меня проблема с генерацией всех возможных комбинаций юнитов в пулах.
Надеюсь, это более четкое описание проблемы