Need programming help

[aneeshm]

Originally posted by Thue
The problem solved in ML; this solution is nicer.

This is programmed using a very functionel strategy, somewhat different from the PHP one used above. It seemed so much nicer that I tried translating it to php afterwards, but I ended up with a PHP program larger and uglier than the PHP program above.

val chars = ["a", "b", "c"];

fun gen (a::arest) bs       res = (gen (arest@bs) [] (a::res))@(gen arest (a::bs) res)
  | gen []       []       res = [res]
  | gen []       bs       res = [];

gen     chars    []       [];

Whatever this is, it's brilliant. I apt-got mosml (Moscow ML), and saved the above program in a file, and changed the values in the val chars to the string I wanted, and it gave me all the results I wanted.

Could you please explain the logic to me? I don't get it, not being familiar with ML.

[Thue]

It is fairly simple. "gen" is a recursive function which recursively descends through all permutations. It takes 3 arguments.
-The first ('a's) is the list of possible next characters (which of course have not been used in the current "res").
-The bs are the characters which are not used yet in the current "res", but which we don't want to use as the next character.
-"res" is the partial string we have have build up. Once we run out of unused characters to append we return it as one of the results.

Each call of "gen" matches exactly one of the branches (one branch per line) The first branch

fun gen (a::arest) bs       res = (gen (arest@bs) [] (a::res))@(gen arest (a::bs) res)

This is essentially an iteration (using recursion) through all characters in the first argument. For each possible "a" character in the list (a::arest), generate all string which start with "a".

-"(gen (arest@bs) [] (a::res))" is a recursive call which generated all strings with "a" as the next character in "res". All unused characters are possible as the next character, so set the "a" argument to "(arest@bs)".
-"(gen arest (a::bs) res)" is a recursive call which generates all strings where the next character is in the list arest. Appends a to "bs" in a recursive call, ie saves it among the characters which have not been used in "res" yet.
-"@" appends the lists of result lists which are returned by the two calls.

Line/branch two

 | gen []       []       res = [res]

Is the end of a successful recursive descend; we have appended characters one by one to res until all characters have been used, and per construction they must have been used exactly one. So return a one-element list with the current string ("[res]").

Line 3:

  | gen []       bs       res = [];

This one catches the end of the iteration over the as in line 1, the ".(gen arest (a::bs) res)" part of that line where arest turns out to be empty. Just return the empty result.

[Solver]

It's hard to argue against the awesome efficiency of functional programming in cases like this...

[Jack_www]

I found an article on msdn that show you how to do this with strings in C++, but I am sure you can adapt it to one string. Here is the link:

http://msdn.microsoft.com/msdnmag/issues/06/12/TestRun/