2

Is there a way to generated pre-filtered permutations, that is rather than doing :

filter condition $ permutations list

the permutation function can short-circuit. For example :

perms [] = [[]]
perms xs = [ i:j | i <- xs, j <- perms $ delete i xs]

I tried a few obvious things like :

perms xs = [ i:j | i <- xs, j <- filter condition $ perms $ delete i xs]

I thought what would happen is this would set off a chain which would end up at [] and then work back up, but filtering along the way. However when feeding it a long list and thus speeding up the process. This doesn't seem to happen as it bogged out (ghci) when trying to do a permutation of a 20 item list that would have only very few actually filtered permutations.

Will Ness
  • 70,110
  • 9
  • 98
  • 181
Cliff Stamp
  • 531
  • 5
  • 11
  • Your "short-circuit" version doesn't match the simple version. `condition` is applied recursively in the "short-circuit" version. – Dannyu NDos Sep 01 '18 at 02:44
  • What are you trying to do exactly? It sounds like you have a predicate such that if it is false for some tail of a list then it is false for the entire list and so your goal is to write an algorithm that avoids generating and checking a bunch of permutations with the same bad tail, for performance reasons. Is that right? – jberryman Sep 01 '18 at 03:31
  • @jberryman Yes, exactly. – Cliff Stamp Sep 01 '18 at 03:33
  • 1
    What do you want if `not (condition [])`? – Dannyu NDos Sep 01 '18 at 04:53

1 Answers1

3

Coding it up in do notation with recursion is pretty straightforward.

foo :: ([a] -> Bool) -> [a] -> [[a]]
foo p xs = bar ([],xs)
   where
   bar (acc,[]) = return acc
   bar (acc,xs) = do
                   (x,ys) <- picks xs      -- shrink the domain (ys)
                   if ( p (x:acc) )        -- test soon
                     then bar (x:acc,ys)   -- loop
                     else mzero            -- fail early

picks [] = []
picks (x : xs) = (x, xs) : [(y, x : ys) | (y, ys) <- picks xs]

picks is from this answer.

Testing:

> foo (const True) [1..3]
[[3,2,1],[2,3,1],[3,1,2],[1,3,2],[2,1,3],[1,2,3]]

> foo (\(x:xs) -> not(null xs) || x > 1) [1..3]
[[3,1,2],[1,3,2],[2,1,3],[1,2,3]]

The last one starts producing its output immediately also for [1..20], [1..300] etc.

I'm sure this can be expressed neatly with higher-level stuff.

Will Ness
  • 70,110
  • 9
  • 98
  • 181