Arrangements with repetition implementation in PHP

Created:08 Oct 2017 14:29:33 , in  Maths

This article, and in particular PHP code it contains, is an outcome of my lack of patience with regards to making arrangements with repetition of finite set items.

Recently, while solving a Probability problem, which eventually led to an infinite series, I reached a step which involved finding all the 5-arrangmements of a 5-element set. The Number of such arrangements is given by count of items in the set raised to the power given by the number of items in a single arrangement. In my case, 5 items in the set raised to the fifth power would yield 3125 arrangements.

If a set looks like {a,b,c,d,e}, one of the required arrangements would be (b,c,d,a,e), another (e,d,a,a,a). Just as name of the operation mentions, repeated elements drawn out from the set are allowed in the arrangement. In simple terms, you put back in what you have just drawn out before drawing out again.

It is worth noting here, that n-arrangements with repetition of a finite set have a special name. They are called n-tuples.

Even though, finding n-tuples may be fun for a while, I also found something else when doing that, namely a limit to my patience. I have enough of it to put together 2-tuples of 2-element set only. Incidentally, being able to find these four 2-tuples successfully also gives sufficient insight to write a function which builds large sets of n-arrangements in the blink of an eye. So I did.

Finding n-tuples with PHP

Below is a listing of a class SWWWCombinatorics which consists of one static method. It is called nA. The method accepts a list of items, optionally also a non-negative integer n, and returns an array of n-tuples. See examples section below for details.

SWWWCombinatorics::nA is a recursive function. It relies upon a nested loop to do its job, which also means quadratic time complexity. I've left my comments in place to give you better idea how the function works.

/*
  Class: SWWWCombinatorics 
  Description: Combinatorics related functions
  Author: Sylwester Wojnowski
  WWW: wojnowski.net.pl

  Methods:
    nA($A,$n) - public static - find n-arrangements of m-set
      parameters:
        $A - array - representation of m-set
        $n - int - non-negative integer which describes what n-tuples to return
      return - array - array of n-arrangements    
*/
class SWWWCombinatorics{
  
  public static function nA($A,$n = null){
    $c = count($A);
    // make sure n is in the acceptable range
    $n = $n !== null && $n >= 0 && $n <= $c ? $n : $c;
    
    // we are at the tree top node
    if($n === 0){ return array(array());}
    
    // get to the tree top node
    $p = SWWWCombinatorics::nP($A,$n - 1); // 
    
    // we have n-tuples we need now
    if($n < 1){ return $p;}
    
    // extend already found tuples
    $P = array(); 
    for($j = 0; $j < count($p); $j++){
      for($i = 0; $i < $c; $i++){
         $k = $p[$j]; 
         $k[] = $A[$i];  
         $P[] = $k; 
      }
    }
    
    // return brand new set of arrangements
    return $P;
  }
}  

SWWWCombinatorics::nA uses array indices to perform its task. Also, it is not aware of sort of objects it handles. They can be strings, numbers, objects or anything else one can store in an array.

Use examples

Here are some use examples.

Finding 2-tuples of 2-element set {'a','b'}:

$A = array('a','b');
$T = SWWWCombinatorics::nA($A);
/*
$T = array(
  array('a','a'),
  array('a','b'),
  array('b','a'),
  array('b','b')
);
*/

Finding 1-tuples of 3-set {'a','b','c'}:

$T = SWWWCombinatorics::nA($A,1);
/*
$T = array(
  array('a'),
  array('b'),
  array('c')
);
*/ 

Normally, type of tuple the function returns is determined by count of items in the array passed to it as the first argument. The count of 3 results in 3-tuples.

But, SWWW::combinatorics::nA is passed a second argument in this example also, a non-negative number, which tells it to return 1-tuples rather than 3-tuples.

Finally, something similar to what I needed in the first place, that is 5-tuples of 5-set:

$A = array('a','b','c','d','e');
$T = SWWWCombinatorics::nA($A);
/*
$T = array(    
  array('a','a','a','a','a'), // 0
  array('a','a','a','a','b'), // 1
  array('a','a','a','a','b'), // 2
  .
  .
  .
  array('e','e','e','e','c'), // 3122
  array('e','e','e','e','d'), // 3123
  array('e','e','e','e','e')  // 3124
);
*/

I guess the examples above give sufficient insight into what SWWWCombinatorics::nA is good at.

Final thoughts

Due to a tree structure often hiding in the background of them, arrangements, combinations or counting related problems similar to the one described in this article can often be solved and coded quick and effectively using recursive programming techniques. Or to put it simply, frequently these problems are based on a underlying repetitive pattern, which can be inferred by taking a closer look at a very small subset of the initial results.

So much for finding 3125 5-tuples of 5-element set by hand.

This post was updated on 08 Oct 2017 17:21:59

Tags:  combinatorics ,  php ,  recursion