Actually, the NrArrangement algorithm is exactly the enumeration algorithm
I need for the problem I'm solving. I would just like to know if there is
a reference (literature or textbook) explaining the algorithm, how it was
developed, etc.

FYI, our group has developed a novel piece of software which searches
protein sequence databases for evolutionary matches to a fragmented query
whose positional residue assignments are known but fragmentary residue
assignments are unknown (and therefore deconvolved by our algorithm).

An example is the easiest way to explain this better:

Say that the "true" matching protein has this sequence:

ACDGHTYERYGHDFIPLKFNDEQWSTRF

Let's take 3 fragments from this protein:

ACDG,
HDFI,
NDEQ

Now, shuffle the residues in each column (position):

ADEI,
NDDQ,
HCFG

This is what our queries look like. They are the result of a biochemical
experiment where an unknown protein is cleaved into fragments and then the
aggregate mixture of fragments is put into an "Edman Sequencer", which
determines the aggregate sequence of the fragments at each position, but
cannot specify to which fragment each residue belongs.

I use a variation of the NrArrangement algorithm to determine the total
number of possible "deconvolved" fragment alignments, given that an
alignment can involve between 1..K fragments. This factor helps us
to define the effective search space when calculating the statistical
significance of any alignment.

In truth, since our algorithm is not optimal, but a fast heuristic, it
turns out that for longer queries with multiple fragments, the effective
search space is much smaller than the theoretically possible search space
defined by the query, so we perform Poisson fitting to adjust our
statistics accordingly.

Both the code and the paper describing this algorithm include
acknowledgement and references to the GAP development team. But I'd also
like to know where the NrArrangment algorithm came from (if even just
"Uhh, it's obvious graduate level combinatorics").

Thanks again,

-Aaron Mackey

On Tue, 22 Feb 2000, Neil Zanella wrote:

Hi,

Are you looking for an algorithm to enumerate permutations?
If so are all of the objects being permuted indistinguishable?
Do you need a lexicographic enumeration or any enumeration?
Why do you need such an enumeration algorithm. Most such algorithms
are almost impractical as they consume a lot of time especially
for n > 15 or so. What do you need such an algorithm for?

Regards,

Neil Zanella
nzanella@cs.mun.ca

On Mon, 21 Feb 2000, Aaron J Mackey wrote:

I would be grateful for any references or pointers regarding the
enumeration algorithm used by NrArrangements. Thank you.

-Aaron Mackey

-- 
 o ~   ~   ~   ~   ~   ~  o
/ Aaron J Mackey           \
\  Dr. Pearson Laboratory  / 
 \ University of Virginia  \     
 /  (804) 924-2821          \
 \  amackey@virginia.edu    /
  o ~   ~   ~   ~   ~   ~  o

-- 
 o ~   ~   ~   ~   ~   ~  o
/ Aaron J Mackey           \
\  Dr. Pearson Laboratory  / 
 \ University of Virginia  \     
 /  (804) 924-2821          \
 \  amackey@virginia.edu    /
  o ~   ~   ~   ~   ~   ~  o

Miles-Receive-Header: reply