Отредактировано для большего дерева, для большего количества примеров.
У меня есть древовидная структура, которая мне нужна для генерации всех возможных перестановок, с некоторыми ограничениями. Учитывая дерево как это:
A1----(B1, B2)
\
\___(C1)
\__(E1, E2)
/
- A2----(B3, B4)
\ \ \
\ \__(D1)
\
\_(F1, F2)
|
(D4)
A3----(B5, B6)
\__(D2, D3)
Или, если это немного расплывчато, вот та же самая структура, сделанная с нотацией Perl:
my $nodes = [
{
name => 'A1',
children => [
[ { name => 'B1', children => [] },
{ name => 'B2', children => [] }
],
[
{ name => 'C1',
children => [
[
{ name => 'E1', children => [] },
{ name => 'E2', children => [] }
]
]
}
]
]
},
{
name => 'A2',
children => [
[ { name => 'B3',
children => [
[
{ name => 'D1', children => [] }
]
]
},
{ name => 'B4', children => [] }
],
[
{ name => 'F1', children => [] },
{ name => 'F2', children => [
[ { name => 'D4', children => [] } ]
]
}
]
]
},
{
name => 'A3',
children => [
[ { name => 'B5', children => [] },
{ name => 'B6', children => [
[ { name => 'D2', children => [] },
{ name => 'D3', children => [] }
]
]
}
]
]
}
];
(Честно говоря, если вы сможете понять это в удобочитаемом Perl, я тоже это приму.)
Я пытаюсь пройтись по дереву и получить все возможные "пути" с верхнего уровня вниз. Все группы-потомки узла должны быть представлены ровно одним членом в «пути». Например, в A1 должен быть представлен один из (B1, B2) и один из (C1). Таким образом, каждый путь, начинающийся с A1, будет начинаться с:
A1 B1 C1
или
A1 B2 C1
Если у B1, B2 или C1 есть дети, их также необходимо представить.
Работая вручную для вышеприведенного дерева, я получаю следующие возможности:
A1 B1 C1 E1
A1 B1 C1 E2
A1 B2 C1 E1
A1 B2 C1 E2
A2 B3 D1 F1
A2 B3 D1 F2 D4
A2 B4 F1
A2 B4 F2 D4
A3 B5
A3 B6 D2
A3 B6 D3
Каждый узел здесь является объектом DataRow:
internal class DataRow
{
internal string tag = "";
internal int id = 0;
internal Dictionary<string, List<DataRow>> children = null;
internal DataRow(int id, string tagname)
{
this.tag = tagname;
this.id = id;
} internal void AddChildren(string type, List<DataRow> drList)
{
if (children == null)
children = new Dictionary<string, List<DataRow>>();
if (!children.ContainsKey(type))
children[type] = new List<DataRow>();
children[type].AddRange(drList);
}
internal void AddChild(string type, DataRow dr)
{
List<DataRow> drList = new List<DataRow>();
drList.Add(dr);
AddChildren(type, drList);
}
public override string ToString()
{
return this.tag + " " + this.id;
}
}
Чтобы построить образец дерева выше (кроме уровней E и F, добавленных позже):
DataRow fullList = new DataRow(null, "");
DataRow dr, dr2, dr3;
// First node above
dr = new DataRow(1, "A");
List<DataRow> drList = new List<DataRow>();
drList.Add(new DataRow(1, "B"));
drList.Add(new DataRow(2, "B"));
dr.AddChildren("B", drList);
drList.Clear();
dr2 = new DataRow(1, "C");
dr2.AddChild("C", new DataRow(1, "E"));
dr2.AddChild("C", new DataRow(2, "E"));
drList.Add(dr2);
dr.AddChildren("C", drList);
fullList.AddChild("A", dr);
// Second Node above (without the "F" stuff)
drList.Clear();
dr = new DataRow(3, "B");
dr.AddChild("D", new DataRow(1, "D"));
drList.Add(dr);
drList.Add(new DataRow(4, "B"));
dr = new DataRow(2, "A");
dr.AddChildren("B", drList);
fullList.AddChild("A", dr);
// Third node above
drList.Clear();
dr3 = new DataRow(6, "B");
dr3.AddChild("B", new DataRow(2, "D"));
dr3.AddChild("B", new DataRow(3, "D"));
dr2 = new DataRow(3, "A");
dr2.AddChild("B", new DataRow(5, "B"));
dr2.AddChild("B", dr3);
fullList.AddChild("A", dr2);
Ходить по всему дереву тривиально:
internal void PermutedList()
{
if ( children == null ) return;
foreach (string kidType in children.Keys)
{
foreach (DataRow dr in children[kidType])
{
dr.PermutedList();
}
}
}
Но это не то, что мне нужно. Эта проблема - полная прогулка по дереву, но в определенном порядке. Что я не получаю? Что это за прогулка?
У меня грязная и медленная реализация, которую я написал на Perl 10 лет назад, но я больше не могу расшифровывать свой собственный код (позор мне!).
Edit:
График и списки ниже были расширены, код не имеет.
Если бы я мог описать график, я бы запрограммировал его. Если бы я знал, как это называется, я мог бы найти это. Но я не могу. Итак, позвольте мне объяснить немного подробнее.
Названия ведер не имеют значения!
У каждого узла есть «корзины детей». A1 имеет два контейнера, один из которых содержит «B», а другой - «C». Если бы это все, что у него было (а у С не было корзин под ним), у меня были бы «А1 В1 С1» и «А1 В2 С1» - по крайней мере, один представитель из всех присутствующих дочерних ведер.
Так что я думаю, что каждое ведро нуждается в перекрестном произведении своих детей (до конца).