Skip to content

Latest commit

 

History

History
877 lines (569 loc) · 35.5 KB

README.md

File metadata and controls

877 lines (569 loc) · 35.5 KB
Raw

The Algorithms - Go

Gitpod Ready-to-Code  golangci-lint godocmd   update_directory_md Discord chat 

Algorithms implemented in Go (for education)

The repository is a collection of open-source implementation of a variety of algorithms implemented in Go and licensed under MIT License.

Read our Contribution Guidelines before you contribute.

List of Algorithms

Packages:

ahocorasick
Functions:
  1. Advanced: Advanced Function performing the Advanced Aho-Corasick algorithm. Finds and prints occurrences of each pattern.
  2. AhoCorasick: AhoCorasick Function performing the Basic Aho-Corasick algorithm. Finds and prints occurrences of each pattern.
  3. ArrayUnion: ArrayUnion Concats two arrays of int's into one.
  4. BoolArrayCapUp: BoolArrayCapUp Dynamically increases an array size of bool's by 1.
  5. BuildAc: Functions that builds Aho Corasick automaton.
  6. BuildExtendedAc: BuildExtendedAc Functions that builds extended Aho Corasick automaton.
  7. ComputeAlphabet: ComputeAlphabet Function that returns string of all the possible characters in given patterns.
  8. ConstructTrie: ConstructTrie Function that constructs Trie as an automaton for a set of reversed & trimmed strings.
  9. Contains: Contains Returns 'true' if array of int's 's' contains int 'e', 'false' otherwise.
  10. CreateNewState: CreateNewState Automaton function for creating a new state 'state'.
  11. CreateTransition: CreateTransition Creates a transition for function σ(state,letter) = end.
  12. GetParent: GetParent Function that finds the first previous state of a state and returns it. Used for trie where there is only one parent.
  13. GetTransition: GetTransition Returns ending state for transition σ(fromState,overChar), '-1' if there is none.
  14. GetWord: GetWord Function that returns word found in text 't' at position range 'begin' to 'end'.
  15. IntArrayCapUp: IntArrayCapUp Dynamically increases an array size of int's by 1.
  16. StateExists: StateExists Checks if state 'state' exists. Returns 'true' if it does, 'false' otherwise.
Types
  1. Result: No description provided.
avl
Package avl is a Adelson-Velskii and Landis tree implemnation avl is self-balancing tree, i.e for all node in a tree, height difference between its left and right child will not exceed 1 more information : https://en.wikipedia.org/wiki/AVL_tree
Functions:
  1. Delete: Delete : remove given key from the tree
  2. Get: Get : return node with given key
  3. Insert: Insert a new item
  4. NewTree: NewTree create a new AVL tree
Types
  1. Node: No description provided.
binary
Package binary describes algorithms that use binary operations for different calculations.
Functions:
  1. BitCounter: BitCounter - The function returns the number of set bits for an unsigned integer number
  2. IsPowerOfTwo: IsPowerOfTwo This function uses the fact that powers of 2 are represented like 10...0 in binary, and numbers one less than the power of 2 are represented like 11...1. Therefore, using the and function: 10...0 & 01...1 00...0 -> 0 This is also true for 0, which is not a power of 2, for which we have to add and extra condition.
  3. IsPowerOfTwoLeftShift: IsPowerOfTwoLeftShift This function takes advantage of the fact that left shifting a number by 1 is equivalent to multiplying by 2. For example, binary 00000001 when shifted by 3 becomes 00001000, which in decimal system is 8 or = 2 * 2 * 2
  4. MeanUsingAndXor: No description provided.
  5. MeanUsingRightShift: No description provided.
  6. ReverseBits: ReverseBits This function initialized the result by 0 (all bits 0) and process the given number starting from its least significant bit. If the current bit is 1, set the corresponding most significant bit in the result and finally move on to the next bit in the input number. Repeat this till all its bits are processed.
  7. XorSearchMissingNumber: No description provided.
binarytree
Functions:
  1. AccessNodesByLayer: AccessNodesByLayer Function that access nodes layer by layer instead of printing the results as one line.
  2. BstDelete: BstDelete removes the node
  3. InOrder: Travers the tree in the following order left --> root --> right
  4. InOrderSuccessor: InOrderSuccessor Goes to the left
  5. Insert: Insert a value in the BSTree
  6. LevelOrder: No description provided.
  7. Max: Max Function that returns max of two numbers - possibly already declared.
  8. NewNode: NewNode Returns a new pointer to an empty Node
  9. PostOrder: Travers the tree in the following order left --> right --> root
  10. PreOrder: Travers the tree in the following order root --> left --> right
