Tag Archives: algorithm

Computing Eulerian paths is harder than you think

Everyone who has studied any graph theory at all knows the celebrated story of the Seven Bridges of Königsberg, and how Euler gave birth to modern graph theory while solving the problem. Euler’s proof is clever, incisive, not hard to … Continue reading

Posted in learning | Tagged , , , , | 3 Comments

Counting inversions with monoidal sparks

Time for me to reveal the example I had in mind that led to the generalization in my previous post. Thanks for all the interesting comments: it seems like there are some interesting connections to be explored (e.g. to the … Continue reading

Posted in math | Tagged , , , , , , , , | 7 Comments

Any clues about this Newton iteration formula with Jacobian matrix?

A while ago I wrote about using Boltzmann sampling to generate random instances of algebraic data types, and mentioned that I have some code I inherited for doing the core computations. There is one part of the code that I … Continue reading

Posted in math | Tagged , , , , , , | 8 Comments

Math.Combinatorics.Multiset and Sawada’s algorithm

I’ve uploaded a new version of my Math.Combinatorics.Multiset library (see the previous announcement here). I’ve added a few more fairly simple algorithms (splitting a multiset into two pieces in all possible ways; finding all size-k submultisets of a multiset), and … Continue reading

Posted in haskell, links, math | Tagged , , , , | 4 Comments

Math.Combinatorics.Multiset

Just a quick note to say that I’ve just uploaded a new package, multiset-comb, to Hackage. It primarily has functions for generating all the distinct permutations and partitions of a multiset (a set where elements are allowed to occur multiple … Continue reading

Posted in haskell, projects | Tagged , , , , | 4 Comments