Возможные категории с использованием рекурсии

У меня есть два массива, один содержит категории верхнего уровня, а другой содержит подкатегории, где длина подкатегорий> длина категорий верхнего уровня.Возможные категории с использованием рекурсии

Я пытаюсь написать рекурсивный алгоритм, чтобы дать мне все возможные способы разместить подкатегории в категориях верхнего уровня. Так, например, если у меня есть категории [A,B,C] верхнего уровня и подкатегорий [W,X,Y,Z] Я хотел бы получить:

A->WXYZ, B->null, C->null 
A->XYZ, B->W, C->null 
A->WYZ, B->X, C->null 
... 
A->null, B->Z, C->WXY 
A->null, B->null, C->WXYZ

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

Спасибо!

источник

2012-06-08 Paul

Итак, каждая подкатегория должна быть не более одной категории? Или точно один? – svick

Каждая подкатегория должна быть в одной категории. – Paul

Я думаю, что могу найти рекурсивное решение, но он использует слишком много памяти, вам нужна практическая реализация? – sukunrt

Вам не нужны перестановки, и вам не нужна рекурсия, вам просто нужно подсчитать. Скажем, у вас есть N категорий и подкатегорий M - вам нужно пройти все M-цифры в базе N.

Давайте возьмем 3 категории, но назовите их 0, 1 и 2 - то есть все цифры в база-3. Теперь давайте посмотрим на всех 4 значные номера в базе в 3:

0000, 0001, 0002, 0010, 0011, 0012, ..., 2212, 2220, 2221, 2222

Каждый номер представляет собой распределение подкатегории к категориям, например: первая цифра для подкатегории W, вторая для подкатегории X, третья для подкатегории Y, а последняя для подкатегории Z.

Итак, 0000 означает, что WXYZ находятся в первой категории (ваш первая строка в примере). 1000 - ваша вторая линия, 2222 - ваша последняя строка и так далее.

источник

2012-06-08 21:43:10 zmbq

+1 для Awesome параллельно подсчету. Это трудно понять, потому что способ был разработан. Если бы он описал это как: Каждая из подкатегорий М должна упасть ровно в 1 из N категорий и создала карту из подкатегорий в категории в его объяснении, OP, вероятно, видел бы это. Удивительная находка. –

Это на самом деле проблема с перестановкой, как вы думали.

У вас есть N подкатегорий, которые необходимо поместить в категории М. Это очень похоже на stars and bars problem.

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

источник

2012-06-08 19:25:44

Это похоже на тот подход, который мне нужно принять. Я попробую его скопировать и отправить решение. Благодаря! – Paul

На следующем обзоре я не думаю, что этот подход будет работать. Кажется, звезды и бары работают только тогда, когда «один различает бункеры ... но никто не хочет отличать k звезд» *. По моему сценарию, «звезды» (подкатегории) различаются. – Paul

Вы правы; Я не прав. –

Возможные категории с использованием рекурсии

ответ

Смежные вопросы