Weekly algorithmic problem 006: Lottery combination

Question:

There are three teams, each with two players.
team1:A,B;
team2:C,D;
team3:E,F;

Now there is one person in each team to form a team to explore. Please list all the ways to form a team.

Train of thought:

This is a combination problem. If you choose one person in each team, there should be 222 = 8 combinations.
If the solution is violent, it is a three-level nesting of loops. But if the problem is expanded to 10 teams, each team has 10 people, it can not be solved violently, at least the code is not scalable.

There is a way of thinking as follows:

Circulate all teams
For the first time, two players, A and B, were taken out and saved.
For the second time, two C and D players were taken out and crossed with the remaining players in the previous round. Four combinations of AC, AD, BC and BD were obtained and saved.
For the third time, two players of E and F were taken out and combined with the results of the previous round. ACE, ACF, ADE, ADF, BCE, BCF, BDE and BDF were obtained.
And so on.

Each cycle combines the players of the previous round with those of the previous round until all the combinations have been traversed.

Answer:

php

<?php
function getCombinations($arrays) {
    $result = array(array());
    foreach ($arrays as $property => $property_values) {
        $tmp = array();
        foreach ($result as $result_item) {
            foreach ($property_values as $property_value) {
                $tmp[] = array_merge($result_item, array($property => $property_value));
            }
        }
        $result = $tmp;
    }
    return $result;
}

$combinations = getCombinations(
    array(
        'item1' => array('A', 'B'),
        'item2' => array('C', 'D'),
        'item3' => array('E', 'F'),
    )
);
$rs = $combinations;
print_r($rs);

Output:

Array
(
    [0] => Array
        (
            [item1] => A
            [item2] => C
            [item3] => E
        )

    [1] => Array
        (
            [item1] => A
            [item2] => C
            [item3] => F
        )

    [2] => Array
        (
            [item1] => A
            [item2] => D
            [item3] => E
        )

    [3] => Array
        (
            [item1] => A
            [item2] => D
            [item3] => F
        )

    [4] => Array
        (
            [item1] => B
            [item2] => C
            [item3] => E
        )

    [5] => Array
        (
            [item1] => B
            [item2] => C
            [item3] => F
        )

    [6] => Array
        (
            [item1] => B
            [item2] => D
            [item3] => E
        )

    [7] => Array
        (
            [item1] => B
            [item2] => D
            [item3] => F
        )

)

golang:

package main

import "fmt"

func main() {
    // Three sets of data, one for each group, the total number should be 2*2*2
    d := make(map[string][]string)
    d["item1"] = []string{"A", "B"}
    d["item2"] = []string{"C", "D"}
    d["item3"] = []string{"E", "F"}

    rs := getCombinations(d)
    fmt.Println(rs)
}

// Get the Combination List
func getCombinations(data map[string][]string) [][]map[string]string {
    result := make([][]map[string]string, 1)
    for property, propertyValues := range data {
        tmp := make([][]map[string]string, 0)
        for _, resultItem := range result {
            for _, propertyValue := range propertyValues {
                tmp = append(tmp, append(resultItem, map[string]string{property: propertyValue}))
            }
        }
        result = tmp
    }
    return result
}

Output: (slightly adjusted format)

[[map[item1:A] map[item2:C] map[item3:E]]
[map[item1:A] map[item2:C] map[item3:F]] 
[map[item1:A] map[item2:D] map[item3:E]] 
[map[item1:A] map[item2:D] map[item3:F]] 
[map[item1:B] map[item2:C] map[item3:E]] 
[map[item1:B] map[item2:C] map[item3:F]]
[map[item1:B] map[item2:D] map[item3:E]]
[map[item1:B] map[item2:D] map[item3:F]]]

Tags: Go PHP

Posted on Fri, 11 Oct 2019 12:53:52 -0700 by jsims