trekhleb / javascript-algorithms Goto Github PK
View Code? Open in Web Editor NEWπ Algorithms and data structures implemented in JavaScript with explanations and links to further readings
License: MIT License
π Algorithms and data structures implemented in JavaScript with explanations and links to further readings
License: MIT License
It should be mentioned that QuickSortInPlace
is the actual quick sort. Other implementation that allows using extra space is like quick sort but not the strictly the actual algorithm.
I've seen this at several places. For example the following implementation of quicksort in Haskell
quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) =
let smallerSorted = quicksort [a | a <- xs, a <= x]
biggerSorted = quicksort [a | a <- xs, a > x]
in smallerSorted ++ [x] ++ biggerSorted
It is shown as a quicksort implementation but in reality it is not.
A lot of newbies will get a wrong idea about the quicksort this way who are only learning algos this way.
It should at least be mentioned in the ReadMe that the one with the in-place is the real one.
Hey, I apologize in advance if this is misplaced. I don't have any maths education or know anything of algorithms.
I've been working on something that I believe I misconstrued from a problem I saw asked that dealt with binary trees. I don't know if this is a valid algorithm or not:
// Find all subtrees of n-ary tree. For example:
//
// 1
// / \
// / \
// 2 3
// / \ /|\
// 4 6 5 7 8
// / \
// 9 10
// I want to show all subtrees:
// 1 1 1 1 1 1 1
// / \ / \ / \ / \ \
// 2 3 2 3 2 3 2 3 3
// | | / /
// 4 4 5 5
I think essentially what I'm trying to communicate here is any valid branching path/"state" from the tree starting at the root node. I first tried order-specific (all permutations of each "level" were valid) but this was far too difficult and I've since retreated to trying to figure out order-inspecific. I could be way off, but this appears to work:
https://repl.it/@GavinRay97/VivaciousWarmheartedComputers-1
var exampleTree = {
a: {
b: {
d: null,
e: {
f: null,
g: {
i: {
l: null,
m: null,
n: null,
},
k: null,
},
h: null
}
},
c: null,
o: null
},
}
"a -> b"
"a -> b-c"
"a -> b-c -> d"
"a -> b-c -> d-e"
"a -> b-c -> d-e -> f"
"a -> b-c -> d-e -> f-g"
"a -> b-c -> d-e -> f-g-h"
"a -> b-c -> d-e -> f-g-h -> i"
"a -> b-c -> d-e -> f-g-h -> i-k"
"a -> b-c -> d-e -> f-g-h -> i-k -> l"
"a -> b-c -> d-e -> f-g-h -> i-k -> l-m"
"a -> b-c -> d-e -> f-g-h -> i-k -> l-m-n"
"a -> b-c -> d-e -> f-g-h -> i-k -> m"
"a -> b-c -> d-e -> f-g-h -> i-k -> m-n"
"a -> b-c -> d-e -> f-g-h -> i-k -> n"
"a -> b-c -> d-e -> f-g-h -> i -> l"
"a -> b-c -> d-e -> f-g-h -> i -> l-m"
"a -> b-c -> d-e -> f-g-h -> i -> l-m-n"
"a -> b-c -> d-e -> f-g-h -> i -> m"
"a -> b-c -> d-e -> f-g-h -> i -> m-n"
"a -> b-c -> d-e -> f-g-h -> i -> n"
"a -> b-c -> d-e -> f-g-h -> k"
"a -> b-c -> d-e -> f-g -> i"
"a -> b-c -> d-e -> f-g -> i-k"
"a -> b-c -> d-e -> f-g -> i-k -> l"
"a -> b-c -> d-e -> f-g -> i-k -> l-m"
"a -> b-c -> d-e -> f-g -> i-k -> l-m-n"
"a -> b-c -> d-e -> f-g -> i-k -> m"
"a -> b-c -> d-e -> f-g -> i-k -> m-n"
"a -> b-c -> d-e -> f-g -> i-k -> n"
"a -> b-c -> d-e -> f-g -> i -> l"
"a -> b-c -> d-e -> f-g -> i -> l-m"
"a -> b-c -> d-e -> f-g -> i -> l-m-n"
"a -> b-c -> d-e -> f-g -> i -> m"
"a -> b-c -> d-e -> f-g -> i -> m-n"
"a -> b-c -> d-e -> f-g -> i -> n"
"a -> b-c -> d-e -> f-g -> k"
"a -> b-c -> d-e -> g"
"a -> b-c -> d-e -> g-h"
"a -> b-c -> d-e -> g-h -> i"
"a -> b-c -> d-e -> g-h -> i-k"
"a -> b-c -> d-e -> g-h -> i-k -> l"
"a -> b-c -> d-e -> g-h -> i-k -> l-m"
"a -> b-c -> d-e -> g-h -> i-k -> l-m-n"
"a -> b-c -> d-e -> g-h -> i-k -> m"
"a -> b-c -> d-e -> g-h -> i-k -> m-n"
"a -> b-c -> d-e -> g-h -> i-k -> n"
"a -> b-c -> d-e -> g-h -> i -> l"
"a -> b-c -> d-e -> g-h -> i -> l-m"
"a -> b-c -> d-e -> g-h -> i -> l-m-n"
"a -> b-c -> d-e -> g-h -> i -> m"
"a -> b-c -> d-e -> g-h -> i -> m-n"
"a -> b-c -> d-e -> g-h -> i -> n"
"a -> b-c -> d-e -> g-h -> k"
"a -> b-c -> d-e -> g -> i"
"a -> b-c -> d-e -> g -> i-k"
"a -> b-c -> d-e -> g -> i-k -> l"
"a -> b-c -> d-e -> g -> i-k -> l-m"
"a -> b-c -> d-e -> g -> i-k -> l-m-n"
"a -> b-c -> d-e -> g -> i-k -> m"
"a -> b-c -> d-e -> g -> i-k -> m-n"
"a -> b-c -> d-e -> g -> i-k -> n"
"a -> b-c -> d-e -> g -> i -> l"
"a -> b-c -> d-e -> g -> i -> l-m"
"a -> b-c -> d-e -> g -> i -> l-m-n"
"a -> b-c -> d-e -> g -> i -> m"
"a -> b-c -> d-e -> g -> i -> m-n"
"a -> b-c -> d-e -> g -> i -> n"
"a -> b-c -> d-e -> g -> k"
"a -> b-c -> d-e -> h"
"a -> b-c -> e"
"a -> b-c -> e -> f"
"a -> b-c -> e -> f-g"
"a -> b-c -> e -> f-g-h"
"a -> b-c -> e -> f-g-h -> i"
"a -> b-c -> e -> f-g-h -> i-k"
"a -> b-c -> e -> f-g-h -> i-k -> l"
"a -> b-c -> e -> f-g-h -> i-k -> l-m"
"a -> b-c -> e -> f-g-h -> i-k -> l-m-n"
"a -> b-c -> e -> f-g-h -> i-k -> m"
"a -> b-c -> e -> f-g-h -> i-k -> m-n"
"a -> b-c -> e -> f-g-h -> i-k -> n"
"a -> b-c -> e -> f-g-h -> i -> l"
"a -> b-c -> e -> f-g-h -> i -> l-m"
"a -> b-c -> e -> f-g-h -> i -> l-m-n"
"a -> b-c -> e -> f-g-h -> i -> m"
"a -> b-c -> e -> f-g-h -> i -> m-n"
"a -> b-c -> e -> f-g-h -> i -> n"
"a -> b-c -> e -> f-g-h -> k"
"a -> b-c -> e -> f-g -> i"
"a -> b-c -> e -> f-g -> i-k"
"a -> b-c -> e -> f-g -> i-k -> l"
"a -> b-c -> e -> f-g -> i-k -> l-m"
"a -> b-c -> e -> f-g -> i-k -> l-m-n"
"a -> b-c -> e -> f-g -> i-k -> m"
"a -> b-c -> e -> f-g -> i-k -> m-n"
"a -> b-c -> e -> f-g -> i-k -> n"
"a -> b-c -> e -> f-g -> i -> l"
"a -> b-c -> e -> f-g -> i -> l-m"
"a -> b-c -> e -> f-g -> i -> l-m-n"
"a -> b-c -> e -> f-g -> i -> m"
"a -> b-c -> e -> f-g -> i -> m-n"
"a -> b-c -> e -> f-g -> i -> n"
"a -> b-c -> e -> f-g -> k"
"a -> b-c -> e -> g"
"a -> b-c -> e -> g-h"
"a -> b-c -> e -> g-h -> i"
"a -> b-c -> e -> g-h -> i-k"
"a -> b-c -> e -> g-h -> i-k -> l"
"a -> b-c -> e -> g-h -> i-k -> l-m"
"a -> b-c -> e -> g-h -> i-k -> l-m-n"
"a -> b-c -> e -> g-h -> i-k -> m"
"a -> b-c -> e -> g-h -> i-k -> m-n"
"a -> b-c -> e -> g-h -> i-k -> n"
"a -> b-c -> e -> g-h -> i -> l"
"a -> b-c -> e -> g-h -> i -> l-m"
"a -> b-c -> e -> g-h -> i -> l-m-n"
"a -> b-c -> e -> g-h -> i -> m"
"a -> b-c -> e -> g-h -> i -> m-n"
"a -> b-c -> e -> g-h -> i -> n"
"a -> b-c -> e -> g-h -> k"
"a -> b-c -> e -> g -> i"
"a -> b-c -> e -> g -> i-k"
"a -> b-c -> e -> g -> i-k -> l"
"a -> b-c -> e -> g -> i-k -> l-m"
"a -> b-c -> e -> g -> i-k -> l-m-n"
"a -> b-c -> e -> g -> i-k -> m"
"a -> b-c -> e -> g -> i-k -> m-n"
"a -> b-c -> e -> g -> i-k -> n"
"a -> b-c -> e -> g -> i -> l"
"a -> b-c -> e -> g -> i -> l-m"
"a -> b-c -> e -> g -> i -> l-m-n"
"a -> b-c -> e -> g -> i -> m"
"a -> b-c -> e -> g -> i -> m-n"
"a -> b-c -> e -> g -> i -> n"
"a -> b-c -> e -> g -> k"
"a -> b-c -> e -> h"
"a -> b-c-o"
"a -> b-c-o -> d"
"a -> b-c-o -> d-e"
"a -> b-c-o -> d-e -> f"
"a -> b-c-o -> d-e -> f-g"
"a -> b-c-o -> d-e -> f-g-h"
"a -> b-c-o -> d-e -> f-g-h -> i"
"a -> b-c-o -> d-e -> f-g-h -> i-k"
"a -> b-c-o -> d-e -> f-g-h -> i-k -> l"
"a -> b-c-o -> d-e -> f-g-h -> i-k -> l-m"
"a -> b-c-o -> d-e -> f-g-h -> i-k -> l-m-n"
"a -> b-c-o -> d-e -> f-g-h -> i-k -> m"
"a -> b-c-o -> d-e -> f-g-h -> i-k -> m-n"
"a -> b-c-o -> d-e -> f-g-h -> i-k -> n"
"a -> b-c-o -> d-e -> f-g-h -> i -> l"
"a -> b-c-o -> d-e -> f-g-h -> i -> l-m"
"a -> b-c-o -> d-e -> f-g-h -> i -> l-m-n"
"a -> b-c-o -> d-e -> f-g-h -> i -> m"
"a -> b-c-o -> d-e -> f-g-h -> i -> m-n"
"a -> b-c-o -> d-e -> f-g-h -> i -> n"
"a -> b-c-o -> d-e -> f-g-h -> k"
"a -> b-c-o -> d-e -> f-g -> i"
"a -> b-c-o -> d-e -> f-g -> i-k"
"a -> b-c-o -> d-e -> f-g -> i-k -> l"
"a -> b-c-o -> d-e -> f-g -> i-k -> l-m"
"a -> b-c-o -> d-e -> f-g -> i-k -> l-m-n"
"a -> b-c-o -> d-e -> f-g -> i-k -> m"
"a -> b-c-o -> d-e -> f-g -> i-k -> m-n"
"a -> b-c-o -> d-e -> f-g -> i-k -> n"
"a -> b-c-o -> d-e -> f-g -> i -> l"
"a -> b-c-o -> d-e -> f-g -> i -> l-m"
"a -> b-c-o -> d-e -> f-g -> i -> l-m-n"
"a -> b-c-o -> d-e -> f-g -> i -> m"
"a -> b-c-o -> d-e -> f-g -> i -> m-n"
"a -> b-c-o -> d-e -> f-g -> i -> n"
"a -> b-c-o -> d-e -> f-g -> k"
"a -> b-c-o -> d-e -> g"
"a -> b-c-o -> d-e -> g-h"
"a -> b-c-o -> d-e -> g-h -> i"
"a -> b-c-o -> d-e -> g-h -> i-k"
"a -> b-c-o -> d-e -> g-h -> i-k -> l"
"a -> b-c-o -> d-e -> g-h -> i-k -> l-m"
"a -> b-c-o -> d-e -> g-h -> i-k -> l-m-n"
"a -> b-c-o -> d-e -> g-h -> i-k -> m"
"a -> b-c-o -> d-e -> g-h -> i-k -> m-n"
"a -> b-c-o -> d-e -> g-h -> i-k -> n"
"a -> b-c-o -> d-e -> g-h -> i -> l"
"a -> b-c-o -> d-e -> g-h -> i -> l-m"
"a -> b-c-o -> d-e -> g-h -> i -> l-m-n"
"a -> b-c-o -> d-e -> g-h -> i -> m"
"a -> b-c-o -> d-e -> g-h -> i -> m-n"
"a -> b-c-o -> d-e -> g-h -> i -> n"
"a -> b-c-o -> d-e -> g-h -> k"
"a -> b-c-o -> d-e -> g -> i"
"a -> b-c-o -> d-e -> g -> i-k"
"a -> b-c-o -> d-e -> g -> i-k -> l"
"a -> b-c-o -> d-e -> g -> i-k -> l-m"
"a -> b-c-o -> d-e -> g -> i-k -> l-m-n"
"a -> b-c-o -> d-e -> g -> i-k -> m"
"a -> b-c-o -> d-e -> g -> i-k -> m-n"
"a -> b-c-o -> d-e -> g -> i-k -> n"
"a -> b-c-o -> d-e -> g -> i -> l"
"a -> b-c-o -> d-e -> g -> i -> l-m"
"a -> b-c-o -> d-e -> g -> i -> l-m-n"
"a -> b-c-o -> d-e -> g -> i -> m"
"a -> b-c-o -> d-e -> g -> i -> m-n"
"a -> b-c-o -> d-e -> g -> i -> n"
"a -> b-c-o -> d-e -> g -> k"
"a -> b-c-o -> d-e -> h"
"a -> b-c-o -> e"
"a -> b-c-o -> e -> f"
"a -> b-c-o -> e -> f-g"
"a -> b-c-o -> e -> f-g-h"
"a -> b-c-o -> e -> f-g-h -> i"
"a -> b-c-o -> e -> f-g-h -> i-k"
"a -> b-c-o -> e -> f-g-h -> i-k -> l"
"a -> b-c-o -> e -> f-g-h -> i-k -> l-m"
"a -> b-c-o -> e -> f-g-h -> i-k -> l-m-n"
"a -> b-c-o -> e -> f-g-h -> i-k -> m"
"a -> b-c-o -> e -> f-g-h -> i-k -> m-n"
"a -> b-c-o -> e -> f-g-h -> i-k -> n"
"a -> b-c-o -> e -> f-g-h -> i -> l"
"a -> b-c-o -> e -> f-g-h -> i -> l-m"
"a -> b-c-o -> e -> f-g-h -> i -> l-m-n"
"a -> b-c-o -> e -> f-g-h -> i -> m"
"a -> b-c-o -> e -> f-g-h -> i -> m-n"
"a -> b-c-o -> e -> f-g-h -> i -> n"
"a -> b-c-o -> e -> f-g-h -> k"
"a -> b-c-o -> e -> f-g -> i"
"a -> b-c-o -> e -> f-g -> i-k"
"a -> b-c-o -> e -> f-g -> i-k -> l"
"a -> b-c-o -> e -> f-g -> i-k -> l-m"
"a -> b-c-o -> e -> f-g -> i-k -> l-m-n"
"a -> b-c-o -> e -> f-g -> i-k -> m"
"a -> b-c-o -> e -> f-g -> i-k -> m-n"
"a -> b-c-o -> e -> f-g -> i-k -> n"
"a -> b-c-o -> e -> f-g -> i -> l"
"a -> b-c-o -> e -> f-g -> i -> l-m"
"a -> b-c-o -> e -> f-g -> i -> l-m-n"
"a -> b-c-o -> e -> f-g -> i -> m"
"a -> b-c-o -> e -> f-g -> i -> m-n"
"a -> b-c-o -> e -> f-g -> i -> n"
"a -> b-c-o -> e -> f-g -> k"
"a -> b-c-o -> e -> g"
"a -> b-c-o -> e -> g-h"
"a -> b-c-o -> e -> g-h -> i"
"a -> b-c-o -> e -> g-h -> i-k"
"a -> b-c-o -> e -> g-h -> i-k -> l"
"a -> b-c-o -> e -> g-h -> i-k -> l-m"
"a -> b-c-o -> e -> g-h -> i-k -> l-m-n"
"a -> b-c-o -> e -> g-h -> i-k -> m"
"a -> b-c-o -> e -> g-h -> i-k -> m-n"
"a -> b-c-o -> e -> g-h -> i-k -> n"
"a -> b-c-o -> e -> g-h -> i -> l"
"a -> b-c-o -> e -> g-h -> i -> l-m"
"a -> b-c-o -> e -> g-h -> i -> l-m-n"
"a -> b-c-o -> e -> g-h -> i -> m"
"a -> b-c-o -> e -> g-h -> i -> m-n"
"a -> b-c-o -> e -> g-h -> i -> n"
"a -> b-c-o -> e -> g-h -> k"
"a -> b-c-o -> e -> g -> i"
"a -> b-c-o -> e -> g -> i-k"
"a -> b-c-o -> e -> g -> i-k -> l"
"a -> b-c-o -> e -> g -> i-k -> l-m"
"a -> b-c-o -> e -> g -> i-k -> l-m-n"
"a -> b-c-o -> e -> g -> i-k -> m"
"a -> b-c-o -> e -> g -> i-k -> m-n"
"a -> b-c-o -> e -> g -> i-k -> n"
"a -> b-c-o -> e -> g -> i -> l"
"a -> b-c-o -> e -> g -> i -> l-m"
"a -> b-c-o -> e -> g -> i -> l-m-n"
"a -> b-c-o -> e -> g -> i -> m"
"a -> b-c-o -> e -> g -> i -> m-n"
"a -> b-c-o -> e -> g -> i -> n"
"a -> b-c-o -> e -> g -> k"
"a -> b-c-o -> e -> h"
"a -> b -> d"
"a -> b -> d-e"
"a -> b -> d-e -> f"
"a -> b -> d-e -> f-g"
"a -> b -> d-e -> f-g-h"
"a -> b -> d-e -> f-g-h -> i"
"a -> b -> d-e -> f-g-h -> i-k"
"a -> b -> d-e -> f-g-h -> i-k -> l"
"a -> b -> d-e -> f-g-h -> i-k -> l-m"
"a -> b -> d-e -> f-g-h -> i-k -> l-m-n"
"a -> b -> d-e -> f-g-h -> i-k -> m"
"a -> b -> d-e -> f-g-h -> i-k -> m-n"
"a -> b -> d-e -> f-g-h -> i-k -> n"
"a -> b -> d-e -> f-g-h -> i -> l"
"a -> b -> d-e -> f-g-h -> i -> l-m"
"a -> b -> d-e -> f-g-h -> i -> l-m-n"
"a -> b -> d-e -> f-g-h -> i -> m"
"a -> b -> d-e -> f-g-h -> i -> m-n"
"a -> b -> d-e -> f-g-h -> i -> n"
"a -> b -> d-e -> f-g-h -> k"
"a -> b -> d-e -> f-g -> i"
"a -> b -> d-e -> f-g -> i-k"
"a -> b -> d-e -> f-g -> i-k -> l"
"a -> b -> d-e -> f-g -> i-k -> l-m"
"a -> b -> d-e -> f-g -> i-k -> l-m-n"
"a -> b -> d-e -> f-g -> i-k -> m"
"a -> b -> d-e -> f-g -> i-k -> m-n"
"a -> b -> d-e -> f-g -> i-k -> n"
"a -> b -> d-e -> f-g -> i -> l"
"a -> b -> d-e -> f-g -> i -> l-m"
"a -> b -> d-e -> f-g -> i -> l-m-n"
"a -> b -> d-e -> f-g -> i -> m"
"a -> b -> d-e -> f-g -> i -> m-n"
"a -> b -> d-e -> f-g -> i -> n"
"a -> b -> d-e -> f-g -> k"
"a -> b -> d-e -> g"
"a -> b -> d-e -> g-h"
"a -> b -> d-e -> g-h -> i"
"a -> b -> d-e -> g-h -> i-k"
"a -> b -> d-e -> g-h -> i-k -> l"
"a -> b -> d-e -> g-h -> i-k -> l-m"
"a -> b -> d-e -> g-h -> i-k -> l-m-n"
"a -> b -> d-e -> g-h -> i-k -> m"
"a -> b -> d-e -> g-h -> i-k -> m-n"
"a -> b -> d-e -> g-h -> i-k -> n"
"a -> b -> d-e -> g-h -> i -> l"
"a -> b -> d-e -> g-h -> i -> l-m"
"a -> b -> d-e -> g-h -> i -> l-m-n"
"a -> b -> d-e -> g-h -> i -> m"
"a -> b -> d-e -> g-h -> i -> m-n"
"a -> b -> d-e -> g-h -> i -> n"
"a -> b -> d-e -> g-h -> k"
"a -> b -> d-e -> g -> i"
"a -> b -> d-e -> g -> i-k"
"a -> b -> d-e -> g -> i-k -> l"
"a -> b -> d-e -> g -> i-k -> l-m"
"a -> b -> d-e -> g -> i-k -> l-m-n"
"a -> b -> d-e -> g -> i-k -> m"
"a -> b -> d-e -> g -> i-k -> m-n"
"a -> b -> d-e -> g -> i-k -> n"
"a -> b -> d-e -> g -> i -> l"
"a -> b -> d-e -> g -> i -> l-m"
"a -> b -> d-e -> g -> i -> l-m-n"
"a -> b -> d-e -> g -> i -> m"
"a -> b -> d-e -> g -> i -> m-n"
"a -> b -> d-e -> g -> i -> n"
"a -> b -> d-e -> g -> k"
"a -> b -> d-e -> h"
"a -> b -> e"
"a -> b -> e -> f"
"a -> b -> e -> f-g"
"a -> b -> e -> f-g-h"
"a -> b -> e -> f-g-h -> i"
"a -> b -> e -> f-g-h -> i-k"
"a -> b -> e -> f-g-h -> i-k -> l"
"a -> b -> e -> f-g-h -> i-k -> l-m"
"a -> b -> e -> f-g-h -> i-k -> l-m-n"
"a -> b -> e -> f-g-h -> i-k -> m"
"a -> b -> e -> f-g-h -> i-k -> m-n"
"a -> b -> e -> f-g-h -> i-k -> n"
"a -> b -> e -> f-g-h -> i -> l"
"a -> b -> e -> f-g-h -> i -> l-m"
"a -> b -> e -> f-g-h -> i -> l-m-n"
"a -> b -> e -> f-g-h -> i -> m"
"a -> b -> e -> f-g-h -> i -> m-n"
"a -> b -> e -> f-g-h -> i -> n"
"a -> b -> e -> f-g-h -> k"
"a -> b -> e -> f-g -> i"
"a -> b -> e -> f-g -> i-k"
"a -> b -> e -> f-g -> i-k -> l"
"a -> b -> e -> f-g -> i-k -> l-m"
"a -> b -> e -> f-g -> i-k -> l-m-n"
"a -> b -> e -> f-g -> i-k -> m"
"a -> b -> e -> f-g -> i-k -> m-n"
"a -> b -> e -> f-g -> i-k -> n"
"a -> b -> e -> f-g -> i -> l"
"a -> b -> e -> f-g -> i -> l-m"
"a -> b -> e -> f-g -> i -> l-m-n"
"a -> b -> e -> f-g -> i -> m"
"a -> b -> e -> f-g -> i -> m-n"
"a -> b -> e -> f-g -> i -> n"
"a -> b -> e -> f-g -> k"
"a -> b -> e -> g"
"a -> b -> e -> g-h"
"a -> b -> e -> g-h -> i"
"a -> b -> e -> g-h -> i-k"
"a -> b -> e -> g-h -> i-k -> l"
"a -> b -> e -> g-h -> i-k -> l-m"
"a -> b -> e -> g-h -> i-k -> l-m-n"
"a -> b -> e -> g-h -> i-k -> m"
"a -> b -> e -> g-h -> i-k -> m-n"
"a -> b -> e -> g-h -> i-k -> n"
"a -> b -> e -> g-h -> i -> l"
"a -> b -> e -> g-h -> i -> l-m"
"a -> b -> e -> g-h -> i -> l-m-n"
"a -> b -> e -> g-h -> i -> m"
"a -> b -> e -> g-h -> i -> m-n"
"a -> b -> e -> g-h -> i -> n"
"a -> b -> e -> g-h -> k"
"a -> b -> e -> g -> i"
"a -> b -> e -> g -> i-k"
"a -> b -> e -> g -> i-k -> l"
"a -> b -> e -> g -> i-k -> l-m"
"a -> b -> e -> g -> i-k -> l-m-n"
"a -> b -> e -> g -> i-k -> m"
"a -> b -> e -> g -> i-k -> m-n"
"a -> b -> e -> g -> i-k -> n"
"a -> b -> e -> g -> i -> l"
"a -> b -> e -> g -> i -> l-m"
"a -> b -> e -> g -> i -> l-m-n"
"a -> b -> e -> g -> i -> m"
"a -> b -> e -> g -> i -> m-n"
"a -> b -> e -> g -> i -> n"
"a -> b -> e -> g -> k"
"a -> b -> e -> h"
"a -> c"
"a -> c-o"
"a -> o"
Results (plus head node): 412
Could anyone tell me whether the problem I'm describing is a real/existing algorithm, and how bad/far off my solution is so far? It's probably O(n^10) or something ridiculous too.
Thank you!
Hi, this is a great project. Thanks.
I have a concern that I would like to share.
For instance, looking at /algorithms/math/factorial
which is one of the most basic math topic:
https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/factorial
I found 2 implementations:
export default function factorial(number) {
let result = 1;
for (let i = 2; i <= number; i += 1) {
result *= i;
}
return result;
}
export default function factorialRecursive(number) {
return number > 1 ? number * factorialRecursive(number - 1) : 1;
}
factorial.js
is a code of Procedural/Imperative programming style, and uses mutable variables.
factorialRecursive.js
is recursive, and can be said functional programming style, immutable. Alghouth this is a typical implementation which I can see everywhere, in terms of "Big O notations". this is rather anti-pattern.
A better or I would say, a proper way is,
//[...Array(5).keys()]
//-> [ 0, 1, 2, 3 ,4 ]
const natural = n => {
const arr0 = [...Array(n + 1).keys()];
const [first, ...arr] = arr0;
return arr;
};
console.log(
natural(5) //[ 1, 2, 3, 4, 5 ]
);
function factorialFunctional(number) {
const list = number < 1
? [1]
: natural(number)
const multiply = (a, b) => a * b;
return list.reduce(multiply);
}
console.log(
factorialFunctional(5)//120
);
This is as efficient as the factorial.js
in terms of "Big O notations", and immutable.
I think when algorithms are presented, it's significantly important to clarify what kind of programming paradigm the algorithms are based on.
Currently, it seems the contributions are updated randomly without formal classification for them, and I think it's a good idea to show a guideline in the README that to clarify which paradigm every algorithm belongs to. In this manner, a contributors notice "oh, here, there is no Functional or Imperative pattern yet, so I will add.."
Thanks.
Hello, Can I try to translate the repo to Chinese?
How about creating a workshopper? I would love to create one.
In the HashTable implementation currently there is no collision resolution mechanism. The following insertion method updates the existing node. There can be chaining or open addressing methods implemented.
insert(key, value) {
const bucketLinkedList = this.buckets[this.hash(key)];
const node = bucketLinkedList.find({ callback: nodeValue => nodeValue.key === key });
if (!node) {
// Insert new node.
bucketLinkedList.append({ key, value });
} else {
// Update value of existing node.
node.value.value = value;
}
}
I'm thinking of adding Big O notation to the docs based on Big-O Cheat Sheet. Would this be useful?
I'd of thought you'd do it like -
peek() {
if (this.isEmpty()) {
return null;
}
return this.linkedList.tail.value;
}
i want to wirte a js to test a data-structures class ,as queue, but this js file can't run on lastest version nodejs? how can i run my test?
Not an issue - more of a suggestion. Is it better to start the loop from 2οΌ
export default function factorial(number) {
let result = 1;
for (let i = 2; i <= number; i += 1) {
result *= i;
}
return result;
}
a suggestion for improve quality, readability and robustness of the algorithms is to have test cases.
without tests it is hard to know if the algorithms / data structure works as intended.
Hello,
I recently tried to run some property based tests on the algorithms provided in javascript-algorithms.
I discovered the following failing case with rabinKarp algorithm:
expect(rabinKarp("^ !/'#'pp", " !/'#'pp")).toBe(2); // output: -1
In order to find it, I used fast-check framework with the property:
// for any strings a, b and c
// rabinKarp(a + b + c, b) should be different from -1 (indeed b is a substring of a+b+c)
fc.assert(
fc.property(
fc.string(), fc.string(), fc.string(),
(a, b, c) => rabinKarp(a + b + c, b) !== -1
)
);
I was not able to have a smaller example for this precise case :/
Thank you for creating this repo, it's awesome.
I just have one small question, can you divide all algorithms into group of level like: Beginner, Intermediate, Advance , etc so someone like students or newbies know where to start?
Hi! Thanks for your project. I can't seem to find the removal algorithm in AVL tree: if it simply borrows the binary tree removal, it's incomplete. I was particularly interested in that, cause I have been looking for a removal procedure that doesn't mutate the nodes.
Cheers.
It seems that the algorithm longestCommonSubstring does not handle unicode characters properly:
longestCommonSubstr('π΅π΅**ABC', 'π΅π΅--ABC') === 'π΅π΅'
// whereas the longest one should be ABC (in terms of number of code points)
// Number of code points:
[...'π΅π΅'].length === 2
[...'ABC'].length === 3
// Number of "characters":
'π΅π΅'.length === 4
'ABC'.length === 3
You should maybe add a note on the algorithm regarding this. Basically the problem can occur whenever the strings contain characters outside the BMP range (ie code points greater than 0xffff).
Feel free to close the issue whenever you want. The aim was just to signal the problem is case you want to patch it in a way.
https://en.wikipedia.org/wiki/Liu_Hui's_%CF%80_algorithm
e.g:
const getSideLength = (sideLength, count) => {
if (count <= 0) return sideLength;
const m = sideLength / 2;
const g = Math.sqrt((0.5 ** 2) - (m ** 2));
const j = 0.5 - g;
return getSideLength(Math.sqrt((j ** 2) + (m ** 2)), count - 1);
};
const pi = (splitCount = 0) => {
const sideLength = getSideLength(0.5, splitCount);
const sideCount = 6 * (splitCount ? 2 ** splitCount : 1);
return sideLength * sideCount;
};
// for (let i = 0; i < 100; i += 1) {
// const p = pi(i);
// console.log(i, p, p === Math.PI);
// }
export default pi;
I believe it would be nice to translate the README.md to Spanish and would love to help!
Not an issue - more of a suggestion. Would be good to return an array for the fibonacci sequence, as well as the sequence at nth position (and maybe rename the nth-position fibonacciNth()
or something). For example:
export default function fibonacci(steps) {
const fibSequence = [];
let currentValue = 1;
let previousValue = 0;
if(steps === 1) {
return [1];
}
while(steps--) {
currentValue += previousValue;
previousValue = (currentValue - previousValue);
fibSequence.push(currentValue);
}
return fibSequence;
}
And:
export default function fibonacciNth(steps) {
let currentValue = 1;
let previousValue = 0;
if(steps === 1) {
return 1;
}
while(steps--) {
currentValue += previousValue;
previousValue = (currentValue - previousValue);
}
return currentValue;
}
Also, where before there was a:
while(iterationsCounter) {
// Do code
iterationsCounter -= 1;
}
This is mildly verbose, and can be more succinctly written without detriment to legibility as:
while(iterationsCounter--) {
// Do code
}
Personally I think that's more readable. Happy to do a PR?
Edit: camel cased variable names to match existing code
in rotateLeftRight, while leftRightNode has left child, it will be lost.
also as well rotateRightLeft.
the following code is my correction.
rotateLeftRight(rootNode) {
// Detach left node from rootNode since it is going to be replaced.
const leftNode = rootNode.left;
rootNode.setLeft(null);
// Detach right node from leftNode.
const leftRightNode = leftNode.right;
leftNode.setRight(null);
if (leftRightNode.left) {
leftNode.setRight(leftRightNode.left);
leftRightNode.setLeft(null);
}
// Attach leftRightNode to the rootNode.
rootNode.setLeft(leftRightNode);
// Attach leftNode as left node for leftRight node.
leftRightNode.setLeft(leftNode);
// Do left-left rotation.
this.rotateLeftLeft(rootNode);
}
rotateRightLeft(rootNode) {
// Detach right node from rootNode since it is going to be replaced.
const rightNode = rootNode.right;
rootNode.setRight(null);
// Detach left node from rightNode.
const rightLeftNode = rightNode.left;
rightNode.setLeft(null);
if (rightLeftNode.right) {
rightNode.setLeft(rightLeftNode.right);
rightLeftNode.setRight(null);
}
// Attach rightLeftNode to the rootNode.
rootNode.setRight(rightLeftNode);
// Attach rightNode as right node for rightLeft node.
rightLeftNode.setRight(rightNode);
// Do right-right rotation.
this.rotateRightRight(rootNode);
}
see javascript-algorithms/src/data-structures/tree/red-black-tree/readme.md
There are four pictures describe the red-black tree's four cases(LL /LR /RR /RL).But the Right Right Case
and the Right Left Case
's picture are the same.
You've created a wonderful repository!
It's really interesting, especially for learning purposes, like in my case.
What do you think about adding a new section that explains how to calculate 3D geometry functions?
the algorithm ignores itemsInStock count
This file contains some grammatical errors and could use better sentence arrangements
Hello,
I have once write Red Black Tree in Java and interesting to write another version in Javascript. Anyone have already working on it? If no one, maybe I will pull the Red Black Tree tonight.
Regard,
Hafidz
I'm planning to get started on a segment tree implementation. The first step would be to implement Range Min Query, then possibly a generalized implementation.
the primality test won't work for float between 1 and 3
Please add correct description for javascript-algorithms/src/data-structures/linked-list/LinkedList.js, because comment in Delete function is misleading:
// If the head must be deleted then make 2nd node to be a head.
It would be better to add:
'while' will delete all nodes with the same value, starting with the this.head.
Hi! The remove
method returns a BinarySearchTreeNode object. But there is one uncertain moment. What should be contained in the properties of this object, such as the parent
, left
, right
? Are these properties relevant? Or they must be null?
I'm looking for any implementation of Multiple Travelers Purchase Problem, any idea ?
I would like to contriblute to adding the B-Tree data structure.
It is a rather common data structure that is great for large data, I'll be glad to implement it.
Test suite failed to run
SecurityError: localStorage is not available for opaque origins
at Window.get localStorage [as localStorage] (node_modules/jsdom/lib/jsdom/browser/Window.js:257:15)
at Array.forEach (<anonymous>)
Shouldn't there be doubly linked list too?
If yes, can I contribute for it?
"This structure allows for efficient insertion or removal of elements from any position in the sequence during iteration." - Not correct for removal. Deleting a node from a linked list is not efficient as you have to traverse the list (in case it is very large list then it will not be optimal) The option is to use Vector.
Hello!!
I want to translate README into Korean.
Can I?
And, are there any restriction?
A Max Heap DS would be terrific in this repo. Should I work on it and submit a PR? I'm also open to other DS or algorithm contributions.
Apologies if this is the expected behavior. In BinaryTreeNode.js, the function removeChild sets either this.left or this.right to null, but does not set nodeToRemove.parent to null. So for example the following test fails:
const rootNode = new BinarySearchTreeNode('foo');
rootNode.insert('bar');
const childNode = rootNode.find('bar');
rootNode.remove('bar');
expect(childNode.parent).toBeNull();
Hi @trekhleb,
This is one amazing project. Thank you for working on it.
I just wanted to quickly share a similar effort I made last year for building a consumable algorithms and data structure library. I did heavily test it. I hope this might help someone.
https://github.com/ManrajGrover/algorithms-js
Maybe, we can link it in README somewhere?
Hello.
I want to translate all README into Russian, are there any rules for translation?
Hey! This repo is awesome! Nice job!
While I was reading through the algorithms, I found weird that the A* algorithm was missing, which is one of the few I know.
I'm just gonna leave this as a suggestion, sorry if I can't do a pull request!
Removing words in a Trie seems equally important as adding words. It would be nice to have that.
I'm thinking of adding pseudocode to the readme based on DSA by Granville Barnett and Luca Del Tongo. Would this be useful?
Nice, it is so useful for us !
I'm new to open source,I wanted to implement z-algorithm for strings
I found this repo while looking for a good example of rope. But I can't find one :(
##I found the algorithm is so hard to understand that I almost pulled my hairs off. I tried to analyze it in Python tutor but It didn't get easier. After struggling for a few hours, I figured a solution that is more expressive and easier to understand.
function comboWithoutRepeat(chooseFrom, numChosen) {
const combinations = []
function recursive(chooseFrom, numChosen, path = []) {
if (numChosen === 0) {
combinations.push(path)
return
}
for (let i = 0; i <= chooseFrom.length - numChosen; i++) {
const letter = chooseFrom[i]
const rest = chooseFrom.slice(i + 1)
recursive(rest, numChosen - 1, [letter].concat(path))
}
}
recursive(chooseFrom, numChosen)
return combinations
}
console.log(comboWithoutRepeat([1, 2, 3, 4], 3, ''))
Hi! I'm new to this repository and would like to try to implement the binary indexed tree!
Shouldn't it be classified as "Beginner"?
Hi, can I translate the README.md to Polish? Thanks.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
π Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. πππ
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google β€οΈ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.