Types

  1. BSTree: No description provided.

  2. Node: No description provided.

caesar
Package caesar is the shift cipher ref: https://en.wikipedia.org/wiki/Caesar_cipher
Functions:
  1. Decrypt: Decrypt decrypts by left shift of "key" each character of "input"
  2. Encrypt: Encrypt encrypts by right shift of "key" each character of "input"
catalan
Functions:
  1. CatalanNumber: No description provided.
coloring
Package coloring provides implementation of different graph coloring algorithms, e.g. coloring using BFS, using Backtracking, using greedy approach. Author(s): Shivam
Functions:
  1. BipartiteCheck: basically tries to color the graph in two colors if each edge connects 2 differently colored nodes the graph can be considered bipartite
Types
  1. Graph: No description provided.
combination
Package combination ...
Functions:
  1. Start: Start ...
Types
  1. Combinations: No description provided.
conversion
Package conversion is a package of implementations which converts one data structure to another.
Functions:
  1. BinaryToDecimal: BinaryToDecimal() function that will take Binary number as string, and return it's Decimal equivalent as integer.
  2. DecimalToBinary: DecimalToBinary() function that will take Decimal number as int, and return it's Binary equivalent as string.
  3. HEXToRGB: HEXToRGB splits an RGB input (e.g. a color in hex format; 0x) into the individual components: red, green and blue
  4. IntToRoman: IntToRoman converts an integer value to a roman numeral string. An error is returned if the integer is not between 1 and 3999.
  5. RGBToHEX: RGBToHEX does exactly the opposite of HEXToRGB: it combines the three components red, green and blue to an RGB value, which can be converted to e.g. Hex
  6. Reverse: Reverse() function that will take string, and returns the reverse of that string.
  7. RomanToInteger: RomanToInteger converts a roman numeral string to an integer. Roman numerals for numbers outside the range 1 to 3,999 will return an error. Nil or empty string return 0 with no error thrown.
diffiehellman
Package diffiehellman implements Deffie Hellman Key Exchange Algorithm for more information watch : https://www.youtube.com/watch?v=NmM9HA2MQGI
Functions:
  1. GenerateMutualKey: GenerateMutualKey : generates a mutual key that can be used by only alice and bob mutualKey = (shareKey^prvKey)%primeNumber
  2. GenerateShareKey: GenerateShareKey : generates a key using client private key , generator and primeNumber this key can be made public shareKey = (g^key)%primeNumber
dynamic
Package dynamic is a package of certain implementations of dynamically run algorithms.
Functions:
  1. Bin2: Bin2 function
  2. CutRodDp: CutRodDp solve the same problem using dynamic programming
  3. CutRodRec: CutRodRec solve the problem recursively: initial approach
  4. EditDistanceDP: EditDistanceDP is an optimised implementation which builds on the ideas of the recursive implementation. We use dynamic programming to compute the DP table where dp[i][j] denotes the edit distance value of first[0..i-1] and second[0..j-1]. Time complexity is O(m * n) where m and n are lengths of the strings, first and second respectively.
  5. EditDistanceRecursive: EditDistanceRecursive is a naive implementation with exponential time complexity.
  6. IsSubsetSum: No description provided.
  7. Knapsack: Knapsack solves knapsack problem return maxProfit
  8. LongestCommonSubsequence: LongestCommonSubsequence function
  9. LongestIncreasingSubsequence: LongestIncreasingSubsequence returns the longest increasing subsequence where all elements of the subsequence are sorted in increasing order
  10. LpsDp: LpsDp function
  11. LpsRec: LpsRec function
  12. MatrixChainDp: MatrixChainDp function
  13. MatrixChainRec: MatrixChainRec function
  14. Max: Max function - possible duplicate
  15. NthCatalanNumber: NthCatalan returns the n-th Catalan Number Complexity: O(n²)
  16. NthFibonacci: NthFibonacci returns the nth Fibonacci Number
dynamicarray
Package dynamicarray A dynamic array is quite similar to a regular array, but its Size is modifiable during program runtime, very similar to how a slice in Go works. The implementation is for educational purposes and explains how one might go about implementing their own version of slices. For more details check out those links below here: GeeksForGeeks article : https://www.geeksforgeeks.org/how-do-dynamic-arrays-work/ Go blog: https://blog.golang.org/slices-intro Go blog: https://blog.golang.org/slices authors Wesllhey Holanda, Milad see dynamicarray.go, dynamicarray_test.go
Types
  1. DynamicArray: No description provided.
