Skip to content

Instantly share code, notes, and snippets.

View MichaelBurge's full-sized avatar

Michael MichaelBurge

View GitHub Profile
@Icelandjack
Icelandjack / gist:1a57ae22fe221ef9a67c96dc24b4751f
Created September 28, 2017 10:54
TODO Divisible implement later
@fedelebron
fedelebron / Permanent.hs
Created August 19, 2013 01:21
A function to compute the permanent of a matrix in Haskell. The algorithm is not as efficient as it could be - it is using the Ryser formula for an O(n^2 * 2^n) runtime, where a O(n * 2^n) algorithm exists, which uses the same idea but adds Gray codes to compute the subsets in a better order, allowing a reuse of computations.
{-# LANGUAGE FlexibleContexts #-}
import Data.Array.IArray (IArray, bounds)
import Data.Array.Unboxed (UArray)
import Data.Array.Base (unsafeAt)
import Data.Bits (popCount, testBit)
permanent :: (Integral a, IArray UArray a) => UArray (Int, Int) a -> a
permanent arr | n == m = (if even n then negate else id) (sum entries)
where
((0, 0), (n, m)) = bounds arr