"Make everything as simple as possible, but not simpler." -- Albert Einstein

Ask Robin Houston, author of Algorithm::FastPermute.

For some reason robin doesn't bring his grate brane here very often, so I passed the question on. Verbatim:

The most obvious use of an exhaustive permutation generator is brute force search. Examples aren't difficult to come up with - see for example Jason Brazile's 1998 TPJ article Iterating Over Permutations which begins "My nephew asked for help with a homework problem" and proceeds to show how a permutation generator can be used to brute force a solution to the problem.

The ideal motivating problem would be one that is:
a) Susceptible to brute force search over permutations
b) Not obviously solvable by a more efficient method
c) As natural (uncontrived) as possible.

There is an extensive directory of NP-complete problems which satisfy (b) and (c), which would seem to be a good place to start looking.

For example, the minimum linear arrangement problem obviously satsfies condition (a).

More useful, perhaps, is the problem of "Sequencing with Release Times and Deadlines" which any programmer who has to manage her own time will be informally familiar with! That can be solved by trying all the possible ordering of tasks (i.e. all the permutations of the task list) until an ordering is found which works (or not).

Also, not just only for genetic simulations, but for other cases where order may or may not matter (say, travelling salesmen approach with genetic algorithsm), permutations are easier to start with then trying to build up a 'random' list .

-----------------------------------------------------
Dr. Michael K. Neylon - mneylon-pm@masemware.com || "You've left the lens cap of your mind on again, Pinky" - The Brain
It's not what you know, but knowing how to find it if you don't know that's important

I've had to write code which generates programmes of study for students (although I did it in C, not perl), and it relates to power sets, not permuations. But they're similar problems. (Power sets, if you aren't aware, are all the possible subsets of a set. So there are n! permutations of a list, but 2ⁿ power sets.)

Since I was working for a modular course, the students frequently had to take 2 out of <these 3 modules>, and 2 out of <these other 4 modules> etc, etc.

The brute force and ignorance method (and oh boy, was there ever a lot of ignorance. Unfortunately, the force wasn't quite as brute as the algorithm demanded...) was to generate the power set of the target list, merge it with the student's existing program and then delete those results which didn't meet requirements (or were more complicated than necessary).

Turned out, permutations was the trick . . . here is the original question (asked by proxy - eduardo):

permutations?

jeffa

For a given mass (as detected via mass spectrometry), determine the combinations of atomic weights that could possibly combine into a fragment of that mass.

One way to solve this problem is by permuting large lists of atomic weights, for those atoms which are considered likely candidates under the circumstances.

buckaduck