Federico, Please pardon my pedantry here. No flames are being directed at you ...
I think you've found the tool you said you needed, but there's a terminology problem in the module and the discussion thread that this old mathematician dearly wants to babble on about. Anyone who wants to avoid the pedantry can scan to the next </PEDANTRY> tag to pick up the tale. There's also one serious error in the POD examples for a method other than the you mentioned that is worth checking, see <WARNING> at the end, just before the <HUMOR>. <PEDANTRY Level="1"> I'm glad to see Math::Combinatorics POD links the MathWorld [http://mathworld.wolfram.com/] site for definitions, but I'm not satisfied with the module's symbology or terminology. [http://search.cpan.org/~allenday/Math-Combinatorics-0.08/lib/Math/Combi natorics.pm] The best point of departure is http://mathworld.wolfram.com/BallPicking.html . > As usual, I managed to mix things up. What iI am looking for are > *Permutations* (_with_ repetition, that part I managed to write right). That certainly got your meaning across. However, calling what you want a "Permutation with replacement" or "Permutation with repetition" is a regrettable neologism, although understandable from the examples you're looking at. This neologism was apparently inserted into a key reference work in the mid 1990's and has been slowly spreading since then. It does NOT appear on the generally excellent Wolfram site cited above. Where the author of the module found the nPRk symbol (and not the P^R(n,k) alternative) in analogy to nPk I don't know, apparently that too is in vogue in applied maths somewhere *shudder*, but that did not come from Mathworld.Wolfram.com. I hope it's not too late to stamp it out. The proper name for this in classic probability was "Ordered Sampling from an Urn with Replacement"; in modern linguistic combinatorics, it's more simply a "String", as you've found. BTW, "Replacement" is a better word than "Repetition", since it is allowed (randomly) to NOT repeat symbols from the alphabet, if the string size is shorter than the size of the alphabet. (I'm startled that MathWorld uses "Repetition" on their Ball Picking page -- I'm posting that as a comment on their page!) <PEDANTRY Level="2"> A Permutation is an order-sensitive sampling, *without* replacement, typically to exhaustion of the set, of a set (unique members of equal probability). [http://mathworld.wolfram.com/Permutation.html] The number of such Pn = n!, the factorial of n. Thus, a true permutation has the same length as the set or bag it's taken from; has multiples only if the urn, set or bag does (in which case the urn is modeled as a bag but not a set). nPk which is normally and better read "N pick K", not "n Permute K", is the non-exhausting variant of permutation, giving a prefix of a permutation. nPk= n!/(n-k)! . In classical probability, is ordered sampling of uniquely labeled balls from the Urn without replacement. One can also do ordered non-replacement sampling of 6 red and 4 white balls, but that's not called permutation. A Combination is an order-INsensitve sampling without replacement that doesn't exhaust the set. (If it exhausts it, since it's not order sensitive, it's boring ... 100% of the time, it's the same as you started with.) [http://mathworld.wolfram.com/Combination.html] I suppose I should be happy Math::Cominatorics pod only uses the nPRk symbol that some may recognize, and doesn't call it Permutation with Repetition or Replacement in the Pod. But since it returns instances of the permutation set, not the count of the permutation set, the use of the nPRk (and !n and nPk etc) symbols seem out of place to me anyway. Having optional Frequency available for Permutation and Combination voids the relevance of the nPk=n!/(n-k)! symbols in the POD. </PEDANTRY> > Math::Combinatorics does provide such method, it is called strings() Yes, it seems that a String is what a modern combinatorist speaking properly would call what you want. [http://mathworld.wolfram.com/String.html] In particularly, you said Character Set, which suggests you *might* want not only repetition but weighting of some members over others. Classically, that would be a feature of Strings, but only on extended permutations and combinations. Since the M:C String has frequency, a old-school statistician might call it a ordered sample with replacement from a mixed urn of several varieties. <PEDANTRY LEVEL="2"> An Alphabet with weights on the symbols, the weights being either Integer or Rational, is totally equivalent to sampling with replacement from a bag (or Urn), with the multiplicities being integers (to which rationals can be converted using 5th grade LCD). Classical Permutations and classical Combinations can be extended to handle multiplicities, so for M:C to speak of Permutations with optional frequencies is not unreasonable. A string from a weighted alphabet is no more general than ordered sampling from a bag, unless irrational weights are permitted. However, avoiding irrational weights is a reasonable limitation for practical applications. (Thus, M:C uses integer weights, but calls them frequencies.) </PEDANTRY> </PEDANTRY> <WARNING> Also be warned that the example for "multichoose" in the Pod is wrong. (I'm reporting that to the module author.) </WARNING> <HUMOR> If you don't need the weighting (frequency) feature, you could just use my $alphbet='aeiou'; my $n=2; my @strings=grep { /[$alphabet]{$n}/ } 'a'x$n .. 'z'x$n; print "@strings"; but it's not very efficient for large values of n unless the alphabet is dense in a..z, nor for alphabets that aren't subsets of Ascii. Boosting $n=6 will run out of memory. Switching to a for loop on the .. (which is optimized ) gets you partial results quickly my $ab="aeiou"; my $n=6; for (q{a}x$n .. q{x}x$n) { next unless /[$ab]{$n}/; print; } but it takes quite a while to scan from auuuuu to eaaaaa, even on a gigahertz clock -- total elapsed time 5.5 minutes! (If you only need to do it once, that's quicker than downloading a module .. but otherwise ..) So I guess having a module to build these makes good sense ... at least until Perl6 lets us run our regexes and parser rules backwards to generate strings. </HUMOR> Have fun in Combinatorics land, Bill not speaking for the firm aka n1vux on use.perl.org _______________________________________________ Boston-pm mailing list [email protected] http://mail.pm.org/mailman/listinfo/boston-pm
