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

Daniel Dyer wrote:

> http://www.merriampark.com/comb.htm
>
> I stumbled across it myself a few weeks back when looking for some code to
> generate combinations.

Nice algorithm. Does anyone know of something comparatively slick for
generating permutations ?

I like the way that the state of the overall iteration is implicit in the state
of the array ('a' in the code on the website). It's straightforward to modify
the idea so that it generates all combinations with repetitions included, and
even more straightforward to make it generate all permutations with repetitions
included, but I can't think of a comparably small change that would make it do
"normal" permutations where repetitions are not included.

It's pretty easy to generate permutations by recursion, but converting a deeply
recursive algorithm into one suitable for external iteration would take, I
think, a Stack of Iterators -- which seems excessive when the other three
closely related algorithms can be handled so elegantly.

BTW, in case it's not clear (I'm not sure if I'm using the standard
terminology) to illustrate what I mean by permutations/combinations
with/without repetitions. Given the source collection {A B C}, and wanting
sub-collections of length 2, I mean
Combinations: AB AC BA
Permutations: AB AC BA BC CA CB
Combinations with repetition: AA AB AC BB BC CC
Permutations with repetition: AA AB AC BA BB BC CA CB CC

-- chris


.

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: 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: 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)
Loading