Back to Questions
893
views2
comments
Problem with permutation algorithm.
f#

Hi,
i try to implement a permutation algorithm in F#, taken from Haskell.
The original comes from Koen Claessen (with short explanation):selections (x:xs) =
selections [] = []
(x,xs) : [ (y,x:ys) | (y,ys) <- selections xs ]permutations xs =
[ y : zs
| (y,ys) <- selections xs
, zs <- permutations ys
]
I translated this 1:1 to F#:

1
2
3
4
5
6
7

let rec selections = function
  | []      -> []
  | x::xs -> (x,xs) :: [ for (y,ys) in selections xs -> (y,x::ys) ]
let rec permutations xs =
  seq { for (y,ys) in selections xs do
          for zs in permutations ys -> y::zs }

While selections works fine, permutations does not yield anything, i.e. seq []. What is wrong?

.

Missing a case in permutations:

1
2
3
4
5
6
7
8
9
10

 

let rec selections = function
    | []      -> []
    | x::xs -> (x,xs) :: [ for (y,ys) in selections xs -> (y,x::ys) ]
let rec permutations = function
  | x::[] -> seq [[x]]
  | xs ->  seq { for (y,ys) in selections xs do
                    for zs in permutations ys do yield y::zs }

[link:www.haskell.org]

By on 4/11/2009 6:31 AM ()

Thank you MichaelGG. Should have continued reading on ...
I changed the title, because its not a problem with the sequence expression.

By on 4/11/2009 7:08 AM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper