c# - 如何确定所有排列 &|层次结构中的组合

Question

我正在尝试找出一种方法来确定假想层次结构中父 <> 子关系的所有可能组合。 (组合或排列 - 一旦你弄清楚了所有的排列，你也得到了可能的组合)。

约束

节点之间的关系可以是 1:1、1:many 或 many to 1，但绝不能是 many:many。当考虑与任何其他给定祖先或父节点的关系时，层次结构中的每个节点都可以具有附加到其关系的 3 个属性中的 1 个。

例如

A -> B(A 是 B 的祖先)

A(X) -> B(A 是具有属性 X 的 B 的祖先)

A(Y) -> B(A 是具有属性 Y 的 B 的祖先)

A(Z) -> B(A 是具有属性 Z 的 B 的祖先)

上述所有 4 个关系都是有效结果。

同理；

A & B -> C(A和B都是C的祖先)

A (X) & B(X) -> C(A 和 B 都是 C 的祖先，A 有 X，B 有 X)

A (X) & B(Y) -> C(同上，但现在 A & B 在此示例中具有 X & Y 属性)

以上3个也是完全有效的。

所以在伪代码中；

foreach(totalNodePopulation 中的节点 someNode)

{尝试与每个祖先的每个组合 SomeCombination | child

foreach(组合中的一些组合)

{ 确定所有 3 个变体}

下面的这段代码确定了简单 Int 列表的所有组合；

public Dictionary<int, List<int>> shouldReturnAllPossibleCombinations(List<int> number)
    {
        Dictionary<int, List<int>> combos = new Dictionary<int, List<int>>();

        double count = Math.Pow(2, number.Count);
        for (int i = 1; i <= count - 1; i++)
        {
            List<int> itemsInThisCombo = new List<int>();

            string str = Convert.ToString(i, 2).PadLeft(number.Count, '0');
            for (int j = 0; j < str.Length; j++)
            {
                if (str[j] == '1')
                {
                    System.Diagnostics.Debug.Write(number[j]);
                    itemsInThisCombo.Add(number[j]);
                }
            }
            combos.Add(i, itemsInThisCombo);
            System.Diagnostics.Debug.WriteLine(Environment.NewLine);
        }

        return combos;
    }

但是如何改进它以应对变体的“维度”？

非常感谢任何想法/指示，谢谢!

Answer 1

这是你的想法吗？

public class Node {
    public string Name { get; set; }
    public override string ToString() => Name;
}

public static List<(Node node1, Node node2, string relationship)> PossibleCombinations(List<Node> lst) {
    var ret = new List<(Node node1, Node node2, string relationship)>();
    var relationships = new string[] { null, "X", "Y", "Z" };
    foreach (var node1 in lst) {
        foreach (var node2 in lst) {
            if (node1==node2) { continue; }
            foreach (var relationship in relationships) {
                ret.Add((node1, node2, relationship));
            }
        }
    }
    return ret;
}

var lst = new List<Node>() {
    new Node() {Name="A"},
    new Node() {Name="B"},
    new Node() {Name="C"}
};
foreach (var node in lst) {
    foreach (var combination_variant in PossibleCombinations(lst)) {
        Console.WriteLine($"{node} - {combination_variant});
    }
}

AFAICT 这是您原始伪代码描述的反射(reflect):

foreach (node someNode in totalNodePopulation)
    {try every combination SomeCombination with every ancestor | child }
    foreach (somecombination in combinations)
       { determine all 3 variants}