How to calculate valid number of combinations, given a two array list? [duplicate]

Question

This question already has answers here:

How to precalculate valid number of combinations instead of using while loop? (2 answers)

Closed 8 years ago.

Given List of datacenters which are dc1, dc2, dc3 and list of machines h1, h2, h3, h4 as mentioned below -

Datacenters = dc1, dc2, dc3
Machines = h1, h2, h3, h4

I want to generate below combinations only for the above list -

a)  {dc1=h1, dc3=h3, dc2=h2}

b)  {dc1=h2, dc3=h4, dc2=h3}

c)  {dc1=h3, dc3=h1, dc2=h4}

d)  {dc1=h4, dc3=h2, dc2=h1}

In general, Each datacenter in the each pass should get alternate machines/hosts. They should not get same machines. For example in a as shown above - dc1 gets h1, dc2 gets h2, dc3 gets h3 so all the machines are different for each datacenters. And in the second pass as shown in b - now dc1 gets h2 (becuase dc1 already got h1 in the first pass), dc2 got h3 (bcoz dc2 already got h2 in the first pass), and dc3 got h4(bcoz dc3 already got h3 in the first pass) and etc etc.

And one more example - if I have only three hosts, then below combination I am supposed to get only -

Datacenters = dc1, dc2, dc3
Machines = h1, h2, h3    

{dc1=h1, dc3=h3, dc2=h2}
{dc1=h2, dc3=h1, dc2=h3}
{dc1=h3, dc3=h2, dc2=h1}

So I came up with the below code which works perfectly fine without any issue -

public class DataCenterMapping {

    public static void main(String[] args) {

    DatacenterMachineMapping dcm = new DatacenterMachineMapping(Arrays.asList("dc1", "dc2", "dc3"), Arrays.asList(
        "h1", "h2", "h3", "h4"));

        // is there any way to precalculate number of combinations 
        // instead of using while loop here?
        while (true) {
            Map<String, String> coloHost = dcm.getDatacenterMachineMapping();
            System.out.println(coloHost);
            for (Map.Entry<String, String> entry : coloHost.entrySet()) {

            }
        }
    }
}

Below is my class which does all the work -

class DatacenterMachineMapping {

    private boolean firstCall = true;
    private int hostListIndex = 0;
    private List<String> datacenterList, hostList;
    private Map<String, Set<String>> dataCenterHostsMap = new HashMap<String, Set<String>>();

    public DatacenterMachineMapping(List<String> datacenterList, List<String> hostList) {
    this.datacenterList = datacenterList;
    this.hostList = hostList;
    }

    public Map<String, String> getDatacenterMachineMapping() {
    Map<String, String> datacenterMachineMapping = new HashMap<String, String>();
    if (!firstCall) {
        if (hostListIndex <= 0) {
        hostListIndex = hostList.size();
        }
        hostListIndex--;
    } else {
        firstCall = false;
    }
    for (String datacenter : datacenterList) {
        if (hostListIndex == hostList.size()) {
        hostListIndex = 0;
        }
        if (addDataCenterHost(datacenter, hostList.get(hostListIndex))) {
        datacenterMachineMapping.put(datacenter, hostList.get(hostListIndex++));
        }
    }
    hostListIndex--;
    return datacenterMachineMapping;
    }

    private boolean addDataCenterHost(String datacenter, String host) {
    Set<String> dataCenterHostSet = dataCenterHostsMap.get(datacenter);
    if (dataCenterHostSet == null) {
        dataCenterHostSet = new HashSet<String>();
        dataCenterHostsMap.put(datacenter, dataCenterHostSet);
    }
    return dataCenterHostSet.add(host);
    }
}

Problem Statement:-

The only problem is I have a while loop which will keep on running always which is not what I want. I am trying to precalculate number of valid combinations before hand then I can use the for loop to iterate that.

Is there any way I can precalculate the number of valid combinations instead of using while loop in my above code?

Answer 1

I'm assuming there are more machines than there are datacenters. In which case your answer is:

hostList.size();

You can always generate the following sets:

Set 1: (1,1), (2,2), ... (n,n)
Set 2: (1,2), (2,3), ... (n,n+1%m)
...
Set m: (1,m), (2,m+1 % m), ... (n,(n + m-1) % m)

Note that:

(m + 1) % m   = 1
(n + m-1) % m = n-1

So it is really:

Set 1: (1,1), (2,2), ... (n,n)
Set 2: (1,2), (2,3), ... (n,n+1%m)
...
Set m: (1,m), (2,1), ... (n,n-1)

In fact...your code can just be:

public List<Map<String, String>> createMappings(List<String> datacenters, List<String> hosts) {
    List<Map<String, String>> result = new ArrayList<Map<String, String>>();
    for(int i = 0; i < hosts.size(); i++) {
        Map<String, String> row = new HashMap<String,String>();
        for(int j = 0; j < datacenters.size(); j++) {
            String datacenter = datacenters.get(j);
            int hostIndex = (j + i) % hosts.size();
            String host = hosts.get(hostIndex);
            row.put(datacenter, host);
        }
        result.add(row);
    }
    return result;
}

Answer 2

number of valid combinations = Datacenters * machines;