Math::...atorics(3pm)

💖 Math::Combinatorics 💖

okay bestie, welcome to Math::Combinatorics (that's the Math::Combinatorics(3pm) page, straight out of the User Contributed Perl Documentation section, iykyk) ✨

This is part 1 of the whole thing, so buckle up, hydrate, and let's get into it 🫶

---

✨ NAME ✨

Math::Combinatorics — do combinations and permutations on lists, fr fr 💅

---

🦋 SYNOPSIS 🦋

so you can use this as an object oriented API:

use Math::Combinatorics;

my @n = qw(a b c);
my $combinat = Math::Combinatorics->new(count => 2,
                                        data => [@n],
                                       );

print "combinations of 2 from: ".join(" ",@n)."\n";
print "------------------------".("--" x scalar(@n))."\n";
while(my @combo = $combinat->next_combination){
  print join(' ', @combo)."\n";
}

print "\n";

print "permutations of 3 from: ".join(" ",@n)."\n";
print "------------------------".("--" x scalar(@n))."\n";
while(my @permu = $combinat->next_permutation){
  print join(' ', @permu)."\n";
}

output:

orrrr it's available through the exported functions permute, combine, and factorial, which is giving shortcut energy ✨

use Math::Combinatorics;

my @n = qw(a b c);
print "combinations of 2 from: ".join(" ",@n)."\n";
print "------------------------".("--" x scalar(@n))."\n";
print join("\n", map { join " ", @$_ } combine(2,@n)),"\n";
print "\n";
print "permutations of 3 from: ".join(" ",@n)."\n";
print "------------------------".("--" x scalar(@n))."\n";
print join("\n", map { join " ", @$_ } permute(@n)),"\n";

Output:

combinations of 2 from: a b c
------------------------------
a b
a c
b c

permutations of 3 from: a b c
------------------------------
a b c
a c b
b a c
b c a
c a b
c b a

both flavours of call give you the same output — but the object-oriented approach consumes much less memory for large sets, and that is the entire tea ☕💅

---

🌸 DESCRIPTION 🌸

okay so, Combinatorics is the branch of mathematics studying the enumeration, combination, and permutation of sets of elements, plus the mathematical relations that characterize their properties. as a jumping off point, go look at:

http://mathworld.wolfram.com/Combinatorics.html

This module gives you a pure-perl implementation of nCk, nCRk, nPk, nPRk, !n and n! — that's combination, multiset, permutation, string, derangement, and factorial, respectively, no cap 🧚

and both the functional and object-oriented usages let you solve problems like these:

combine - nCk

http://mathworld.wolfram.com/Combination.html

"Fun questions to ask the pizza parlor wait staff: how many possible combinations of 2 toppings can I get on my pizza?".

derange - !n

http://mathworld.wolfram.com/Derangement.html

"A derangement of n ordered objects, denoted !n, is a permutation in which none of the objects appear in their "natural" (i.e., ordered) place."

permute - nPk

http://mathworld.wolfram.com/Permutation.html

"Master Mind Game: ways to arrange pieces of different colors in a certain number of positions, without repetition of a color".

Object-oriented usage additionally allows solving these problems by calling "new()" with a frequency vector, which is honestly such a serve 👑

string - nPRk

http://mathworld.wolfram.com/String.html

"Morse signals: different signals of 3 positions using the two symbols - and .".

$o = Math::Combinatorics->new( count=>3 , data=>[qw(. -)] , frequency=>[3,3] );
while ( my @x = $o->next_multiset ) {
  my $p = Math::Combinatorics->new( data=>\@x , frequency=>[map{1} @x] );
  while ( my @y = $p->next_string ) {
    #do something
  }
}

multiset/multichoose - nCRk

http://mathworld.wolfram.com/Multiset.html

"ways to extract 3 balls at once of a bag with 3 black and 3 white balls".

$o = Math::Combinatorics->new( count=>3 , data=>[qw(white black)] , frequency=>[3,3] );
while ( my @x = $o->next_multiset ) {
  #do something
}

💜 EXPORT 💜

the following export tags will bring a single method into the caller's namespace. no symbols are exported by default — so don't come for me if nothing shows up, bestie. see the pod documentation below for method descriptions 🎀

combine
derange
multiset
permute
string
factorial

---

👑 AUTHOR 👑

Allen Day <allenday@ucla.edu>, with algorithmic contributions from Christopher Eltschka and Tye.

Copyright (c) 2004-2005 Allen Day. All rights reserved. This program is free software; you can redistribute it and/or modify it under the same terms as Perl itself.

---

🫶 ACKNOWLEDGEMENTS 🫶

a sincere thanks to everyone for helping to make this a better module 💖 after initial development I've only had time to accept patches and improvements. Math::Combinatorics continues to be developed and improved by the community. contributors of note include:

• For adding new features: Carlos Rica, David Coppit, Carlos Segre, Lyon Lemmens
• For bug reports: Ying Yang, Joerg Beyer, Marc Logghe, Yunheng Wang, Torsten Seemann, Gerrit Haase, Joern Behre, Lyon Lemmens, Federico Lucifredi

---

💀 BUGS / TODO 💀

report them to the author, bestie.

• Need more extensive unit tests.
  • tests for new()'s frequency argument
• A known bug (more of a missing feature, actually) does not allow parameterization of k for nPk in permute(). it is assumed k == n. L</permute()> for details. You can work around this by making calls to both L</permute()> and L</combine()>
• Lots of really interesting stuff from Mathworld.Wolfram.com. MathWorld rocks! Expect to see implementation of more concepts from their site, e.g.:

http://mathworld.wolfram.com/BellNumber.html
http://mathworld.wolfram.com/StirlingNumberoftheSecondKind.html
http://mathworld.wolfram.com/Word.html

• Other combinatorics stuff

http://en.wikipedia.org/wiki/Catalan_number
http://en.wikipedia.org/wiki/Stirling_number

---

🌈 SEE ALSO 🌈

• Set::Scalar
• Set::Bag
• String::Combination (alas misnamed, it actually returns permutations on a string).
• ``` http://perlmonks.thepen.com/29374.html

- ```
http://groups.google.com/groups?selm=38568F79.13680B86%40physik.tu-muenchen.de&output=gplain

---

⭐ EXPORTED FUNCTIONS ⭐

🍓 combine() 🍓

• Usage — my @combinations = combine($k,@n);
• Function — implements nCk (n choose k), or n!/(k!*(n-k!)). returns all unique unordered combinations of k items from set n. items in n are assumed to be character data, and are copied into the return data structure (see "Returns" below).
• Example —

my @n = qw(a b c);
my @c = combine(2,@n);
print join "\n", map { join " ", @$_ } @c;
# prints:
# b c
# a c
# a b

• Returns — a list of arrays, where each array contains a unique combination of k items from n
• Args — a list of items to be combined
• Notes — data is internally assumed to be alphanumeric. this is necessary to efficiently generate combinations of large sets. if you need combinations of non-alphanumeric data, or on data C<sort {$a cmp $b}> would not be appropriate, use the object-oriented API. See L</new()> and the compare option.

Identical items are assumed to be non-unique. That is, calling C<combine(1,'a','a') yields two sets: {a}, and {a}. See L</next_multiset()> if this is not the desired behavior.

🧚 derange() 🧚

• Usage — my @deranges = derange(@n);
• Function — implements !n, a derangement of n items in which none of the items appear in their originally ordered place.
• Example —

my @n = qw(a b c);
my @d = derange(@n);
print join "\n", map { join " ", @$_ } @d;
# prints:
# a c b
# b a c
# b c a
# c a b
# c b a

• Returns — a list of arrays, where each array contains a derangement of k items from n (where k == n).
• Args — a list of items to be deranged.
• Note — k should really be parameterizable. this will happen in a later version of the module. send me a patch to make that version come out sooner.
• Notes — data is internally assumed to be alphanumeric. this is necessary to efficiently generate combinations of large sets. if you need combinations of non-alphanumeric data, or on data C<sort {$a cmp $b}> would not be appropriate, use the object-oriented API. See L</new()>, and the compare option.

💅 next_derangement() 💅

• Usage — my @derangement = $c->next_derangement();
• Function — get derangements for @data.
• Returns — returns a permutation of items from @data (see L</new()>), where none of the items appear in their natural order. repeated calls retrieve all unique derangements of @data elements. a returned empty list signifies all derangements have been iterated.
• Args — none.

✨ factorial() ✨

• Usage — my $f = factorial(4); #returns 24, or 4*3*2*1
• Function — calculates n! (n factorial).
• Returns — undef if n is non-integer or n < 0
• Args — a positive, non-zero integer
• Note — this function is used internally by combine() and permute()

🎀 permute() 🎀

• Usage — my @permutations = permute(@n);
• Function — implements nPk (n permute k) (where k == n), or n!/(n-k)! returns all unique permutations of k items from set n (where n == k, see "Note" below). items in n are assumed to be character data, and are copied into the return data structure.
• Example —

my @n = qw(a b c);
my @p = permute(@n);
print join "\n", map { join " ", @$_ } @p;
# prints:
# b a c
# b c a
# c b a
# c a b
# a c b
# a b c

• Returns — a list of arrays, where each array contains a permutation of k items from n (where k == n).
• Args — a list of items to be permuted.
• Note — k should really be parameterizable. this will happen in a later version of the module. send me a patch to make that version come out sooner.
• Notes — data is internally assumed to be alphanumeric. this is necessary to efficiently generate combinations of large sets. if you need combinations of non-alphanumeric data, or on data C<sort {$a cmp $b}> would not be appropriate, use the object-oriented API. See L</new()>, and the compare option.

Identical items are assumed to be non-unique. That is, calling C<permute('a','a') yields two sets: {a,a}, and {a,a}. See L</next_string()> if this is not the desired behavior.

💖 CONSTRUCTOR 💖

okay bestie, this is where you build the whole thing. new() is literally the main character constructor. ✨

✨ new() ✨

Usage   : my $c = Math::Combinatorics->new( count => 2,       #treated as int
                                            data => [1,2,3,4] #arrayref or anonymous array
                                          );
Function: build a new Math::Combinatorics object.
Returns : a Math::Combinatorics object
Args    : count     - required for combinatoric functions/methods.  number of elements to be
                      present in returned set(s).
          data      - required for combinatoric B<AND> permutagenic functions/methods.  this is the
                      set elements are chosen from.  B<NOTE>: this array is modified in place; make
                      a copy of your array if the order matters in the caller's space.
          frequency - optional vector of data frequencies.  must be the same length as the B<data>
                      constructor argument.  These two constructor calls here are equivalent:

                        $a = 'a';
                        $b = 'b';

                        Math::Combinatorics->new( count=>2, data=>[\$a,\$a,\$a,\$a,\$a,\$b,\$b] );
                        Math::Combinatorics->new( count=>2, data=>[\$a,\$b], frequency=>[5,2] );

                      so why use this?  sometimes it's useful to have multiple identical entities in
                      a set (in set theory jargon, this is called a "bag", See L<Set::Bag>).
          compare   - optional subroutine reference used in sorting elements of the set.  examples:

                      #appropriate for character elements
                      compare => sub { $_[0] cmp $_[1] }
                      #appropriate for numeric elements
                      compare => sub { $_[0] <=> $_[1] }
                      #appropriate for object elements, perhaps
                      compare => sub { $_[0]->value <=> $_[1]->value }

                    The default sort mechanism is based on references, and cannot be predicted.
                    Improvements for a more flexible compare() mechanism are most welcome.

so like, let's decode this for the group chat: 💅

• count — required for combinatoric functions/methods. it's the number of elements that will be present in returned set(s). treated as int, no cap. 👑
• data — required for combinatoric AND permutagenic functions/methods. this is the set elements are chosen from. NOTE: this array is modified in place; make a copy of your array if the order matters in the caller's space. seriously, don't skip that copy bestie. 😭
• frequency — optional vector of data frequencies. must be the same length as the data constructor argument. these two constructor calls here are equivalent:

$a = 'a';
$b = 'b';

Math::Combinatorics->new( count=>2, data=>[\$a,\$a,\$a,\$a,\$a,\$b,\$b] );
Math::Combinatorics->new( count=>2, data=>[\$a,\$b], frequency=>[5,2] );

so why use this? sometimes it's useful to have multiple identical entities in a set (in set theory jargon, this is called a "bag", See L<Set::Bag>). 👜✨

• compare — optional subroutine reference used in sorting elements of the set. examples:

#appropriate for character elements
compare => sub { $_[0] cmp $_[1] }
#appropriate for numeric elements
compare => sub { $_[0] <=> $_[1] }
#appropriate for object elements, perhaps
compare => sub { $_[0]->value <=> $_[1]->value }

The default sort mechanism is based on references, and cannot be predicted. Improvements for a more flexible compare() mechanism are most welcome. (so if you got ideas, the author wants them, fr fr.) 🫶

---

🦋 OBJECT METHODS 🦋

now the fun part: iterating through all the combos, multisets, permutations and strings. ✨

next_combination()

Usage   : my @combo = $c->next_combination();
Function: get combinations of size $count from @data.
Returns : returns a combination of $count items from @data (see L</new()>).
          repeated calls retrieve all unique combinations of $count elements.
          a returned empty list signifies all combinations have been iterated.
Note    : this method may only be used if a B<frequency> argument is B<NOT>
          given to L</new()>, otherwise use L</next_multiset()>.
Args    : none.

call this in a loop, and when you get an empty list, that's the end, periodt. but only if you didn't pass frequency to L</new()> — if you did, go use L</next_multiset()> instead. okay? 💖

next_multiset()

Usage   : my @multiset = $c->next_multiset();
Function: get multisets for @data.
Returns : returns a multiset of items from @data (see L</new()>).
          a multiset is a special type of combination where the set from which
          combinations are drawn contains items that are indistinguishable.  use
          L</next_multiset()> when a B<frequency> argument is passed to L</new()>.
          repeated calls retrieve all unique multisets of @data elements.  a
          returned empty list signifies all multisets have been iterated.
Note    : this method may only be used if a B<frequency> argument is given to
          L</new()>, otherwise use L</next_combination()>.
Args    : none.

this one's for when your set has clones, basically. if you passed frequency to L</new()>, you're in the right place. otherwise, L</next_combination()> is your girl. 🧚

next_permutation()

Usage   : my @permu = $c->next_permutation();
Function: get permutations of elements in @data.
Returns : returns a permutation of items from @data (see L</new()>).
          repeated calls retrieve all unique permutations of @data elements.
          a returned empty list signifies all permutations have been iterated.
Note    : this method may only be used if a B<frequency> argument is B<NOT>
          given to L</new()>, otherwise use L</next_string()>.
Args    : none.

order matters here, bestie. unique permutations only. empty list means done. but if you gave frequency to L</new()>, don't use this, use L</next_string()>. 🔥

next_string()

Usage   : my @string = $c->next_string();
Function: get strings for @data.
Returns : returns a multiset of items from @data (see L</new()>).
          a multiset is a special type of permutation where the set from which
          combinations are drawn contains items that are indistinguishable.  use
          L</next_permutation()> when a B<frequency> argument is passed to L</new()>.
          repeated calls retrieve all unique multisets of @data elements.  a
          returned empty list signifies all strings have been iterated.
Note    : this method may only be used if a B<frequency> argument is given to
          L</new()>, otherwise use L</next_permutation()>.
Args    : none.

so "strings" here are like permutations but with indistinguishable items, iykyk. only if you gave frequency to L</new()>. otherwise use L</next_permutation()>. 🌸

---

🔧 INTERNAL FUNCTIONS AND METHODS 🔧

these are the backstage helpers. not your main character, but they keep the show running. 💜

sum()

Usage   : my $sum = sum(1,2,3); # returns 6
Function: sums a list of integers.  non-integer list elements are ignored
Returns : sum of integer items in arguments passed in
Args    : a list of integers
Note    : this function is used internally by combine()

non-integers are ignored, so don't come for it with floats. it's used internally by combine(). ✨

compare()

Usage   : $obj->compare()
Function: internal, undocumented.  holds a comparison coderef.
Returns : value of compare (a coderef)

count()

Usage   : $obj->count()
Function: internal, undocumented.  holds the "k" in nCk or nPk.
Returns : value of count (an int)

data()

Usage   : $obj->data()
Function: internal, undocumented.  holds the set "n" in nCk or nPk.
Returns : value of data (an arrayref)

swap()

internal, undocumented.

reverse()

internal, undocumented.

rotate()

internal, undocumented.

upper_bound()

internal, undocumented.

lower_bound()

internal, undocumented.

_permutation_cursor()

Usage   : $obj->_permutation_cursor()
Function: internal method.  cursor on permutation iterator order.
Returns : value of _permutation_cursor (an arrayref)
Args    : none

---

and that's the tea, bestie. this page was served by perl v5.36.0 on 2022-12-04, under the Math::...atorics(3pm) banner. now go slay some combinations. 💖✨🎀