Re: Strategy or Iterator?

Hendrik Maryns wrote:

/**
* The number of permutations to go.
*/
private int count;

Note that using an int to hold the size of the output stream (N factorial) will
limit you to inputs with no more than 12 elements. If you used a long, then
you could get up to 20. If you want more, then you'll have to switch to
counting with BigIntegers, or use a different technique to detect the end of
the sequence.


* Permuter.java

Another point, do you actually want the /permutations/ ? I though you wanted
to iterate over the tuples defined by the Cartesian product of a set (or list)
with itself R times.

For instance, if the input is { A B C } and R is 2, then that sequence would
be:
A A
A B
A C
B A
B B
B C
C A
C B
C C

Dijkstra's algorithm generates permutations, which is a different concept.
Note that there is no R that you can set in his algorithm (and the way the
algorithm works makes it impossible to add an R parameter, you have to take a
completely different approach).

Dijkstra's algorithm would give (in some order):
A B C
A C B
B A C
B C A
C A B
C B A


FWIW, there are at least 5 different kinds of combination/permutation-like
sequences one can derive from an input list of size N. We can generate:

All possible subsets of size R of the input (itself considered to be a
Set), i.e. not caring about the ordering.
R must be <= N.
Usually called the "combinations" of the input.
There are N choose R (nCr) outputs.

All possible subsequences of length N of the input (considered to be
a list), preserving the ordering of the elements in the input.
R must be <= N.
There are nCr outputs (there are algorithms which can be used for
both this and combinations).

All possible tuples of R elements taken from the input. Duplications
are allowed. (The case illustrated above).
R may be > N.
There are N**R outputs.

All possible re-orderings of the input.
The R parameter is not meaningful.
Usually called the "permutations" of the input.
This is what Dijkstra's algorithm produces.
There are N! outputs.

All possible subsequences of length R of the input, subsequences
are considered to be different if the elements occur in different orders.
R may be > N.
There are N perm R (nPr) outputs.

They can all be computed by external iterators. The first three can be
implemented easily; permutations requires something like Dijkstra's algorithm;
the last is a bit of a bugger to do elegantly (you can do it inelegantly by
applying Dijkstra to each R-combination in turn).

-- chris


.

Relevant Pages

  • Re: Help with Permutations
    ... >>>In order to keep track of the progress through the algorithm, ... >>>be able to calculate the total number of permutations in advance. ... >> gives 1265, as quasi reported. ... either Maple has a bug or there's a bug in my program. ...
    (sci.math)
  • Re: Permuatations [was: Please Help!!Daughter...]
    ... mathematical purity of exchanging elements. ... ", and then unifies them into a framework based on exchanges), ... It isn't that I don't know how to generate permutations. ... generate-and-discard algorithm with a bit of early pruning). ...
    (comp.lang.java.programmer)
  • Re: Strategy or Iterator?
    ... You need GnuPG to verify this message ... * The number of permutations to go. ... private int count; ... This is what Dijkstra's algorithm produces. ...
    (comp.lang.java.programmer)
  • Re: Javascript Best Practices Document v1.0
    ... or is it not a general algorithm. ... Today you assert that the algorithm becomes 'general' when it applies to ... An algorithm that is totally specific to a single context ... permutations. ...
    (comp.lang.javascript)
  • Re: Help with Permutations
    ... >>>In order to keep track of the progress through the algorithm, ... >>>be able to calculate the total number of permutations in advance. ... >> Derek Holt. ... >is inside the sum or outside but not 1265. ...
    (sci.math)