factorial
Package factorial describes algorithms Factorials calculations.
Functions:
  1. BruteForceFactorial: No description provided.
  2. CalculateFactorialUseTree: No description provided.
  3. RecursiveFactorial: No description provided.
gcd
Functions:
  1. Extended: Extended simple extended gcd
  2. ExtendedIterative: ExtendedIterative finds and returns gcd(a, b), x, y satisfying ax + by = gcd(a, b).
  3. ExtendedRecursive: ExtendedRecursive finds and returns gcd(a, b), x, y satisfying ax + by = gcd(a, b).
  4. Iterative: Iterative Faster iterative version of GcdRecursive without holding up too much of the stack
  5. Recursive: Recursive finds and returns the greatest common divisor of a given integer.
  6. TemplateBenchmarkExtendedGCD: No description provided.
  7. TemplateBenchmarkGCD: No description provided.
  8. TemplateTestExtendedGCD: No description provided.
  9. TemplateTestGCD: No description provided.
generateparentheses
Functions:
  1. GenerateParenthesis: No description provided.
genetic
Package genetic provides functions to work with strings using genetic algorithm. https://en.wikipedia.org/wiki/Genetic_algorithm Author: D4rkia
Functions:
  1. GeneticString: GeneticString generates PopultaionItem based on the imputed target string, and a set of possible runes to build a string with. In order to optimise string generation additional configurations can be provided with Conf instance. Empty instance of Conf (&Conf{}) can be provided, then default values would be set. Link to the same algorithm implemented in python: https://github.com/TheAlgorithms/Python/blob/master/genetic_algorithm/basic_string.py
Types

  1. Conf: No description provided.

  2. PopulationItem: No description provided.

  3. Result: No description provided.

geometry
Functions:
  1. Distance: Calculates the shortest distance between two points.
  2. Intercept: Calculates the Y-Intercept of a line from a specific Point.
  3. IsParallel: Checks if two lines are parallel or not.
  4. IsPerpendicular: Checks if two lines are perpendicular or not.
  5. PointDistance: Calculates the distance of a given Point from a given line. The slice should contain the coefficiet of x, the coefficient of y and the constant in the respective order.
  6. Section: Calculates the Point that divides a line in specific ratio. DO NOT specify the ratio in the form m:n, specify it as r, where r = m / n.
  7. Slope: Calculates the slope (gradient) of a line.
Types

  1. Line: No description provided.

  2. Point: No description provided.

graph
Package graph demonstrates Graph search algorithms reference: https://en.wikipedia.org/wiki/Tree_traversal
Functions:
  1. BreadthFirstSearch: BreadthFirstSearch is an algorithm for traversing and searching graph data structures. It starts at an arbitrary node of a graph, and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level. Worst-case performance O(|V|+|E|)=O(b^{d})}O(|V|+|E|)=O(b^{d}) Worst-case space complexity O(|V|)=O(b^{d})}O(|V|)=O(b^{d}) reference: https://en.wikipedia.org/wiki/Breadth-first_search
  2. DepthFirstSearch: No description provided.
  3. DepthFirstSearchHelper: No description provided.
  4. FloydWarshall: FloydWarshall Returns all pair's shortest path using Floyd Warshall algorithm
  5. GetIdx: No description provided.
  6. KruskalMST: KruskalMST will return a minimum spanning tree along with its total cost to using Kruskal's algorithm. Time complexity is O(m * log (n)) where m is the number of edges in the graph and n is number of nodes in it.
  7. New: Constructor functions for graphs (undirected by default)
  8. NewDSU: NewDSU will return an initialised DSU using the value of n which will be treated as the number of elements out of which the DSU is being made
  9. NotExist: No description provided.
  10. Topological: Assumes that graph given is valid and possible to get a topo ordering. constraints are array of []int{a, b}, representing an edge going from a to b
Types

  1. DisjointSetUnion: No description provided.

  2. DisjointSetUnionElement: No description provided.

  3. Edge: No description provided.

  4. Graph: No description provided.

  5. Item: No description provided.

  6. WeightedGraph: No description provided.

