c# - रफल - सिद्ध करे कि त्रिभुज के तीनों कोणों का योग 180 होता है




सी#में एक त्रिभुज कैसे बनाएँ (5)

क्या किसी को पता है कि मैं सी # में एक trie बनाने के लिए एक उदाहरण मिल सकता है। मैं शब्दों का एक शब्दकोश / सूची लेने और इसके साथ एक तिहाई बनाने की कोशिश कर रहा हूं।


इस कोडप्लेक्स प्रोजेक्ट पर एक नज़र डालें:

https://trienet.codeplex.com/

यह एक पुस्तकालय है जिसमें अच्छी तरह से परीक्षण किए गए जेनेरिक सी # त्रिभुज वर्गों के कई अलग-अलग प्रकार होते हैं जिनमें पेट्रीसिया ट्राई और समांतर त्रिभुज शामिल हैं।

  • Trie - सरल ट्राई, केवल उपसर्ग खोज की अनुमति देता है, जैसे। .Where(s => s.StartsWith(searchString))
  • SuffixTrie - SuffixTrie खोज को भी अनुमति देता है, जैसे। .Where(s => s.Contains(searchString))
  • PatriciaTrie - संपीड़ित trie, अधिक कॉम्पैक्ट, लुकअप के दौरान थोड़ा और अधिक कुशल, लेकिन एक धीमी durig build-up।
  • SuffixPatriciaTrie - PatriciaTrie के समान, SuffixPatriciaTrie खोज को सक्षम बनाता है।
  • ParallelTrie - बहुत प्राइमेटिव रूप से समानांतर डेटा संरचना लागू होती है जो डेटा को जोड़ने और परिणामों को एक साथ अलग-अलग धागे से प्राप्त करने की अनुमति देती है।

एक साधारण ट्री कार्यान्वयन।

http://github.com/bharathkumarms/AlgorithmsMadeEasy/blob/master/AlgorithmsMadeEasy/Tries.cs

using System;
using System.Collections.Generic;
using System.Linq;

namespace AlgorithmsMadeEasy
{
    class Tries
    {
        TrieNode root;

        public void CreateRoot()
        {
            root = new TrieNode();
        }

        public void Add(char[] chars)
        {
            TrieNode tempRoot = root;
            int total = chars.Count() - 1;
            for (int i = 0; i < chars.Count(); i++)
            {
                TrieNode newTrie;
                if (tempRoot.children.Keys.Contains(chars[i]))
                {
                    tempRoot = tempRoot.children[chars[i]];
                }
                else
                {
                    newTrie = new TrieNode();

                    if (total == i)
                    {
                        newTrie.endOfWord = true;
                    }

                    tempRoot.children.Add(chars[i], newTrie);
                    tempRoot = newTrie;
                }
            }
        }

        public bool FindPrefix(char[] chars)
        {
            TrieNode tempRoot = root;
            for (int i = 0; i < chars.Count(); i++)
            {
                if (tempRoot.children.Keys.Contains(chars[i]))
                {
                    tempRoot = tempRoot.children[chars[i]];
                }
                else
                {
                    return false;
                }
            }
            return true;
        }

        public bool FindWord(char[] chars)
        {
            TrieNode tempRoot = root;
            int total = chars.Count() - 1;
            for (int i = 0; i < chars.Count(); i++)
            {
                if (tempRoot.children.Keys.Contains(chars[i]))
                {
                    tempRoot = tempRoot.children[chars[i]];

                    if (total == i)
                    {
                        if (tempRoot.endOfWord == true)
                        {
                            return true;
                        }
                    }
                }
                else
                {
                    return false;
                }
            }
            return false;
        }
    }

    public class TrieNode
    {
        public Dictionary<char, TrieNode> children = new Dictionary<char, TrieNode>();
        public bool endOfWord;
    }
}

/*
Calling Code:
    Tries t = new Tries();
    t.CreateRoot();
    t.Add("abc".ToCharArray());
    t.Add("abgl".ToCharArray());
    t.Add("cdf".ToCharArray());
    t.Add("abcd".ToCharArray());
    t.Add("lmn".ToCharArray());

    bool findPrefix1 = t.FindPrefix("ab".ToCharArray());
    bool findPrefix2 = t.FindPrefix("lo".ToCharArray());

    bool findWord1 = t.FindWord("lmn".ToCharArray());
    bool findWord2 = t.FindWord("ab".ToCharArray());
    bool findWord3 = t.FindWord("cdf".ToCharArray());
    bool findWord4 = t.FindWord("ghi".ToCharArray());
*/

