Non-repeating combination of specific count in PHP

Question

This is a particular variation of an oft-repeated question, but try as I might, I couldn't find this exact situation anywhere on Stack Overflow.

Long story short, I want to take an array like this:

$days[0] = 'Monday';
$days[1] = 'Tuesday';
$days[2] = 'Thursday';

($days could contain any number and combination of the five work days of the week.)

And then, given a particular value of $numberOfDays (which, of course, has to be at least 1 and not more than the count of $days), I'd like an array containing all the possible combinations of $days with $numberOfDays number of days.

For example:

$days[0] = 'Monday';
$days[1] = 'Tuesday';
$days[2] = 'Thursday';

$numberOfDays = 2;

$dayCombinations = getDayCombinations($days, $numberOfDays);

Output:

$dayCombinations[0] = array("Monday", "Tuesday");
$dayCombinations[1] = array("Monday", "Thursday");
$dayCombinations[2] = array("Tuesday", "Thursday");

Note that these are combinations, not permutations, so order doesn't matter.

If it helps, I found this function here: It works well, but includes repetitions and is based off of a string instead of an array (that last part is workable, not a big deal, but the repetitions part really messes it up for me).

function sampling($chars, $size, $combinations = array()) {

    # if it's the first iteration, the first set 
    # of combinations is the same as the set of characters
    if (empty($combinations)) {
        $combinations = $chars;
    }

    # we're done if we're at size 1
    if ($size == 1) {
        return $combinations;
    }

    # initialise array to put new values in
    $new_combinations = array();

    # loop through existing combinations and character set to create strings
    foreach ($combinations as $combination) {
        foreach ($chars as $char) {
            $new_combinations[] = $combination . $char;
        }
    }

    # call same function again for the next iteration
    return sampling($chars, $size - 1, $new_combinations);
}

UPDATE: I've tried to wrap the line assigning $new_combinations with a conditional to help; this has had no effect at all, though I'm not sure why. All of the combinations still come through, even those with repetitions.

function sampling($chars, $size, $combinations = array()) {

    # if it's the first iteration, the first set 
    # of combinations is the same as the set of characters
    if (empty($combinations)) {
        $combinations = $chars;
    }

    # we're done if we're at size 1
    if ($size == 1) {
        return $combinations;
    }

    # initialise array to put new values in
    $new_combinations = array();

    # loop through existing combinations and character set to create strings
    foreach ($combinations as $combination) {
        foreach ($chars as $char) {
            if (strpos($combination, $char) === FALSE) {
                echo "Char $char not found in Combination $combination<br>";
                $new_combinations[] = $combination . $char;
            }
        }
    }

    # call same function again for the next iteration
    return sampling($chars, $size - 1, $new_combinations);
}

The output in there returns oddities like:

Char 2 not found in Combination 2
Char 3 not found in Combination 23

And so on.

Thanks for the help!

Alex

what do you mean repetitions? Duplicates right. You could try `array_unique($dayCombinations)` to remove them not sure if it works arrays as the value. Or another way it to use the combination as the key, like `$dayCombinations['Monday-Tuesday'] = array("Monday", "Tuesday");` then they are naturally unique as long as the days are in the same order for the key. — ArtisticPhoenix, Dec 31 '16 at 20:34
Add `if (!in_array($item, $combination))` around the `$new_combinations[]` assignment. — Barmar, Dec 31 '16 at 20:37
Barmar, I'm actually trying that right now. Within the sampling function, $combination and $char are both strings, so I'm trying to use strpos. Not having any luck for some reason though. I'm updating the main post now to reflect it. — Alex Gold, Dec 31 '16 at 20:39
ArtisticPhoneix, by "repetitions," I mean outputs where the same day is listed twice, like "Monday, Monday" - as contrasted with my examples where each combination can only include each day a single time at most. — Alex Gold, Dec 31 '16 at 20:45
oh i was thinking like this `["Monday", "Tuesday"]` and `["Tuesday","Monday"]` — ArtisticPhoenix, Dec 31 '16 at 20:51
That as well :). I was trying to be formal with that and say "combination" instead of "permutation," as ["Monday", "Tuesday"] and ["Tuesday","Monday"] would be examples of permutation instead of combination. — Alex Gold, Dec 31 '16 at 21:03

Barmar · Accepted Answer · 2016-12-31T20:47:25.270

It's basically the same structure, just check if the day is already in the combination before adding it.

function sampling($days, $size, $combinations = array()) {

    # if it's the first iteration, the first set 
    # of combinations is the same as the set of days
    if (empty($combinations)) {
        $combinations = array_map(function($day) { return array($day); }, $days);
    }

    # we're done if we're at size 1
    if ($size == 1) {
        return $combinations;
    }

    # initialise array to put new values in
    $new_combinations = array();

    # loop through existing combinations and character set to create strings
    foreach ($combinations as $combination) {
        foreach ($days as $day) {
            if (!in_array($day, $combination)) {
                $new_combination = $combination;
                $new_combination[] = $day;
                $new_combinations[] = $new_combination;
            }
        }
    }

    # call same function again for the next iteration
    return sampling($days, $size - 1, $new_combinations);
}

DEMO

I love the idea (converting it to arrays to make it easier). Only issue I see is that these are permutations, not combinations (e.g., we get "Monday, Tuesday" as one answer and "Tuesday, Monday" as another). I'll see if I can figure that out in your code, but if you see this, any quick alterations for that? Thanks! — Alex Gold, Dec 31 '16 at 20:58
I was able to fix that part after the call by adding this after, though it would be somewhat nicer and more efficient to do it int he function itself of possible. $daycombinations = sampling($dayslisted,$daysperweek); foreach($daycombinations AS $key => $daycombination) { sort($daycombination); if (in_array($daycombination, $daycombinations)){unset($daycombinations[$key]);} else{$daycombinations[$key] = $daycombination;} } — Alex Gold, Dec 31 '16 at 21:04

Alex Gold · Answer 2 · 2016-12-31T22:20:50.343

Piggybacking off of Barmar's answer, which returned permutations instead of combinations, I just added an additional two lines of code after you call the function to get rid of the unnecessary permutations. There's probably a more efficient way, but for the array sizes I'm looking at it's negligible. See the last two lines below.

function sampling($days, $size, $combinations = array()) {

    # if it's the first iteration, the first set 
    # of combinations is the same as the set of days
    if (empty($combinations)) {
        $combinations = array_map(function($day) { return array($day); }, $days);
    }

    # we're done if we're at size 1
    if ($size == 1) {
        return $combinations;
    }

    # initialise array to put new values in
    $new_combinations = array();

    # loop through existing combinations and character set to create strings
    foreach ($combinations as $combination) {
        foreach ($days as $day) {
            if (!in_array($day, $combination)) {
                $new_combination = $combination;
                $new_combination[] = $day;
                $new_combinations[] = $new_combination;
            }
        }
    }

    # call same function again for the next iteration
    return sampling($days, $size - 1, $new_combinations);
}

$combinations = getDayCombinations($days, $numberOfDays);

for ($round=0;$round<count($combinations);$round++){sort($combinations[$round]);}
    $combinations = array_values(array_map("unserialize", array_unique(array_map("serialize", $combinations))));

Non-repeating combination of specific count in PHP

2 Answers2