- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
针对更大的树进行了编辑,以获取更多示例。
我有一个树结构,我需要生成所有可能的排列,但有一些限制。给定这样一棵树:
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 中解决这个问题,我也会接受。)
我希望遍历树并从顶层向下检索所有可能的“路径”。节点的所有后代组都必须由“路径”中的 1 个成员表示。例如,在A1中需要表示(B1,B2)之一和(C1)之一。因此,从 A1 下降的每条路径都将以以下任一方式开始:
A1 B1 C1
或
A1 B2 C1
如果 B1、B2 或 C1 有 child ,则也需要代表他们。
为上面的树手工计算,我得到了这些可能性:
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();
}
}
}
但这不是我需要的。这个问题是完整的树遍历,但是有特定的顺序。我没有得到什么?这是什么样的步行?
10 年前,我用 Perl 编写了一个困惑且缓慢的实现,但我无法再破译自己的代码(我感到羞耻!)。
编辑:下面的图表和列表已经扩展,代码没有。
如果我能描述图表,我就能对其进行编程。如果我知道它叫什么,我可以查一下。但我不能。那么让我进一步解释一下。
存储桶名称并不重要!
每个节点都有“子节点桶”。 A1 有两个桶,一个包含“B”,另一个包含“C”。如果这就是它的全部(并且 C 下没有桶),我将有“A1 B1 C1”和“A1 B2 C1”——所有子桶中至少有一个代表在场。
所以我认为每个桶都需要其子项的叉积(一直向下)。
最佳答案
使用以下子:
use 5.10.0; # for // (aka defined-or)
use subs 'enumerate';
sub enumerate {
my($root) = @_;
my $kids = $root->{children};
return [ $root->{name} // () ]
unless @$kids;
my @results;
foreach my $node (@{ $kids->[0] }) {
my @fronts = map [ $root->{name} // (), @$_ ],
enumerate $node;
my @below = enumerate {
name => undef,
children => [ @{$kids}[1 .. $#$kids ] ],
};
foreach my $a (@fronts) {
foreach my $b (@below) {
push @results => [ @$a, @$b ];
}
}
}
@results;
}
你可以打印它
foreach my $tree (@$nodes) {
foreach my $path (enumerate $tree) {
print "@$path\n";
}
print "\n";
}
得到如下输出:
A1 B1 C1 E1A1 B1 C1 E2A1 B2 C1 E1A1 B2 C1 E2A2 B3 D1 F1A2 B3 D1 F2 D4A2 B4 F1A2 B4 F2 D4A3 B5A3 B6 D2A3 B6 D3
I used $path
above, but it will seriously confuse anyone who maintains your code because path has a well-understood meaning. You could skirt the naming issue entirely with a bit of cleverness:
print join "\n" =>
map { join "" => map "@$_\n", @$_ }
map [ enumerate($_) ] => @$nodes;
关于c# - 检索树结构的所有排列的有效方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2102924/
我遇到了一个奇怪的问题。我有这个: $(document).ready(function () {
我正在编写一个程序,它从列表中读取一些 ID,从中找出不同的 URL,然后将图像保存到我的 C: 驱动器中。 如果我在浏览器中导航到图像 URL,它们就会起作用。此外,如果我尝试从不同的服务器获取图像
我编写了一个 REST WCF RIA Silverlight 4.0 兼容服务,我可以从 javascript + jQuery.1.4.2.js + JSON2.js(当然,还可以从 .NET 4
我很确定这个网站实际上还没有得到回答。一劳永逸地,与 32 位有符号整数范围内的数字字符串匹配的最小正则表达式是什么,范围是 -2147483648至 2147483647 . 我必须使用正则表达式进
我有两个data.table;我想从那些与键匹配的元素中随机分配一个元素。我现在这样做的方式相当慢。 让我们具体点;这是一些示例数据: dt1<-data.table(id=sample(letter
我已经安装了 celery 、RabitMQ 和花。我可以浏览到花港。我有以下简单的工作人员,我可以将其附加到 celery 并从 python 程序调用: # -*- coding: utf-8 -
我正在使用 ScalaCheck 在 ScalaTest 中进行一些基于属性的测试。假设我想测试一个函数,f(x: Double): Double仅针对 x >= 0.0 定义的, 并返回 NaN对于
我想检查文件是否具有有效的 IMAGE_DOS_SIGNATURE (MZ) function isMZ(FileName : String) : boolean; var Signature: W
在 Herbert Schildt 的“Java:完整引用,第 9 版”中,有一个让我有点困惑的例子。它的关键点我无法理解可以概括为以下代码: class Test { public stat
我在工作中查看了一些代码,发现了一些我以前没有遇到过的东西: for (; ;) { // Some code here break; } 我们一直调用包含这个的函数,我最近才进去看看它是
在 Herbert Schildt 的“Java:完整引用,第 9 版”中,有一个让我有点困惑的例子。它的关键点我无法理解可以概括为以下代码: class Test { public stat
我试图编写一个函数,获取 2D 点矩阵和概率 p 并以概率 p 更改或交换每个点坐标 所以我问了一个question我试图使用二进制序列作为特定矩阵 swap_matrix=[[0,1],[1,0]]
这个问题在这里已经有了答案: Using / or \\ for folder paths in C# (5 个答案) 关闭 7 年前。 我在某个Class1中有这个功能: public v
PostgreSQL 10.4 我有一张 table : Column | Type ------------------------- id | integer| title
我正在 Postgresql 中编写一个函数,它将返回一些针对特定时区(输入)计算的指标。 示例结果: 主要问题是这只是一个指标。我需要从其他表中获取其他 9 个指标。 对于实现此目标的更简洁的方法有
我需要在 python 中模拟超几何分布(用于不替换采样元素的花哨词)。 设置:有一个装满人口许多弹珠的袋子。弹珠有两种类型,红色和绿色(在以下实现中,弹珠表示为 True 和 False)。从袋子中
我正在使用 MaterializeCSS 框架并动态填充文本输入。我遇到的一个问题是,在我关注该字段之前,valid 和 invalid css 类不会添加到我的字段中。 即使我调用 M.update
是否有重叠 2 个 div 的有效方法。 我有以下内容,但无法让它们重叠。 #top-border{width:100%; height:60px; background:url(image.jpg)
我希望你们中的一位能向我解释为什么编译器要求我在编译单元中重新定义一个静态固定长度数组,尽管我已经在头文件中这样做了。这是一个例子: 我的类.h: #ifndef MYCLASS_H #define
我正在使用旧线程发布试图解决相同问题的新代码。什么是安全 pickle ? this? socks .py from socket import socket from socket import A
我是一名优秀的程序员,十分优秀!