密码（Ciphers）、动态规划（Dynamic Programming）、图计算（Graphs）等golang版算法实现。涵盖了计算机科学、数学和统计、数据科学、机器学习、工程等领域的各种主题。
Akshay Dubey 6a99cd70c5 algorithm: Liouville lambda function (#540) | 4 days ago | |
---|---|---|
.github | 4 months ago | |
checksum | 5 months ago | |
cipher | 1 month ago | |
constraints | 6 months ago | |
conversion | 6 months ago | |
dynamic | 4 months ago | |
graph | 1 month ago | |
hashing | 10 months ago | |
math | 4 days ago | |
other | 4 weeks ago | |
search | 1 month ago | |
sort | 1 month ago | |
strings | 4 weeks ago | |
structure | 2 weeks ago | |
.gitignore | 1 year ago | |
.golangci.yml | 1 month ago | |
CONTRIBUTING.md | 2 months ago | |
LICENSE | 1 year ago | |
README.md | 1 week ago | |
go.mod | 1 month ago | |
go.sum | 1 month ago |
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.
<summary> <strong> ahocorasick </strong> </summary>
Advanced
: Advanced Function performing the Advanced Aho-Corasick algorithm. Finds and prints occurrences of each pattern.AhoCorasick
: AhoCorasick Function performing the Basic Aho-Corasick algorithm. Finds and prints occurrences of each pattern.ArrayUnion
: ArrayUnion Concats two arrays of int's into one.BoolArrayCapUp
: BoolArrayCapUp Dynamically increases an array size of bool's by 1.BuildAc
: Functions that builds Aho Corasick automaton.BuildExtendedAc
: BuildExtendedAc Functions that builds extended Aho Corasick automaton.ComputeAlphabet
: ComputeAlphabet Function that returns string of all the possible characters in given patterns.ConstructTrie
: ConstructTrie Function that constructs Trie as an automaton for a set of reversed & trimmed strings.Contains
: Contains Returns 'true' if array of int's 's' contains int 'e', 'false' otherwise.CreateNewState
: CreateNewState Automaton function for creating a new state 'state'.CreateTransition
: CreateTransition Creates a transition for function σ(state,letter) = end.GetParent
: GetParent Function that finds the first previous state of a state and returns it. Used for trie where there is only one parent.GetTransition
: GetTransition Returns ending state for transition σ(fromState,overChar), '-1' if there is none.GetWord
: GetWord Function that returns word found in text 't' at position range 'begin' to 'end'.IntArrayCapUp
: IntArrayCapUp Dynamically increases an array size of int's by 1.StateExists
: StateExists Checks if state 'state' exists. Returns 'true' if it does, 'false' otherwise.Result
: No description provided.<summary> <strong> armstrong </strong> </summary>
IsArmstrong
: No description provided.<summary> <strong> avl </strong> </summary>
Delete
: Delete : remove given key from the treeGet
: Get : return node with given keyInsert
: Insert a new itemNewTree
: NewTree create a new AVL treeNode
: No description provided.<summary> <strong> binary </strong> </summary>
Abs
: Abs returns absolute value using binary operation Principle of operation: 1) Get the mask by right shift by the base 2) Base is the size of an integer variable in bits, for example, for int32 it will be 32, for int64 it will be 64 3) For negative numbers, above step sets mask as 1 1 1 1 1 1 1 1 and 0 0 0 0 0 0 0 0 for positive numbers. 4) Add the mask to the given number. 5) XOR of mask + n and mask gives the absolute value.BitCounter
: BitCounter - The function returns the number of set bits for an unsigned integer numberIsPowerOfTwo
: 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.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 * 2LogBase2
: LogBase2 Finding the exponent of n = 2**x using bitwise operations (logarithm in base 2 of n) See moreMeanUsingAndXor
: MeanUsingAndXor This function finds arithmetic mean using "AND" and "XOR" operationsMeanUsingRightShift
: MeanUsingRightShift This function finds arithmetic mean using right shiftReverseBits
: 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.SequenceGrayCode
: SequenceGrayCode The function generates an "Gray code" sequence of length nSqrt
: No description provided.XorSearchMissingNumber
: XorSearchMissingNumber This function finds a missing number in a sequence<summary> <strong> binarytree </strong> </summary>
AccessNodesByLayer
: AccessNodesByLayer Function that access nodes layer by layer instead of printing the results as one line.BstDelete
: BstDelete removes the nodeInOrder
: Travers the tree in the following order left --> root --> rightInOrderSuccessor
: InOrderSuccessor Goes to the leftInsert
: Insert a value in the BSTreeLevelOrder
: No description provided.Max
: Max Function that returns max of two numbers - possibly already declared.NewNode
: NewNode Returns a new pointer to an empty NodePostOrder
: Travers the tree in the following order left --> right --> rootPreOrder
: Travers the tree in the following order root --> left --> right<summary> <strong> caesar </strong> </summary>
Decrypt
: Decrypt decrypts by left shift of "key" each character of "input"Encrypt
: Encrypt encrypts by right shift of "key" each character of "input"<summary> <strong> catalan </strong> </summary>
CatalanNumber
: CatalanNumber This function returns the nth
Catalan number<summary> <strong> checksum </strong> </summary>
CRC8
: CRC8 calculates CRC8 checksum of the given data.Luhn
: Luhn validates the provided data using the Luhn algorithm.CRCModel
: No description provided.<summary> <strong> coloring </strong> </summary>
BipartiteCheck
: basically tries to color the graph in two colors if each edge connects 2 differently colored nodes the graph can be considered bipartiteGraph
: No description provided.<summary> <strong> combination </strong> </summary>
Start
: Start ...Combinations
: No description provided.<summary> <strong> conversion </strong> </summary>
Base64Decode
: Base64Decode decodes the received input base64 string into a byte slice. The implementation follows the RFC4648 standard, which is documented at https://datatracker.ietf.org/doc/html/rfc4648#section-4Base64Encode
: Base64Encode encodes the received input bytes slice into a base64 string. The implementation follows the RFC4648 standard, which is documented at https://datatracker.ietf.org/doc/html/rfc4648#section-4BinaryToDecimal
: BinaryToDecimal() function that will take Binary number as string, and return it's Decimal equivalent as integer.DecimalToBinary
: DecimalToBinary() function that will take Decimal number as int, and return it's Binary equivalent as string.FuzzBase64Encode
: No description provided.HEXToRGB
: HEXToRGB splits an RGB input (e.g. a color in hex format; 0x) into the individual components: red, green and blue
IntToRoman
: IntToRoman converts an integer value to a roman numeral string. An error is returned if the integer is not between 1 and 3999.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. HexReverse
: Reverse() function that will take string, and returns the reverse of that string.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.<summary> <strong> diffiehellman </strong> </summary>
GenerateMutualKey
: GenerateMutualKey : generates a mutual key that can be used by only alice and bob mutualKey = (shareKey^prvKey)%primeNumberGenerateShareKey
: GenerateShareKey : generates a key using client private key , generator and primeNumber this key can be made public shareKey = (g^key)%primeNumber<summary> <strong> dynamic </strong> </summary>
Abbreviation
: Returns true if it is possible to make a equals b (if b is an abbreviation of a), returns false otherwiseBin2
: Bin2 functionCoinChange
: CoinChange finds the number of possible combinations of coins of different values which can get to the target amount.CutRodDp
: CutRodDp solve the same problem using dynamic programmingCutRodRec
: CutRodRec solve the problem recursively: initial approachEditDistanceDP
: 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.EditDistanceRecursive
: EditDistanceRecursive is a naive implementation with exponential time complexity.IsSubsetSum
: No description provided.Knapsack
: Knapsack solves knapsack problem return maxProfitLongestCommonSubsequence
: LongestCommonSubsequence functionLongestIncreasingSubsequence
: LongestIncreasingSubsequence returns the longest increasing subsequence where all elements of the subsequence are sorted in increasing orderLongestIncreasingSubsequenceGreedy
: LongestIncreasingSubsequenceGreedy is a function to find the longest increasing subsequence in a given array using a greedy approach. The dynamic programming approach is implemented alongside this one. Worst Case Time Complexity: O(nlogn) Auxiliary Space: O(n), where n is the length of the array(slice). Reference: https://www.geeksforgeeks.org/construction-of-longest-monotonically-increasing-subsequence-n-log-n/LpsDp
: LpsDp functionLpsRec
: LpsRec functionMatrixChainDp
: MatrixChainDp functionMatrixChainRec
: MatrixChainRec functionMax
: Max function - possible duplicateNthCatalanNumber
: NthCatalan returns the n-th Catalan Number Complexity: O(n²)NthFibonacci
: NthFibonacci returns the nth Fibonacci Number<summary> <strong> dynamicarray </strong> </summary>
DynamicArray
: No description provided.<summary> <strong> factorial </strong> </summary>
Iterative
: Iterative returns the iteratively brute forced factorial of nRecursive
: Recursive This function recursively computes the factorial of a numberUsingTree
: UsingTree This function finds the factorial of a number using a binary tree<summary> <strong> fibonacci </strong> </summary>
Formula
: Formula This function calculates the n-th fibonacci number using the formula Attention! Tests for large values fall due to rounding error of floating point numbers, works well, only on small numbersMatrix
: Matrix This function calculates the n-th fibonacci number using the matrix method. See<summary> <strong> gcd </strong> </summary>
Extended
: Extended simple extended gcdExtendedIterative
: ExtendedIterative finds and returns gcd(a, b), x, y satisfying a*x + b*y = gcd(a, b).ExtendedRecursive
: ExtendedRecursive finds and returns gcd(a, b), x, y satisfying a*x + b*y = gcd(a, b).Iterative
: Iterative Faster iterative version of GcdRecursive without holding up too much of the stackRecursive
: Recursive finds and returns the greatest common divisor of a given integer.TemplateBenchmarkExtendedGCD
: No description provided.TemplateBenchmarkGCD
: No description provided.TemplateTestExtendedGCD
: No description provided.TemplateTestGCD
: No description provided.<summary> <strong> generateparentheses </strong> </summary>
GenerateParenthesis
: No description provided.<summary> <strong> genetic </strong> </summary>
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.pyConf
: No description provided.
PopulationItem
: No description provided.
Result
: No description provided.
<summary> <strong> geometry </strong> </summary>
Distance
: Distance calculates the shortest distance between two points.IsParallel
: IsParallel checks if two lines are parallel or not.IsPerpendicular
: IsPerpendicular checks if two lines are perpendicular or not.PointDistance
: 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.Section
: 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.Slope
: Slope calculates the slope (gradient) of a line.YIntercept
: YIntercept calculates the Y-Intercept of a line from a specific Point.<summary> <strong> graph </strong> </summary>
ArticulationPoint
: ArticulationPoint is a function to identify articulation points in a graph. The function takes the graph as an argument and returns a boolean slice which indicates whether a vertex is an articulation point or not. Worst Case Time Complexity: O(|V| + |E|) Auxiliary Space: O(|V|) reference: https://en.wikipedia.org/wiki/Biconnected_component and https://cptalks.quora.com/Cut-Vertex-Articulation-pointBreadthFirstSearch
: 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_searchDepthFirstSearch
: No description provided.DepthFirstSearchHelper
: No description provided.FloydWarshall
: FloydWarshall Returns all pair's shortest path using Floyd Warshall algorithmGetIdx
: No description provided.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.LowestCommonAncestor
: For each node, we will precompute its ancestor above him, its ancestor two nodes above, its ancestor four nodes above, etc. Let's call jump[j][u]
is the 2^j
-th ancestor above the node u
with u
in range [0, numbersVertex)
, j
in range [0,MAXLOG)
. These information allow us to jump from any node to any ancestor above it in O(MAXLOG)
time.New
: Constructor functions for graphs (undirected by default)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 madeNewTree
: No description provided.NotExist
: No description provided.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 bDisjointSetUnion
: No description provided.
DisjointSetUnionElement
: No description provided.
Edge
: No description provided.
Graph
: No description provided.
Item
: No description provided.
Query
: No description provided.
Tree
: No description provided.
TreeEdge
: No description provided.
WeightedGraph
: No description provided.
<summary> <strong> hashmap </strong> </summary>
Make
: Make creates a new HashMap instance with input size and capacityNew
: New return new HashMap instanceHashMap
: No description provided.<summary> <strong> kmp </strong> </summary>
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.Result
: No description provided.<summary> <strong> lcm </strong> </summary>
Lcm
: Lcm returns the lcm of two numbers using the fact that lcm(a,b) * gcd(a,b) = | a * b |<summary> <strong> levenshtein </strong> </summary>
Distance
: Distance Function that gives Levenshtein Distance<summary> <strong> linkedlist </strong> </summary>
JosephusProblem
: https://en.wikipedia.org/wiki/Josephus_problem This is a struct-based solution for Josephus problem.NewCyclic
: Create new list.NewDoubly
: No description provided.NewNode
: Create new node.NewSingly
: NewSingly returns a new instance of a linked listCyclic
: No description provided.
Doubly
: No description provided.
Node
: No description provided.
Singly
: No description provided.
testCase
: No description provided.
<summary> <strong> manacher </strong> </summary>
LongestPalindrome
: No description provided.<summary> <strong> math </strong> </summary>
Abs
: Abs returns absolute valueCos
: Cos returns the cosine of the radian argument x. See more Based on the idea of Bhaskara approximation of cos(x)FindKthMax
: FindKthMax returns the kth large element given an integer slice with nil error
if found and returns -1 with error
search.ErrNotFound
if not found. NOTE: The nums
slice gets mutated in the process.FindKthMin
: FindKthMin returns kth small element given an integer slice with nil error
if found and returns -1 with error
search.ErrNotFound
if not found. NOTE: The nums
slice gets mutated in the process.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.Mean
: No description provided.Median
: No description provided.Mode
: No description provided.Phi
: Phi is the Euler totient function. This function computes the number of numbers less then n that are coprime with n.Sin
: Sin returns the sine of the radian argument x. See more<summary> <strong> max </strong> </summary>
Bitwise
: Bitwise computes using bitwise operator the maximum of all the integer input and returns itInt
: Int is a function which returns the maximum of all the integers provided as arguments.<summary> <strong> maxsubarraysum </strong> </summary>
MaxSubarraySum
: MaxSubarraySum returns the maximum subarray sum<summary> <strong> min </strong> </summary>
Bitwise
: Bitwise This function returns the minimum integer using bit operationsInt
: Int is a function which returns the minimum of all the integers provided as arguments.<summary> <strong> modular </strong> </summary>
Exponentiation
: Exponentiation returns base^exponent % modInverse
: Inverse Modular functionMultiply64BitInt
: Multiply64BitInt Checking if the integer multiplication overflows<summary> <strong> moserdebruijnsequence </strong> </summary>
MoserDeBruijnSequence
: No description provided.<summary> <strong> nested </strong> </summary>
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.<summary> <strong> palindrome </strong> </summary>
IsPalindrome
: No description provided.IsPalindromeRecursive
: No description provided.<summary> <strong> pangram </strong> </summary>
IsPangram
: No description provided.<summary> <strong> parenthesis </strong> </summary>
Parenthesis
: parcounter will be 0 if all open parenthesis are closed correctly<summary> <strong> pascal </strong> </summary>
GenerateTriangle
: GenerateTriangle This function generates a Pascal's triangle of n lines<summary> <strong> password </strong> </summary>
Generate
: Generate returns a newly generated password<summary> <strong> permutation </strong> </summary>
GenerateElementSet
: No description provided.Heaps
: Heap's Algorithm for generating all permutations of n objects<summary> <strong> pi </strong> </summary>
MonteCarloPi
: No description provided.MonteCarloPiConcurrent
: MonteCarloPiConcurrent approximates the value of pi using the Monte Carlo method. Unlike the MonteCarloPi function (first version), this implementation uses goroutines and channels to parallelize the computation. More details on the Monte Carlo method available at https://en.wikipedia.org/wiki/Monte_Carlo_method. More details on goroutines parallelization available at https://go.dev/doc/effective_go#parallel.Spigot
: No description provided.<summary> <strong> polybius </strong> </summary>
NewPolybius
: NewPolybius returns a pointer to object of Polybius. If the size of "chars" is longer than "size", "chars" are truncated to "size".Polybius
: No description provided.<summary> <strong> power </strong> </summary>
IterativePower
: IterativePower is iterative O(logn) function for pow(x, y)RecursivePower
: RecursivePower is recursive O(logn) function for pow(x, y)RecursivePower1
: RecursivePower1 is recursive O(n) function for pow(x, y)UsingLog
: No description provided.<summary> <strong> prime </strong> </summary>
Factorize
: Factorize is a function that computes the exponents of each prime in the prime factorization of nGenerate
: Generate returns a int slice of prime numbers up to the limitGenerateChannel
: Generate generates the sequence of integers starting at 2 and sends it to the channel ch
MillerRabinDeterministic
: MillerRabinDeterministic is a Deterministic version of the Miller-Rabin test, which returns correct results for all valid int64 numbers.MillerRabinProbabilistic
: MillerRabinProbabilistic is a probabilistic test for primality of an integer based of the algorithm devised by Miller and Rabin.MillerRandomTest
: MillerRandomTest This is the intermediate step that repeats within the miller rabin primality test for better probabilitic chances of receiving the correct result with random witnesses.MillerTest
: MillerTest tests whether num is a strong probable prime to a witness. Formally: a^d ≡ 1 (mod n) or a^(2^r * d) ≡ -1 (mod n), 0 <= r <= sMillerTestMultiple
: MillerTestMultiple is like MillerTest but runs the test for multiple witnesses.OptimizedTrialDivision
: OptimizedTrialDivision checks primality of an integer using an optimized trial division method. The optimizations include not checking divisibility by the even numbers and only checking up to the square root of the given number.Sieve
: Sieve Sieving the numbers that are not prime from the channel - basically removing them from the channelsTrialDivision
: TrialDivision tests whether a number is prime by trying to divide it by the numbers less than it.<summary> <strong> pythagoras </strong> </summary>
Distance
: Distance calculates the distance between to vectors with the Pythagoras theoremVector
: No description provided.<summary> <strong> queue </strong> </summary>
BackQueue
: BackQueue return the Back valueDeQueue
: DeQueue it will be removed the first value that added into the listEnQueue
: EnQueue it will be added new value into our listFrontQueue
: FrontQueue return the Front valueIsEmptyQueue
: IsEmptyQueue check our list is empty or notLenQueue
: LenQueue will return the length of the queue list<summary> <strong> rsa </strong> </summary>
Decrypt
: Decrypt decrypts encrypted rune slice based on the RSA algorithmEncrypt
: Encrypt encrypts based on the RSA algorithm - uses modular exponentitation in math directory<summary> <strong> search </strong> </summary>
BoyerMoore
: Implementation of boyer moore string search O(l) where l=len(text)Naive
: Implementation of naive string search O(n*m) where n=len(txt) and m=len(pattern)<summary> <strong> segmenttree </strong> </summary>
NewSegmentTree
: No description provided.SegmentTree
: No description provided.<summary> <strong> set </strong> </summary>
New
: New gives new set.<summary> <strong> sha256 </strong> </summary>
Hash
: Hash hashes the input message using the sha256 hashing function, and return a 32 byte array. The implementation follows the RGC6234 standard, which is documented at https://datatracker.ietf.org/doc/html/rfc6234<summary> <strong> sort </strong> </summary>
Bubble
: Bubble is a simple generic definition of Bubble sort algorithm.Comb
: Comb is a simple sorting algorithm which is an improvement of the bubble sorting algorithm.Count
: No description provided.Exchange
: No description provided.HeapSort
: No description provided.ImprovedSimple
: ImprovedSimple is a improve SimpleSort by skipping an unnecessary comparison of the first and last. This improved version is more similar to implementation of insertion sortInsertion
: No description provided.Merge
: Merge Perform merge sort on a sliceMergeIter
: No description provided.Partition
: No description provided.Patience
: No description provided.Pigeonhole
: Pigeonhole sorts a slice using pigeonhole sorting algorithm.Quicksort
: Quicksort Sorts the entire arrayQuicksortRange
: QuicksortRange Sorts the specified range within the arrayRadixSort
: No description provided.Selection
: No description provided.Shell
: No description provided.Simple
: No description provided.<summary> <strong> stack </strong> </summary>
<summary> <strong> strings </strong> </summary>
CountChars
: CountChars counts the number of a times a character has occurred in the provided string argument and returns a map with rune
as keys and the count as value.<summary> <strong> transposition </strong> </summary>
KeyMissingError
: No description provided.
NoTextToEncryptError
: No description provided.
<summary> <strong> trie </strong> </summary>
NewNode
: NewNode creates a new Trie node with initialized children map.Node
: No description provided.<summary> <strong> xor </strong> </summary>
Decrypt
: Decrypt decrypts with Xor encryptionEncrypt
: 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.