hashmap
Functions:
  1. Make: Make creates a new HashMap instance with input size and capacity
  2. New: New return new HashMap instance
Types
  1. HashMap: No description provided.
kmp
Functions:
  1. Kmp: Kmp Function kmp performing the Knuth-Morris-Pratt algorithm. Prints whether the word/pattern was found and on what position in the text or not. m - current match in text, i - current character in w, c - amount of comparisons.
Types
  1. Result: No description provided.
lcm
Functions:
  1. Lcm: Lcm returns the lcm of two numbers using the fact that lcm(a,b) * gcd(a,b) = | a * b |
levenshtein
Functions:
  1. Distance: Distance Function that gives Levenshtein Distance
linkedlist
Package linkedlist demonstates different implementations on linkedlists.
Functions:
  1. JosephusProblem: https://en.wikipedia.org/wiki/Josephus_problem This is a struct-based solution for Josephus problem.
  2. NewCyclic: Create new list.
  3. NewDoubly: No description provided.
  4. NewNode: Create new node.
  5. NewSingly: NewSingly returns a new instance of a linked list
Types

  1. Cyclic: No description provided.

  2. Doubly: No description provided.

  3. Node: No description provided.

  4. Singly: No description provided.

  5. testCase: No description provided.

manacher
Functions:
  1. LongestPalindrome: No description provided.
math
Package math is a package that contains mathematical algorithms and its different implementations.
Functions:
  1. IsPowOfTwoUseLog: IsPowOfTwoUseLog This function checks if a number is a power of two using the logarithm. The limiting degree can be from 0 to 63. See alternatives in the binary package.
  2. Phi: Phi is the Euler totient function. This function computes the number of numbers less then n that are coprime with n.
max
Functions:
  1. BitwiseMax: No description provided.
  2. Int: Int is a function which returns the maximum of all the integers provided as arguments.
maxsubarraysum
Package maxsubarraysum is a package containing a solution to a common problem of finding max contiguous sum within a array of ints.
Functions:
  1. MaxSubarraySum: MaxSubarraySum returns the maximum subarray sum
min
Functions:
  1. Bitwise: No description provided.
  2. Int: Int is a function which returns the minimum of all the integers provided as arguments.
modular
Functions:
  1. Exponentiation: Exponentiation returns base^exponent % mod
  2. Inverse: Inverse Modular function
  3. Multiply64BitInt: Multiply64BitInt Checking if the integer multiplication overflows
moserdebruijnsequence
Functions:
  1. MoserDeBruijnSequence: No description provided.
nested
Package nested provides functions for testing strings proper brackets nesting.
Functions:
  1. IsBalanced: IsBalanced returns true if provided input string is properly nested. Input is a sequence of brackets: '(', ')', '[', ']', '{', '}'. A sequence of brackets s is considered properly nested if any of the following conditions are true: - s is empty; - s has the form (U) or [U] or {U} where U is a properly nested string; - s has the form VW where V and W are properly nested strings. For example, the string "()()[()]" is properly nested but "[(()]" is not. Note Providing characters other then brackets would return false, despite brackets sequence in the string. Make sure to filter input before usage.
palindrome
Functions:
  1. IsPalindrome: No description provided.
pangram
Functions:
  1. IsPangram: No description provided.
pascal
Functions:
  1. GenerateTriangle: GenerateTriangle This function generates a Pascal's triangle of n lines
password
Package password contains functions to help generate random passwords
Functions:
  1. Generate: Generate returns a newly generated password
permutation
Functions:
  1. GenerateElementSet: No description provided.
  2. Heaps: Heap's Algorithm for generating all permutations of n objects
pi
spigotpi_test.go description: Test for Spigot Algorithm for the Digits of Pi author(s) red_byte see spigotpi.go
Functions:
  1. MonteCarloPi: No description provided.
  2. Spigot: No description provided.
polybius
Package polybius is encrypting method with polybius square ref: https://en.wikipedia.org/wiki/Polybius_square#Hybrid_Polybius_Playfair_Cipher
Functions:
  1. NewPolybius: NewPolybius returns a pointer to object of Polybius. If the size of "chars" is longer than "size", "chars" are truncated to "size".
Types
  1. Polybius: No description provided.
power
Functions:
  1. IterativePower: IterativePower is iterative O(logn) function for pow(x, y)
  2. RecursivePower: RecursivePower is recursive O(logn) function for pow(x, y)
  3. RecursivePower1: RecursivePower1 is recursive O(n) function for pow(x, y)
  4. UsingLog: No description provided.
