messin' with subset-sum

subset-sum-dynamic.rb

def subset_sum(set, length)
  map = Hash.new { |h, k| h[k] = Hash.new([]) }

  map[set.first][1] = [set.first]

  1.upto(set.length - 1) do |i|
    map.keys.each do |sum|
      new_sum = sum + set[i]

      map[sum].keys.each do |subset_len|
        new_len = subset_len + 1
        new_set = map[sum][subset_len] + [set[i]]

        if new_len == length && new_sum == 0
          return new_set
        elsif new_len < length
          map[new_sum][subset_len + 1] = new_set
        end
      end

    end

    map[set[i]][1] ||= [set[i]]
  end

  return nil
end

def rand_set(len)
  len.times.each_with_object([]) do |_, arr|
    arr << rand(-5000..5000)
  end
end

subset-sum.hs

import System.Random
import Data.List
import qualified Data.Map.Strict as M
import qualified Data.Set as S
import Control.Monad

subsetSum :: [Int] -> [Int] -> [Int]

subsetSum set subset
  | ssum == 0 && (not . null) subset = subset
  | null set = []
  | otherwise = let incl = subsetSum xs (x:subset)
                    nincl = subsetSum xs subset
                in  if null incl then nincl else incl
  where (x:xs) = set
        ssum = sum subset

subsetSumOfLength len set subset
  | ssum == 0 && length subset == len = subset
  | null set = []
  | otherwise = let incl = subsetSumOfLength len xs (x:subset)
                    nincl = subsetSumOfLength len xs subset
                in  if null incl then nincl else incl
  where (x:xs) = set
        ssum = sum subset

randList :: Int -> IO [Int]
randList len = do
  gen <- newStdGen
  return $ take len $ unfoldr uf gen
  where uf gen = let (r, gen') = next gen in Just (r `mod` 100000 - 49999, gen')

subsetSumOfLengthDynamic :: Int -> [Int] -> Maybe [Int]
subsetSumOfLengthDynamic n set =
  case ssol of
    Left xs -> Just xs
    _ -> Nothing
  where
    ssol :: Either [Int] (M.Map Int (M.Map Int [Int]))
    ssol = foldM f M.empty set
    f sumMap x = do sumMap' <- foldM g sumMap (M.toList sumMap)
                    return $ M.insertWith M.union x (M.singleton 1 [x]) sumMap'
      where
        g sumMap (sum, lengthMap) = foldM h sumMap (M.toList lengthMap)
          where
            h sumMap (length, subset)
              | sum' == 0 && length == n - 1 = Left subset'
              | length == n - 1 = Right sumMap
              | otherwise = Right $ M.insertWith
                                      M.union sum' (M.singleton (length + 1) subset') sumMap
              where
                sum' = sum + x
                subset' = x : subset

main = do
  list <- randList 10000
  forM_ [3..10] $ \n -> putStrLn $ show $ subsetSumOfLengthDynamic n list