如何预先计算有效的组合数而不是使用 while 循环? [英] How to precalculate valid number of combinations instead of using while loop?

问题描述

给定数据中心列表 dc1、dc2、dc3 和机器列表 h1、h2、h3、h4，如下所述 -

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}

每次传递中的每个数据中心都应获得备用机器/主机.他们不应该得到相同的机器.例如在 a 中如上所示 - dc1 得到 h1，dc2 得到 h2，dc3 得到 h3 所以所有的每个数据中心的机器都不同.在第二遍中，如 b 所示 - 现在 dc1 得到 h2(因为 dc1 在第一遍中已经得到了 h1)，dc2 得到了 h3(bcoz dc2 第一遍已经得到了 h2)，dc3 得到了 h4(bcoz dc3 第一遍已经得到了 h3)等等.

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);
    }
}

问题陈述:-

唯一的问题是我有一个会一直运行的while循环，

The only problem is I have a while loop which will keep on running always,

有什么办法可以预先计算有效组合的数量而不是使用 while 循环?

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

推荐答案

你说的是数学.答案是(n 选择 k)，其中 n 是机器的数量，k 是数据中心的数量.

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

原因如下:排序并不重要，所以我们假设数据中心总是以相同的顺序排列.对于第一个数据中心，我们可以选择 n 台机器中的任何一台.对于第二个，我们可以选择任何一台机器，除了之前选择的机器，因此 n * (n-1).下一个数据中心将导致n * (n-1) * (n-2) 种可能的情况.

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.

因此，如果您有 10 台机器和 4 个数据中心，您将拥有:

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

10 * 9 * 8 * 7 种可能的组合.

更多信息在这里:http://en.wikipedia.org/wiki/Combination

如果你想要一个函数为你完成工作，它在 Apache 公共资源中:http://commons.apache.org/proper/commons-math/apidocs/org/apache/commons/math3/util/ArithmeticUtils.html#binomialCoefficientDouble%28int,%20int%29

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

但是，如果您确实想要生成这些组合，那么您需要一个 for 循环.

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

这篇关于如何预先计算有效的组合数而不是使用 while 循环?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！