Beefy Boxes and Bandwidth Generously Provided by pair Networks
Pathologically Eclectic Rubbish Lister

Re^2: Obtaining terms in an expansion

by pKai (Priest)
on Jan 06, 2006 at 12:52 UTC ( #521464=note: print w/replies, xml ) Need Help??

in reply to Re: Obtaining terms in an expansion
in thread Obtaining terms in an expansion

Actually 2**N is the number of subsets of a set of cardinality N, while the number of permutations of a set of N distinct elements is N! (facultyfactorial).

ivancho used the subset theme quite succesfully in this node above.

Replies are listed 'Best First'.
Re^3: Obtaining terms in an expansion
by DungeonKeeper (Novice) on Jan 06, 2006 at 13:23 UTC
    In a way you are correct, except that it's "factorial" not "faculty" - I used the word permutations a bit too loosely.

    However, the module Math::Combinatorics can still be used to iterate through the 2**N subsets as well as the nCr combinations and the N! permutations.

      Thank you, for pointing me to the "factorial"
      Note to self: Don't transfer mathematical/technical terms from German to English without consulting a dictionary first.

      Also, would you be able to give example code for the subset iteration with Math::Combinatorics?

      If there is an easy way to do so, it has escaped me.

      The closest I saw in the docs was that example to generate:
      "Morse signals: diferent signals of 3 positions using the two symbols - and .".

      Now Morse signals of length 3 are surely one-to-one and onto the subsets of a 3 element set (set elements = pos in signal; element not/contained = dot/dash)

      The given iteration using next_multiset and next_string is like computing 2**n as sumk=0..n nCk

      At least this is not trivial application of the modules methods.

        I guess that's as good as it gets from Math::Combinatorics - doable, but not very natural.

        There are plenty of other iterators out there that give all the subsets, though - List::PowerSet, Data::PowerSet, Algorithm::ChooseSubsets - We just have to convert them to give a bit mask instead - ie:

        use List::PowerSet qw/powerset_lazy/; my @set = (0) x $N; my @C = (1) x 2**$N; my $M = 0; my $ps_itr = powerset_lazy(0 .. $N-1); while (my $ref_set = $ps_itr->()) { $_ = 1 for local @set[@$ref_set]; $C[ $M ] *= $arr->[ $_ ][ $set[$_] ] for 0 .. $N-1; $M++; }
        The 2**N doesn't need to be computed anyway. next_multiset() will just keep returning each possible set until all have been returned, at which point it returns undef().

        Everything but the troll

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://521464]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others drinking their drinks and smoking their pipes about the Monastery: (5)
As of 2021-05-11 14:50 GMT
Find Nodes?
    Voting Booth?
    Perl 7 will be out ...

    Results (117 votes). Check out past polls.