как получить все комбинации из нескольких деревьев? - PullRequest
Новая
       40

как получить все комбинации из нескольких деревьев?

0 голосов
/ 17 марта 2011

Я понятия не имею, как получить все возможности из x наборов данных, кроме использования вложенных для циклов x, что я не хочу делать, потому что я не знаю значения x, что делает возможным очень большое числоиз для циклов for жестко запрограммировано не равно числу необходимых циклов.

скажем, у меня есть: 

A:1,2,3,4
B:2,4,65,2
C:1,3,2
D:2,8

и я хотел получить каждую комбинацию по 1 элементу из каждой группы (в моем кодеЯ использую std::vector <myclass>), как бы я это сделал?Может кто-нибудь, пожалуйста, опубликуйте общий псевдокод, которому я могу следовать, чтобы сделать это?

1 Ответ

0 голосов
/ 17 марта 2011

если вы не знаете, сколько у вас «групп», я полагаю, у вас есть хотя бы некоторая коллекция из них? т.е. массив / вектор всех ваших векторов?

если так, вот общее представление о том, что будет работать 

void iterateAllCombinations(array_of_groups, current_group_index,temp_result,callback_function)
{
  current_group = array_of_groups[current_group_index]
  for each element in current_group
  {
    temp_result[current_group_index]=element
    if current_group_index>0
      iterateAllCombinations(array_of_groups,current_group_index-1,temp_result,callback_function)
    else
      callback_function(temp_result)
  }
}

this would be called in some fashion like:
iterateAllCombinations(my_groups,my_groups.length-1,new vector[my_groups.length],&do_something_with_array)

Основное объяснение того, что происходит: когда вы вызываете функцию, она начинает проходить через каждый элемент в «верхней» группе (последний в array_of_groups). Если кроме «верхней» группы будет больше групп, она вызовет ту же функцию, пропустив текущие элементы и попросив ее просмотреть следующую группу.

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

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

Это псевдокод, особенности меняются в зависимости от вашего языка. «временный результат» может быть объявленным и выделенным предварительным массивом (как я показываю в псевдокоде), или это может быть стек, который передается перед каждым рекурсивным вызовом и извлекается после, или это может быть массив / вектор, который вы копируете и добавляете перед каждым рекурсивным вызовом. Вы могли бы даже иметь связанный список, где каждый узел просто сохранялся бы в кадре стека для этого вызова функции, и вам просто нужно было бы передать указатель «родителя» на следующий уровень вниз.

Если у вас есть одна конкретная вещь, которую вы хотите сделать, вы можете заменить 'callback_function' этой конкретной вещью. Или, если ваш язык это позволяет, вы можете использовать это как итератор / генератор и позволить этому «обратному вызову» быть неявным

Если вы действительно ненавидите рекурсивный код, вы можете написать то же самое, что и цикл while, но гораздо проще написать его как рекурсивную функцию.

...