नीचे यूआरआई के आलेख में अन्य .NET संग्रह के साथ बहुत अच्छा कार्यान्वयन और तुलना है। यह परिदृश्य भी निर्दिष्ट करता है जहां हमें संग्रह में .NET निर्माण के बजाय ट्री का उपयोग करना चाहिए (हैशसेट <>, सॉर्टेडलिस्ट <>) इत्यादि।

https://visualstudiomagazine.com/articles/2015/10/20/text-pattern-search-trie-class-net.aspx


मैंने अभी सी # में एक Trie कार्यान्वयन बनाया है:

https://github.com/TomGullen/C-Sharp-Trie/tree/master

कोड:

/*
    Copyright (c) 2016 Scirra Ltd
    www.scirra.com

    Permission is hereby granted, free of charge, to any person obtaining a copy
    of this software and associated documentation files (the "Software"), to deal
    in the Software without restriction, including without limitation the rights
    to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
    copies of the Software, and to permit persons to whom the Software is
    furnished to do so, subject to the following conditions:

    The above copyright notice and this permission notice shall be included in all
    copies or substantial portions of the Software.

    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
    IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
    FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
    AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
    LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
    OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
    SOFTWARE.
 */
public class Trie
{
    private class Node
    {
        public bool Terminal { get; set; }
        public Dictionary<char, Node> Nodes { get; private set; }
        public Node ParentNode { get; private set; }
        public char C { get; private set; }

        /// <summary>
        /// String word represented by this node
        /// </summary>
        public string Word
        {
            get
            {
                var b = new StringBuilder();
                b.Insert(0, C.ToString(CultureInfo.InvariantCulture));
                var selectedNode = ParentNode;
                while (selectedNode != null)
                {
                    b.Insert(0, selectedNode.C.ToString(CultureInfo.InvariantCulture));
                    selectedNode = selectedNode.ParentNode;
                }
                return b.ToString();
            }
        }

        public Node(Node parent, char c)
        {
            C = c;
            ParentNode = parent;
            Terminal = false;
            Nodes = new Dictionary<char, Node>();
        }

        /// <summary>
        /// Return list of terminal nodes under this node
        /// </summary>
        public IEnumerable<Node> TerminalNodes(char? ignoreChar = null)
        {
            var r = new List<Node>();
            if (Terminal) r.Add(this);
            foreach (var node in Nodes.Values)
            {
                if (ignoreChar != null && node.C == ignoreChar) continue;
                r = r.Concat(node.TerminalNodes()).ToList();
            }
            return r;
        } 
    }

    private Node TopNode_ { get; set; }
    private Node TopNode
    {
        get
        {
            if (TopNode_ == null) TopNode_ = new Node(null, ' ');
            return TopNode_;
        }
    }
    private bool CaseSensitive { get; set; }

    /// <summary>
    /// Get list of all words in trie that start with
    /// </summary>
    public HashSet<string> GetAutocompleteSuggestions(string wordStart, int fetchMax = 10)
    {
        if(fetchMax <= 0) throw new Exception("Fetch max must be positive integer.");

        wordStart = NormaliseWord(wordStart);

        var r = new HashSet<string>();

        var selectedNode = TopNode;
        foreach (var c in wordStart)
        {
            // Nothing starting with this word
            if (!selectedNode.Nodes.ContainsKey(c)) return r;
            selectedNode = selectedNode.Nodes[c];
        }

        // Get terminal nodes for this node
        {
            var terminalNodes = selectedNode.TerminalNodes().Take(fetchMax);
            foreach (var node in terminalNodes)
            {
                r.Add(node.Word);
            }
        }

        // Go up a node if not found enough suggestions
        if (r.Count < fetchMax)
        {
            var parentNode = selectedNode.ParentNode;
            if (parentNode != null)
            {
                var remainingToFetch = fetchMax - r.Count;
                var terminalNodes = parentNode.TerminalNodes(selectedNode.C).Take(remainingToFetch);
                foreach (var node in terminalNodes)
                {
                    r.Add(node.Word);
                }
            }
        }

        return r;
    } 

    /// <summary>
    /// Initialise instance of trie with set of words
    /// </summary>
    public Trie(IEnumerable<string> words, bool caseSensitive = false)
    {
        CaseSensitive = caseSensitive;
        foreach (var word in words)
        {
            AddWord(word);
        }
    }

    /// <summary>
    /// Add a single word to the trie
    /// </summary>
    public void AddWord(string word)
    {
        word = NormaliseWord(word);
        var selectedNode = TopNode;

        for (var i = 0; i < word.Length; i++)
        {
            var c = word[i];
            if (!selectedNode.Nodes.ContainsKey(c))
            {
                selectedNode.Nodes.Add(c, new Node(selectedNode, c));
            }
            selectedNode = selectedNode.Nodes[c];
        }
        selectedNode.Terminal = true;
    }

