java - 如何预先计算有效组合数而不是使用 while 循环？

Question

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

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

我只想生成以下组合 -

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}

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

还有一个例子——如果我只有三个主机，那么下面的组合我应该只得到——

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}

所以我想出了下面的代码，它工作得很好 -

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 循环，它会一直运行，

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

Answer 1

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

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

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

10 * 9 * 8 * 7 可能的组合。

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

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

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