F# all permutations of C# class

Question

I have a C# class MyClass.

And I would need to implement f# method returning all possible permutations of items in a IList

Problem is that MyClass contains a method bool CheckOrder(IList predecessors) returning true if the instance of MyClass can be placed in the permutation after instances of MyClass in the parameter. Otherwisem this method returns false.

Please, could anyone advise me how to implement a proper F# function.

Update: Please, could you outline F# code of the method test considering my C# class having method: bool CheckOrder(IList predecessors)

These may be of interest: http://stackoverflow.com/questions/286427/calculating-permutations-in-f; http://stackoverflow.com/questions/1526046/f-permutations — Daniel, Apr 07 '11 at 17:42
With this interface, the only solution seems to be "Generate and Test", i.e. create all permutations and then filter them. This can be impractical for large lists. With a more explicit representation of the ordering constraints, an efficient implementation should be possible, using techniques from scheduling and constraint programming. Maybe take a look at Microsoft Solver Foundation. — wmeyer, Apr 07 '11 at 19:49

score 0 · Answer 1 · answered Apr 11 '11 at 15:58

Your CheckOrder method expects an IList<MyClass>, so we should maybe work with arrays in F#, since arrays implement the IList interface.

For every element in a permutation candidate, we need to check whether all its predecessors in the array are legal. To me, that looks like a job for a fold operation where the fold's state parameter is a tuple of the "array so far" and a boolean success flag.

let checkPermutation (permutation:MyClass[]) =
   let prefix, success =
      permutation
      |> Array.fold (fun (prefix:MyClass[], success) element ->
                        if not success then
                           (Array.empty, false) // once failed, the result is false
                        else
                           (Array.append [|element|] prefix, element.CheckOrder prefix)
                    )
                    (Array.empty, true)
   success

Array.append is probably quite inefficient. If this is too slow, you should consider using a ResizeArray (which is the same as a C# List) instead.

F# all permutations of C# class

1 Answers1