On 17/05/2012, at 10:07 PM, Roman Werpachowski wrote:
No slide deck required. The task is "generating alternating permutations".
Method 1: generate permutations using a backtracking search; when a permutation is generated, check if it is alternating.
Method 2: use the same backtracking search, but only allow extensions that preserve the property of being an alternating permutation.
Gregg,
what makes Method 2 so much harder than Method 1 to implement in C or C++?
It was me, not Gregg. There was and is no claim that method 2 is "much harder to implement in C or C++". In fact both methods *were* implemented easily in C. The claim was and remains solely that THE TIME DIFFERENCE BETWEEN *ALGORITHMS* can be bigger than THE TIME DIFFERENCE BETWEEN *LANGUAGES* and is in this particular case. (And that's despite the fact that the C version kept the set of unused elements as a one-native-word bit mask, while the Prolog version kept it as a linked list.) There is also a second claim, which I thought was uncontentious: the relative difficulty of tasks varies with language.