How to precalculate valid number of combinations instead of using while loop?

Question

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 -

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}

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 -

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 avoid while loop here?
        while (true) {
            Map<String, String> coloHost = dcm.getDatacenterMachineMapping();
            System.out.println(coloHost);
            for (Map.Entry<String, String> entry : coloHost.entrySet()) {

            }
        }
    }
}

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,

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

Answer 1

You're talking math. The answer is (n choose k), where n is the number of machines, and k is the number of datacenters.

The reason is the following: The ordering doesn't really matter, so we'll assume that the Datacenters are always arranged in the same order. For the first data center, we can pick any one of the n machines. For the second, we can pick any one of the machines, except for the one picked before, thus n * (n-1). The next data center will lead to n * (n-1) * (n-2) possible situations.

Thus, if you had 10 machines, and 4 datacenters, you would have:

10 * 9 * 8 * 7 possibile combinations.

More info here: http://en.wikipedia.org/wiki/Combination

If you want a function to do the work for you , it is in the Apache commons: http://commons.apache.org/proper/commons-math/apidocs/org/apache/commons/math3/util/ArithmeticUtils.html#binomialCoefficientDouble%28int,%20int%29

However, if you are actually wanting to generate those combinations, then you need a for loop.

Answer 2

Not really sure what you've asked here, but i think i can see where the problem is, each time get call get mapping you only generate 1 row. so i've rewritten the code so it generates all of them and gives you back a list of the maps. so you can do what you need with them.

public class DataCenterMapping {

    public static void main(String[] args) {

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


            List<Map<String, String>> coloHost = dcm
                    .getDatacenterMachineMappings();

            System.out.println(coloHost);

    }
}

class DatacenterMachineMapping {

    private boolean firstCall = true;
    private int hostListIndex = 0;
    private List<String> datacenterList, hostList;

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

    public List<Map<String, String>> getDatacenterMachineMappings() {
        List<Map<String, String>> grid = new ArrayList<Map<String, String>>();
        for (int i = 0; i < datacenterList.size(); i++) {

            Map<String, String> datacenterMachineMapping = new HashMap<String, String>();
            String[] line = new String[hostList.size()];
            for (int j = 0; j < line.length; j++) {
                int off = j + i;
                if (off >= datacenterList.size()) {
                    off -= datacenterList.size();
                }
                datacenterMachineMapping.put(hostList.get(j) ,datacenterList.get(off));
            }

            grid.add(datacenterMachineMapping);
        }
        return grid;
    }

}

example output:

[{h4=dc1, h1=dc1, h3=dc3, h2=dc2}, {h4=dc2, h1=dc2, h3=dc1, h2=dc3}, {h4=dc3, h1=dc3, h3=dc2, h2=dc1}]