Re: Permuatations [was: Please Help!!Daughter...]

Daniel Dyer wrote:

> http://www.merriampark.com/perm.htm

Thanks to everyone who replied.

The thing is that all of the solutions referred to seem to be based on
exchanging elements. And that clearly cannot generate all the permutations of
length 2 of elements of the string A B C.

In fact I couldn't find anything that didn't start off by being dazzled by the
mathematical purity of exchanging elements. The best references I found were a
1977 review paper by Sedgewick (which starts off by saying "Over thirty
algorithms have been published during the last twenty years for generating
[permutations]", and then unifies them into a framework based on exchanges),
and -- inevitably -- Knuth. It's all very interesting, but none of it does
what I want :-(

It isn't that I don't know how to generate permutations (of substrings). For
instance any of the above algorithms could be applied to each combination in
turn. But it seems strange that while one can iterate over any of:
the length R combinations,
the length R combinations-with-repetition,
the length R permutations-with-repetition,
and the length R subsequences[*]
of N elements using minor variations to the framework in the original
algorithm, there is no obvious way of doing the permutations with the same
framework. It is obvious that the auxiliary array 'a' /does/ contain enough
information to permit generating permutations -- just iterate the
permutations-with-repetition skipping candidates with repeated elements, but
that's O(N**R) not O(N perm R). I still suspect that it /should/ be doable,
but can't think of or find a way of doing it. (The nearest I've got so far
requires keeping an addition Set of size O(R) and is basically the
generate-and-discard algorithm with a bit of early pruning).

-- chris

([*] same algorithm as for length R combinations)


.

Relevant Pages

  • Re: Strategy or Iterator?
    ... private int count; ... Dijkstra's algorithm generates permutations, ... All possible subsequences of length N of the input (considered to be ...
    (comp.lang.java.programmer)
  • 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: 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)