prime
Functions:
  1. Factorize: Factorize is a function that computes the exponents of each prime in the prime factorization of n
  2. Generate: Generate returns a int slice of prime numbers up to the limit
  3. GenerateChannel: Generate generates the sequence of integers starting at 2 and sends it to the channel ch
  4. MillerRabinTest: MillerRabinTest Probabilistic test for primality of an integer based of the algorithm devised by Miller and Rabin.
  5. MillerTest: MillerTest This is the intermediate step that repeats within the miller rabin primality test for better probabilitic chances of receiving the correct result.
  6. NaiveApproach: NaiveApproach checks if an integer is prime or not. Returns a bool.
  7. PairApproach: PairApproach checks primality of an integer and returns a bool. More efficient than the naive approach as number of iterations are less.
  8. Sieve: Sieve Sieving the numbers that are not prime from the channel - basically removing them from the channels
pythagoras
Functions:
  1. Distance: Distance calculates the distance between to vectors with the Pythagoras theorem
Types
  1. Vector: No description provided.
queue
Functions:
  1. BackQueue: BackQueue return the Back value
  2. DeQueue: DeQueue it will be removed the first value that added into the list
  3. EnQueue: EnQueue it will be added new value into our list
  4. FrontQueue: FrontQueue return the Front value
  5. IsEmptyQueue: IsEmptyQueue check our list is empty or not
  6. LenQueue: LenQueue will return the length of the queue list
Types

  1. LQueue: No description provided.

  2. Node: No description provided.

  3. Queue: No description provided.

rsa
Package rsa shows a simple implementation of RSA algorithm
Functions:
  1. Decrypt: Decrypt decrypts encrypted rune slice based on the RSA algorithm
  2. Encrypt: Encrypt encrypts based on the RSA algorithm - uses modular exponentitation in math directory
search
Functions:
  1. BoyerMoore: Implementation of boyer moore string search O(l) where l=len(text)
  2. Naive: Implementation of naive string search O(n*m) where n=len(txt) and m=len(pattern)
segmenttree
Functions:
  1. NewSegmentTree: No description provided.
Types
  1. SegmentTree: No description provided.
set
package set implements a Set using a golang map. This implies that only the types that are accepted as valid map keys can be used as set elements. For instance, do not try to Add a slice, or the program will panic.
Functions:
  1. New: New gives new set.
sort
Package sort a package for demonstrating sorting algorithms in Go
Functions:
  1. Comb: No description provided.
  2. Count: No description provided.
  3. Exchange: No description provided.
  4. HeapSort: No description provided.
  5. ImprovedSimpleSort: ImprovedSimpleSort is a improve SimpleSort by skipping an unnecessary comparison of the first and last. This improved version is more similar to implementation of insertion sort
  6. InsertionSort: No description provided.
  7. Mergesort: Mergesort Perform mergesort on a slice of ints
  8. Pigeonhole: Pigeonhole sorts a slice using pigeonhole sorting algorithm.
  9. QuickSort: QuickSort Sorts the entire array
  10. QuickSortRange: QuickSortRange Sorts the specified range within the array
  11. RadixSort: No description provided.
  12. SelectionSort: No description provided.
  13. ShellSort: No description provided.
  14. SimpleSort: No description provided.
Types

  1. Int:

    Methods:

    1. More: No description provided.

  2. MaxHeap: No description provided.

stack
Types

  1. Node: No description provided.

  2. SList: No description provided.

  3. Stack: No description provided.

transposition
Functions:
  1. Decrypt: No description provided.
  2. Encrypt: No description provided.
Types

  1. KeyMissingError: No description provided.

  2. NoTextToEncryptError: No description provided.

trie
Package trie provides Trie data structures in golang. Wikipedia: https://en.wikipedia.org/wiki/Trie
Functions:
  1. NewNode: NewNode creates a new Trie node with initialized children map.
Types
  1. Node: No description provided.
xor
Package xor is an encryption algorithm that operates the exclusive disjunction(XOR) ref: https://en.wikipedia.org/wiki/XOR_cipher
Functions:
  1. Decrypt: Decrypt decrypts with Xor encryption
  2. Encrypt: Encrypt encrypts with Xor encryption after converting each character to byte The returned value might not be readable because there is no guarantee which is within the ASCII range If using other type such as string, []int, or some other types, add the statements for converting the type to []byte.