I recently had a friend tell me that I was good at naming things. But I’m tired of that. I want to be good at something else, or at least be presented with some options from which I can just choose and spend my energy elsewhere. “There’s an algorithm for that!” I wish I hadn’t written that for you to see, but I’ve been pretending that my backspace key is broken this week. My job is pretty upset about that one, and now so I am I.

Let’s say we have some possible first, middle, and last names (this happens to be in PHP, but could, of course, be applied elsewhere):

$keyValues = array(
    'firstName' => array('Jane', 'Peter', 'Maximilian'),
    'middleName' => array('Bradley', 'Hammerstein'),
    'lastName' => array('Russell', 'Karinen', 'Umphrey', 'Boors')
);

So, we pass that array to…

function getUniqueCombinations(array $keyValues)
{
    if (count($keyValues) == 0) {
        /* if we have no options, a blank array is reasonable */
        return array();
    }
    $iterators = array();
    $total = 1;
    $keys = array_keys($keyValues);
    /* calculate the total number of possible combinations,
       which is the product of possible values: 
       count($keyValues[firstKey]) * count($keyValues[secondKey]) * ...
       and we also set up our value iterators */
    foreach ($keyValues as $key => $values) {
        $iterators[$key] = 0;
        $total = $total * count($values);
    }
    $i = 0;
    $combinations = array();
    while ($i < $total) {
        $combination = array();
        foreach ($keyValues as $key => $values) {
            $combination[$key] = $values[$iterators[$key]];
        }
        $combinations[] = $combination;
        foreach ($keys as $key) {
            if ($iterators[$key] + 1 >= count($keyValues[$key])) {
                /* this means we need to increment the next key 
                   iterator and reset this one to 0 */
                $iterators[$key] = 0;
                continue;
            } else {
                /* we're moving on to the next one for this key */            
                $iterators[$key]++;
                break;
            }
        }
        $i++;
    }
    return $combinations;
}

The above should give us all the possible first, middle, and last name combinations possible. A namer’s tool:

Array
(
    [0] => Array
        (
            [firstName] => Jane
            [middleName] => Bradley
            [lastName] => Russell
        )

    [1] => Array
        (
            [firstName] => Peter
            [middleName] => Bradley
            [lastName] => Russell
        )

    [2] => Array
        (
            [firstName] => Maximilian
            [middleName] => Bradley
            [lastName] => Russell
        )

    [3] => Array
        (
            [firstName] => Jane
            [middleName] => Hammerstein
            [lastName] => Russell
        )

    [4] => Array
        (
            [firstName] => Peter
            [middleName] => Hammerstein
            [lastName] => Russell
        )

    [5] => Array
        (
            [firstName] => Maximilian
            [middleName] => Hammerstein
            [lastName] => Russell
        )

    [6] => Array
        (
            [firstName] => Jane
            [middleName] => Bradley
            [lastName] => Karinen
        )

    [7] => Array
        (
            [firstName] => Peter
            [middleName] => Bradley
            [lastName] => Karinen
        )

    [8] => Array
        (
            [firstName] => Maximilian
            [middleName] => Bradley
            [lastName] => Karinen
        )

    [9] => Array
        (
            [firstName] => Jane
            [middleName] => Hammerstein
            [lastName] => Karinen
        )

    [10] => Array
        (
            [firstName] => Peter
            [middleName] => Hammerstein
            [lastName] => Karinen
        )

    [11] => Array
        (
            [firstName] => Maximilian
            [middleName] => Hammerstein
            [lastName] => Karinen
        )

    [12] => Array
        (
            [firstName] => Jane
            [middleName] => Bradley
            [lastName] => Umphrey
        )

    [13] => Array
        (
            [firstName] => Peter
            [middleName] => Bradley
            [lastName] => Umphrey
        )

    [14] => Array
        (
            [firstName] => Maximilian
            [middleName] => Bradley
            [lastName] => Umphrey
        )

    [15] => Array
        (
            [firstName] => Jane
            [middleName] => Hammerstein
            [lastName] => Umphrey
        )

    [16] => Array
        (
            [firstName] => Peter
            [middleName] => Hammerstein
            [lastName] => Umphrey
        )

    [17] => Array
        (
            [firstName] => Maximilian
            [middleName] => Hammerstein
            [lastName] => Umphrey
        )

    [18] => Array
        (
            [firstName] => Jane
            [middleName] => Bradley
            [lastName] => Boors
        )

    [19] => Array
        (
            [firstName] => Peter
            [middleName] => Bradley
            [lastName] => Boors
        )

    [20] => Array
        (
            [firstName] => Maximilian
            [middleName] => Bradley
            [lastName] => Boors
        )

    [21] => Array
        (
            [firstName] => Jane
            [middleName] => Hammerstein
            [lastName] => Boors
        )

    [22] => Array
        (
            [firstName] => Peter
            [middleName] => Hammerstein
            [lastName] => Boors
        )

    [23] => Array
        (
            [firstName] => Maximilian
            [middleName] => Hammerstein
            [lastName] => Boors
        )
)

Any improvements? I tried to spend a little time trying to figure out the actual complexity tonight, but kept getting distracted by my inability to concentrate. Maybe someone else can do that for me since I’m not exactly a pure CS guy.

Tagged with:
 

11 Responses to PHP Unique Combinations

  1. Chris says:

    This is called the Cartesian Product in set theory: http://en.wikipedia.org/wiki/Cartesian_product

    Another way to do it, if you wanted to be non generic about it, is just to foreach() the shit out of it:

    $keyValues = array(
        'firstName' => array('Jane', 'Peter', 'Maximilian'),
        'middleName' => array('Bradley', 'Hammerstein'),
        'lastName' => array('Russell', 'Karinen', 'Umphrey', 'Boors')
    );
    
    $allNames = array();
    foreach($keyValues['firstName'] as $firstName) {
        foreach($keyValues['middleName'] as $middleName) {
            foreach($keyValues['lastName'] as $lastName) {
                $allNames[] = array('firstName' => $firstName, 'middleName' => $middleName, 'lastName' => $lastName);
            }
        }
    }
    
    var_dump($allNames);
    

    You could also replace those foreach’s with recursion given an array of keys to do the same thing in a pretty short way I think.

    • Patrick says:

      Nice, thanks man. A quick and clean alternative for sure. I was trying to stay away from recursion if possible, as the complexity could get pretty crazy pretty quickly, so it was at least partially a proof-of-concept in trying to steer clear of recursion with an indeterminate number of set keys and set values for each key, etc. Oh, and thanks for the Cartesian Product info. I was battling with the title of this post, and it would’ve been so easy to include that in it :) .

  2. Pete Karinen says:

    was Zach the one who told you that you were good at naming things because you came with “Phoebe” as a potential daughter name for him?

  3. Pete Karinen says:

    why do you moderate comments? i tired of awaiting.

  4. Pete Karinen says:

    what’s up, bud? things good?

  5. Pete Karinen says:

    is this why you moderate comments?

  6. Pete Karinen says:

    because of shit like this?

  7. Pete Karinen says:

    just got this message:

    You are posting comments too quickly. Slow down.

  8. Pete Karinen says:

    i can read between the lines there.

Leave a Reply

Your email address will not be published. Required fields are marked *

*

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>