Сформировать все возможные комбинации

Обновить

November 2018

Просмотры

674 раз

4

У меня есть приложение, где пользователи могут настроить продукт, который они собираются приобрести, выбирая опцию из меню. Это меню имеет много разделов, и каждый раздел может иметь список флажков для MultiChoice или радиокнопок, когда только один вариант может быть выбран. Пользователь должен выбрать, по крайней мере, один из вариантов в каждой секции. Структура меню что-то вроде этого:

$sections = array();

$sections[1] = array(
    'multichoice' => true,
    'options' => array('A','B','C')
);

$sections[2] = array(
    'multichoice' => false,
    'options' => array('A','B','C','D')
);

$sections[3] = array(
    'multichoice' => false,
    'options' => array('A','B')
);

$sections[4] = array(
    'multichoice' => true,
    'options' => array('A','B','C','D','E')
);

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

Теперь, мой босс попросил меня создать страницу со списком всех возможных комбинаций в случае, если пользователь слишком ленив, чтобы построить продукт сами. Так что я должен быть в состоянии сформировать структуру, как это:

$combinations = array(
    array(
        1 => array('A','B'),
        2 => 'A',
        3 => 'A',
        4 => array('B','D','E')
    ),
    array(
        1 => array('A'),
        2 => 'B',
        3 => 'A',
        4 => array('A','B')
    )
// etc...
);

Мне удалось найти все возможные комбинации, используя случайный подход, генерируя хэш для Comparision с тем, что уже было создано. Это на самом деле работает, но работает очень медленно (это перебор в основном):

...

function generate(){
    $result = array();
    $ids = array();
    foreach($this->getSections() as $sect){
        $items = $this->getSectionOptions($sect['id']);
        if($sect['multi']=='N'){
            $item = $items[rand(0, count($items)-1)];
            $result[$sect['id']] = $item['id'];
            $ids[] = $item['id'];
        } else {
            $how_many = rand(1,count($items));
            shuffle($items);
            for($i=1;$i<=$how_many;$i++){
                $item = array_shift($items);
                $result[$sect['id']][] = $item['id'];
                $ids[] = $item['id'];
            }
        }
    }
    sort($ids);
    return array(
        'hash' => implode(',',$ids),
        'items' => $result
    );
}

function generateMany($attempts=1000){
    $result = array();
    $hashes = array();
    for($i=1;$i<=$attempts;$i++){
        $combine = $this->generate();
        if(!in_array($combine['hash'],$hashes)){
            $result[] = $combine['items'];
            $hashes[] = $combine['hash'];
        }
    }
    return $result;
}


...

Я хочу, чтобы ваша помощь, чтобы создать что-то более точным и быстрым. Помните, что каждая комбинация должна иметь по крайней мере один из вариантов каждого раздела. А также иметь в виду, что порядок опций в разделах MULTICHOICE не имеет никакого значения, (т.е. E, B, A является такой же, как B, E, A)

Спасибо

1 ответы

3

Благодаря это головоломка действительно интересно делать!

Так как же я решаю, рекурсия рекурсии рекурсии: D

Я начал с несколькими выбор, так как это самый трудный! (И на самом деле он будет решать и смешивание)

объяснение

Для того, чтобы объяснить, как я получил его на работу, позволяет брать пример с выбором A, B, C. Мы имели бы тогда следующие комбинации:

A B
A B C
A C
B
B C
C

Если мы посмотрим ближе, мы можем видеть, как некоторые шаблон. Давайте список результатов первого элемента (А)

B
B C
C
---
B
B C
C

Хм, интересно ... Теперь давайте снова первый элемент (B)

C
---
C

Это простой случай, но это произойдет в любом случае размер.

Так что я сделал сценарий рекурсии, чтобы добраться до конца, а затем добавить назад, сочетание итерации и дублируя его с предыдущим значением.

И вуаля! это оно!

Для окончательной смеси , где требуются все элементы, я сделал очень похожий метод, но он должен содержать 1 элемент каждого

И это очень быстро!

Общее время на 100000 итераций с 126 комбинаций: 14.410287857056 секунд

если вы нашли ошибку пинг меня: D

Код

https://gist.github.com/MLoureiro/a0ecd1ef477e08b6b83a