Как определить все перестановки и | комбинации в иерархической структуре - PullRequest
Новая
       23

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

0 голосов
/ 08 мая 2018

Я пытаюсь найти метод для определения каждой возможной комбинации родительских <> дочерних отношений в воображаемой иерархии. (Комбинация или перестановка - как только вы выяснили все перестановки, у вас также есть возможные комбинации).

Ограничения

Отношения между узлами могут быть 1: 1, 1: много или много к 1, но никогда не много: много. Каждый узел в иерархии может иметь 1 из 3 свойств, связанных с его отношением, если учитывать их отношение к любому другому данному предку или родительскому узлу.

Например

A -> B (A является предком B)

A (X) -> B (A является предком B со свойством X)

A (Y) -> B (A является предком B со свойством Y)

A (Z) -> B (A является предком B со свойством Z) * ​​1017 *

Все 4 приведенных выше отношения являются действительными результатами.

Аналогично; * +1021 *

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 (узел someNode в totalNodePopulation)

{попробуйте каждую комбинацию SomeCombination с каждым предком | ребенок}

foreach (некоторая комбинация в комбинациях)

{определить все 3 варианта}

Этот код ниже определяет все комбинации простого списка Ints; 

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;
    }

Но как тогда улучшить его, чтобы справиться с "размерностью" вариантов?

Любые идеи / указатели высоко ценится, спасибо!

1 Ответ

0 голосов
/ 08 мая 2018

Это то, что вы имеете в виду? 

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, это отражение вашего оригинального описания psuedocode: 

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