Реализация PQ-Tree, семейство перестановок на множестве элементов
Нашел несколько хороших статей на тему PQ-Tree и решил написать эту структуру данных уже на C#, потому что не нашел не одного варианта реализации на данном язык
Статья: https://www.duo.uio.no/bitstream/handle/10852/8874/GVollen.pdf?sequence=1 страница 12
Статья гугл-инженера: https://gregable.com/2008/11/pq-tree-algorithm.html
Если есть какие-то рекомендации или замечания пишите. Пока только начал писать. Так же если есть люди которые разбираются хорошо, можете объяснить методы ограничения, которые делаются в два этапа Bubble and Blocks
Мейн класс
using System;
using System.Collections.Generic;
namespace PQTree
{
class Program
{
static void Main(string[] args)
{
Console.Write("Введите основное мн-во для PQ дерева: "); //Указываем множество
var plenty = IntSequence();
if (plenty.Length < 2)
throw new Exception("Множество PQ-дерева не может состоять менее чем из 2 элементов"); //т.к P-Node обязан хранить 2 и более объектов и делаем условие.
var tree = new PqTree(plenty);
Console.ReadLine();
//.............................................
}
private static int[] IntSequence() => Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse); //Считаем данные в строку
}
}
Ноды
using System.Collections.Generic;
//Так же нам важно чтобы каждый из узлов хранил колекцию объектов это могут быть как листовые узлы так и внутренние
namespace PQTree
{
public class InnerNode {}
public class QNode : InnerNode //Должны иметь 3 и более потомков
{
public List<InnerNode> childrenQNode = new List<InnerNode>();
}
public class PNode : InnerNode //Должны иметь 2 и более потомков
{
public List<InnerNode> childrenPNode = new List<InnerNode>();
}
public class LeafNode : InnerNode
{
public InnerNode Parent { get; private set; }
public int Value;
public LeafNode(int value, InnerNode parent)
{
Value = value;
Parent = parent;
}
}
}
Само дерево
using System.Collections.Generic;
namespace PQTree
{
public class PqTree //Изначально когда мы задаем дерево, на его вход должно поступать множество с которым мы будем работать. При том корень такого дерева должен быть PNode
{
private InnerNode _root;
public PqTree(int[] values)
{
_root = new PNode();
var root = _root as PNode;
foreach (var item in values)
{
var temp = new LeafNode(item, root);
root.childrenPNode.Add(temp);
}
}
//Далее мы будем задавать методы такие как: выделения подмножества и ограничения.
}
}