Hi Mark,
For a direct recursive version, you can try this. Making Concat tail
recursive is left as an exercise ;-)
fun {Combinations Xs}
case Xs
of nil then [nil]
[] X|Xr then
Hs={Choices X}
Ts={Combinations Xr}
in
{Concat {Map Hs fun {$ H} {Map Ts fun {$ T} H|T end} end}}
else
end
fun {Choices X}
if {Tuple.is X} then {Record.toList X} else [X] end
end
fun {Concat Ls}
case Ls
of nil then nil
[] L|Lr then {Append L {Concat Lr}}
end
end
Cheers,
Raphael
On Tue, Feb 9, 2010 at 3:35 PM, mark richardson <[email protected]>wrote:
> Hi,
>
> The question arises from some work a colleague of mine is doing in formal
> methods. They use FORTH as a prototype language so a 'direct recursive
> algorithm' would be best but they are also testing the use of choice points,
> so choice (or something similar) is necessary.
> What would be ideal would be a single tail-recursive function with
> integrated choice.
>
> Regards
>
> Mark
>
> Wolfgang Meyer wrote:
>
> P.S.: If you really need performance, you should probably use a direct
> recursive algorithm for the n-ary Cartesian product, without using
> search/logic programming.
>
> Cheers,
> Wolfgang
>
>
> On Tue, Feb 9, 2010 at 2:05 PM, mark richardson
> <[email protected]>wrote:
>
>> Hi,
>>
>> I have a short script to calculate all possible combinations of a list
>> such as [1#2 3 4#5] , the tuples representing a choice between two values.
>> Solutions to this would be [1 3 4] [1 3 5] [2 3 4] [2 3 5] for example.
>> The problem translates quite nicely into a constraint based search using
>> FD but it set me wondering if their was a more efficient approach using
>> choice or dis recursively (ie. without using loops)
>> I've had no success as yet trying to find such a solution and wondered if
>> anyone had any opinions on this?
>>
>> Regards
>>
>> Mark
>>
>> --
>> Mark Richardson MBCS
>> Research Assistant
>> University of Teesside, UK
>> Email: [email protected]
>> [email protected]
>> Skype: mark.richardson.
>>
>>
>> _________________________________________________________________________________
>> mozart-users mailing list
>> [email protected]
>> http://www.mozart-oz.org/mailman/listinfo/mozart-users
>>
>
> ------------------------------
>
> _________________________________________________________________________________
> mozart-users mailing list
> [email protected]http://www.mozart-oz.org/mailman/listinfo/mozart-users
>
>
>
> --
> Mark Richardson MBCS
> Research Assistant
> University of Teesside, UK
> Email: [email protected]
> [email protected]
> Skype: mark.richardson.
>
>
>
> _________________________________________________________________________________
> mozart-users mailing list
> [email protected]
> http://www.mozart-oz.org/mailman/listinfo/mozart-users
>
_________________________________________________________________________________
mozart-users mailing list
[email protected]
http://www.mozart-oz.org/mailman/listinfo/mozart-users