    /// <summary>
    /// Normalise word for trie
    /// </summary>
    private string NormaliseWord(string word)
    {
        if (String.IsNullOrWhiteSpace(word)) word = String.Empty;
        word = word.Trim();
        if (!CaseSensitive)
        {
            word = word.Trim();
        }
        return word;
    }

    /// <summary>
    /// Does this word exist in this trie?
    /// </summary>
    public bool IsWordInTrie(string word)
    {
        word = NormaliseWord(word);
        if (String.IsNullOrWhiteSpace(word)) return false;
        var selectedNode = TopNode;
        foreach (var c in word)
        {
            if (!selectedNode.Nodes.ContainsKey(c)) return false;
            selectedNode = selectedNode.Nodes[c];
        }
        return selectedNode.Terminal;
    }
}

उदाहरण का उपयोग:

var trie = new Trie(new String[] {"hello", "help", "he-man", "happy", "hoppy", "tom"});

var autoCompleteSuggestions = trie.GetAutocompleteSuggestions("ha");
foreach (var s in autoCompleteSuggestions)
{
    Response.Write(s + "\n");
}

यहां एक ट्री और एक स्कैनर है ( Resin कोडबेस से लिया गया):

using System;
using System.Collections.Generic;
using System.IO;

namespace Resin
{
    public class UseTrie
    {
        public void Main()
        {
            var words = new[]{"pre", "prefix"};
            var trie = new Trie(words);

            // Print "pre" and "prefix"
            foreach(var word in trie.GetTokens("pr"))
            {
                Console.WriteLine(word);
            }
        }
    }
    public class Trie
    {
        public char Value { get; set; }

        public bool Eow { get; set; }

        public IDictionary<char, Trie> Children { get; set; }

        public bool Root { get; set; }

        public Trie(bool isRoot)
        {
            Root = isRoot;
            Children = new Dictionary<char, Trie>();
        }

        public Trie(IList<string> words)
        {
            if (words == null) throw new ArgumentNullException("words");

            Root = true;
            Children = new Dictionary<char, Trie>();

            foreach (var word in words)
            {
                AppendToDescendants(word);
            }
        }

        public Trie(string text)
        {
            if (string.IsNullOrWhiteSpace(text))
            {
                throw new ArgumentException("text");
            }

            Value = text[0];

            Children = new Dictionary<char, Trie>();

            if (text.Length > 1)
            {
                var overflow = text.Substring(1);
                if (overflow.Length > 0)
                {
                    AppendToDescendants(overflow);
                }
            }
            else
            {
                Eow = true;
            }
        }

        public IEnumerable<string> GetTokens(string prefix)
        {
            var words = new List<string>();
            Trie child;
            if (Children.TryGetValue(prefix[0], out child))
            {
                child.Scan(prefix, prefix, ref words);
            }
            return words;
        }

        private void Scan(string originalPrefix, string prefix, ref List<string> words)
        {
            if (string.IsNullOrWhiteSpace(prefix)) throw new ArgumentException("prefix");

            if (prefix.Length == 1 && prefix[0] == Value)
            {
                // The scan has reached its destination. Find words derived from this node.
                if (Eow) words.Add(originalPrefix);
                foreach (var node in Children.Values)
                {
                    node.Scan(originalPrefix+node.Value, new string(new []{node.Value}), ref words);
                }
            }
            else if (prefix[0] == Value)
            {
                Trie child;
                if (Children.TryGetValue(prefix[1], out child))
                {
                    child.Scan(originalPrefix, prefix.Substring(1), ref words);
                }
            }
        }

        public void AppendToDescendants(string text)
        {
            if (string.IsNullOrWhiteSpace(text)) throw new ArgumentException("text");

            Trie child;
            if (!Children.TryGetValue(text[0], out child))
            {
                child = new Trie(text);
                Children.Add(text[0], child);
            }
            else
            {
                child.Append(text);
            }
        }

        public void Append(string text)
        {
            if (string.IsNullOrWhiteSpace(text)) throw new ArgumentException("text");
            if (text[0] != Value) throw new ArgumentOutOfRangeException("text");
            if (Root) throw new InvalidOperationException("When appending from the root, use AppendToDescendants.");

            var overflow = text.Substring(1);
            if (overflow.Length > 0)
            {
                AppendToDescendants(overflow);
            }
        }
    }
}






trie