Generating a valid number of combinations of datacenter and its host ID

Question

I have a list of datacenters, which are dc1, dc2 and dc3. And each datacenter has six IDs as of now (can be 11 in each datacenter as well or uneven number for each datacenter).

dc1 - h1, h2, h3, h4, h5, h6
dc2 - h1, h2, h3, h4, h5, h6
dc3 - h1, h2, h3, h4, h5, h6

Now I am trying to generate combinations of datacenter and its ID so the rules are:

1. In each pass, we will have each datacenter and alternate IDs.

For example:

dc1=h1, dc2=h2, dc3=h3

If you see above, each datacenter has unique ID, meaning dc1 has h1, dc2 has h2 and dc3 has h3. We cannot have same ID for each datacenter in any of the passes, like we cannot have like this:

dc1=h1, dc2=h1, dc3=h3

If you see above, h1 appears twice in dc1 and dc2 which is wrong.

2. In the next pass, we should not use same ID for that datacenter. Meaning if below is the first pass:

   dc1=h1, dc2=h2, dc3=h3
   

   then second pass can be as below. If you see below, dc1 has h4 in the second pass, which has some other ID apart from h1, as h1 was used in the first pass for dc1 datacenter and same with dc2 and dc3.

   dc1=h4, dc2=h5, dc3=h6
   

   We cannot have same ID for same datacenter in the next pass if it was used earlier. So we cannot have this in the second pass:

   dc1=h4, dc2=h2, dc3=h6
   

   as h2 was used earlier for dc2 in the first pass.

Now I have got all the above logic working fine in my below code. I'd like to see whether it will work fine in all the input cases and if it will follow my two above rules or not. I have tested on some of the input cases and it works fine.

public static class ConfigurationGenerator<K, V> {
 private Map<K, List<V>> lists;
 public ConfigurationGenerator(Map<K, List<V>> lists) {
 this.lists = new LinkedHashMap<K, List<V>>();
 // Make copies of the lists so we can modify them without touching the original lists.
 for (K key : lists.keySet())
 this.lists.put(key, new ArrayList<>(lists.get(key)));
 }
 /**
 * @returns null when all lists are exhausted.
 */
 public Map<K, V> extractConfiguration() {
 Map<K, V> output = new HashMap<K, V>();
 Set<V> takenValues = new HashSet<>();
 for (K key : lists.keySet()) {
 List<V> list = lists.get(key);
 V chosenValue = null;
 for (V value : list) {
 if (!takenValues.contains(value)) {
 chosenValue = value;
 break;
 }
 }
 if (chosenValue != null) {
 takenValues.add(chosenValue);
 list.remove(chosenValue);
 output.put(key, chosenValue);
 }
 }
 return output.isEmpty() ? null : output;
 }
}
public static void main(String[] args) {
 Map<String, List<String>> lists = new LinkedHashMap<String, List<String>>();
 lists.put("dc1", Arrays.asList("h1", "h2", "h3", "h4"));
 lists.put("dc2", Arrays.asList("h1", "h2", "h3", "h4"));
 lists.put("dc3", Arrays.asList("h1", "h2", "h3", "h4"));
 ConfigurationGenerator<String, String> generator = new ConfigurationGenerator<>(lists);
 Map<String, String> map = null;
 while ((map = generator.extractConfiguration()) != null) {
 System.out.println(map);
 }
}

For the below inputs:

List<String> hosts1 = new ArrayList<String>(Arrays.asList("h1", "h2", "h3", "h4"));
List<String> hosts2 = new ArrayList<String>(Arrays.asList("h1", "h2", "h3", "h4"));
List<String> hosts3 = new ArrayList<String>(Arrays.asList("h1", "h2", "h3", "h4"));
Map<String, List<String>> maps = new LinkedHashMap<String, List<String>>();
maps.put("dc1", hosts1);
maps.put("dc2", hosts2);
maps.put("dc3", hosts3);
boolean debug = false;
List<Map<String, String>> mappings = createDatacenterIdMappings(maps, debug);
// print mappings here

I get output as:

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

Other input parameters can be:

 List<String> hosts1 = new ArrayList<>(Arrays.asList("h1", "h2", "h3", "h4", "h5", "h6",
 "h7", "h8", "h9", "h10", "h11"));
 List<String> hosts2 = new ArrayList<>();
 List<String> hosts3 = new ArrayList<>();
 Map<String, List<String>> maps = new LinkedHashMap<String, List<String>>();
 maps.put("dc1", hosts1);
 maps.put("dc2", hosts2);
 maps.put("dc3", hosts3);

And output for above input comes as:

[{dc1=h1}, 
 {dc1=h2}, 
 {dc1=h3}, 
 {dc1=h4}, 
 {dc1=h5}, 
 {dc1=h6}, 
 {dc1=h7}, 
 {dc1=h8}, 
 {dc1=h9}, 
 {dc1=h10}, 
 {dc1=h11}]

or below is another input:

 List<String> hosts1 = new ArrayList<>(Arrays.asList("h1", "h2", "h3"));
 List<String> hosts2 = new ArrayList<>(Arrays.asList("h1", "h2", "h3", "h4", "h5", "h6",
 "h7", "h8", "h9", "h10", "h11"));
 List<String> hosts3 = new ArrayList<>(Arrays.asList("h1", "h2", "h3"));
 Map<String, List<String>> maps = new LinkedHashMap<String, List<String>>();
 maps.put("dc1", hosts1);
 maps.put("dc2", hosts2);
 maps.put("dc3", hosts3);

And output for above input comes as:

[{dc1=h1, dc2=h2, dc3=h3}, 
 {dc1=h2, dc2=h1}, 
 {dc1=h3, dc2=h4, dc3=h2}, 
 {dc2=h5, dc3=h1}, 
 {dc2=h3}, 
 {dc2=h6}, 
 {dc2=h7}, 
 {dc2=h8}, 
 {dc2=h9}, 
 {dc2=h10}, 
 {dc2=h11}]

I'd like to see whether I can simplify this code or improve it slightly. Since it looks slightly complicated to me, there should be some way of simplifying this code for sure.

Below is the code I use to print out the mappings. Just keep on changing the input parameters.

public static void main(String[] args) {
 List<String> hosts1 = new ArrayList<String>(Arrays.asList("h1", "h2", "h3", "h4"));
 List<String> hosts2 = new ArrayList<String>(Arrays.asList("h1", "h2", "h3", "h4"));
 List<String> hosts3 = new ArrayList<String>(Arrays.asList("h1", "h2", "h3", "h4"));
 Map<String, List<String>> maps = new LinkedHashMap<String, List<String>>();
 maps.put("dc1", hosts1);
 maps.put("dc2", hosts2);
 maps.put("dc3", hosts3);
 boolean debug = false;
 List<Map<String, String>> mappings = createDatacenterIdMappings(maps, debug);
 printOutput(mappings);
}
public static void printOutput(List<Map<String, String>> mappings) {
 System.out.println(mappings.toString().replaceAll("},", "},\n") + "\n==================================");
}

Below are the inputs and outputs:

Example 1:

 List<String> hosts1 = new ArrayList<String>(Arrays.asList("h1", "h2", "h3", "h4"));
 List<String> hosts2 = new ArrayList<String>(Arrays.asList("h1", "h2", "h3", "h4"));
 List<String> hosts3 = new ArrayList<String>(Arrays.asList("h1", "h2", "h3", "h4"));
 Map<String, List<String>> maps = new LinkedHashMap<String, List<String>>();
 maps.put("dc1", hosts1);
 maps.put("dc2", hosts2);
 maps.put("dc3", hosts3);

Output 1:

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

Example 2:

 List<String> hosts1 = new ArrayList<>(Arrays.asList("h1", "h2", "h3", "h4", "h5", "h6", "h7", "h8", "h9",
 "h10", "h11"));
 List<String> hosts2 = new ArrayList<>();
 List<String> hosts3 = new ArrayList<>();
 Map<String, List<String>> maps = new LinkedHashMap<String, List<String>>();
 maps.put("dc1", hosts1);
 maps.put("dc2", hosts2);
 maps.put("dc3", hosts3);

Output 2:

[{dc1=h1},
 {dc1=h2},
 {dc1=h3},
 {dc1=h4},
 {dc1=h5},
 {dc1=h6},
 {dc1=h7},
 {dc1=h8},
 {dc1=h9},
 {dc1=h10},
 {dc1=h11}]

Example 3:

 List<String> hosts1 = new ArrayList<>(Arrays.asList("h1", "h2", "h3", "h4", "h5", "h6",
 "h7", "h8", "h9", "h10", "h11"));
 List<String> hosts2 = new ArrayList<>(Arrays.asList("h1", "h2", "h3", "h4", "h5", "h6",
 "h7", "h8", "h9", "h10", "h11"));
 List<String> hosts3 = new ArrayList<>(Arrays.asList("h1", "h2", "h3", "h4", "h5", "h6",
 "h7", "h8", "h9", "h10", "h11"));
 Map<String, List<String>> maps = new LinkedHashMap<String, List<String>>();
 maps.put("dc1", hosts1);
 maps.put("dc2", hosts2);
 maps.put("dc3", hosts3);

Output 3:

[{dc1=h1, dc2=h2, dc3=h3},
 {dc1=h4, dc2=h5, dc3=h6},
 {dc1=h7, dc2=h8, dc3=h9},
 {dc1=h10, dc2=h11, dc3=h1},
 {dc1=h2, dc2=h1, dc3=h4},
 {dc1=h5, dc2=h4, dc3=h7},
 {dc1=h8, dc2=h7, dc3=h10},
 {dc1=h11, dc2=h10, dc3=h2},
 {dc1=h3, dc2=h6, dc3=h8},
 {dc1=h9, dc2=h3, dc3=h5},
 {dc1=h6, dc2=h9, dc3=h11}]

Example 4:

And similarly for six host IDs per datacenter:

 List<String> hosts1 = new ArrayList<>(Arrays.asList("h1", "h2", "h3", "h4", "h5", "h6"));
 List<String> hosts2 = new ArrayList<>(Arrays.asList("h1", "h2", "h3", "h4", "h5", "h6"));
 List<String> hosts3 = new ArrayList<>(Arrays.asList("h1", "h2", "h3", "h4", "h5", "h6"));
 Map<String, List<String>> maps = new LinkedHashMap<String, List<String>>();
 maps.put("dc1", hosts1);
 maps.put("dc2", hosts2);
 maps.put("dc3", hosts3);

• 200_success: Previous question

Answer 1

Unit testing

Your code does the job. But right now there's no good way to verify that. Running the main method with various inputs and reading the output is not a good way to verify. This is relatively easy to fix by converting your manual tests to unit tests that are easy to re-run and re-verify, for example:

public class ConfigGeneratorTest {
 private String resultToString(Map<String, String> map) {
 return new TreeMap<>(map).toString();
 }
 @Test
 public void testBasicExampleWithSameHosts() {
 Map<String, List<String>> lists = new LinkedHashMap<>();
 lists.put("dc1", Arrays.asList("h1", "h2", "h3", "h4"));
 lists.put("dc2", Arrays.asList("h1", "h2", "h3", "h4"));
 lists.put("dc3", Arrays.asList("h1", "h2", "h3", "h4"));
 ConfigGenerator<String, String> generator = new ConfigGenerator<>(lists);
 assertEquals("{dc1=h1, dc2=h2, dc3=h3}", resultToString(generator.next()));
 assertEquals("{dc1=h2, dc2=h1, dc3=h4}", resultToString(generator.next()));
 assertEquals("{dc1=h3, dc2=h4, dc3=h1}", resultToString(generator.next()));
 assertEquals("{dc1=h4, dc2=h3, dc3=h2}", resultToString(generator.next()));
 assertTrue(generator.next().isEmpty());
 }
 @Test
 public void testExampleWithEmptyHosts() {
 Map<String, List<String>> lists = new LinkedHashMap<>();
 lists.put("dc1", Arrays.asList("h1", "h2", "h3"));
 lists.put("dc2", Arrays.asList());
 ConfigGenerator<String, String> generator = new ConfigGenerator<>(lists);
 assertEquals("{dc1=h1}", resultToString(generator.next()));
 assertEquals("{dc1=h2}", resultToString(generator.next()));
 assertEquals("{dc1=h3}", resultToString(generator.next()));
 assertTrue(generator.next().isEmpty());
 }
 @Test
 public void testExampleWithVariableHosts() {
 Map<String, List<String>> lists = new LinkedHashMap<>();
 lists.put("dc1", Arrays.asList("h1", "h2"));
 lists.put("dc2", Arrays.asList("h1", "h2", "h3"));
 lists.put("dc3", Arrays.asList("h3", "h4", "h5"));
 ConfigGenerator<String, String> generator = new ConfigGenerator<>(lists);
 assertEquals("{dc1=h1, dc2=h2, dc3=h3}", resultToString(generator.next()));
 assertEquals("{dc1=h2, dc2=h1, dc3=h4}", resultToString(generator.next()));
 assertEquals("{dc2=h3, dc3=h5}", resultToString(generator.next()));
 assertTrue(generator.next().isEmpty());
 }
}

I wrote these test cases before improving your code. When writing the assertions, you don't even have to think too much. You can start by adding failing assertions like this:

assertEquals("blah", resultToString(generator.next()));

When you run this test case, it will fail, but it will tell you what was the expected result. If that result seems to make sense, you can copy-paste it into the assertion. You can continue this until all tests pass. Converting your examples took me only a few minutes this way.

Until this point, I only made trivial changes and some style changes for my taste:

• Renamed the ConfigurationGenerator class to ConfigGenerator, which is just shorter, more comfortable, without losing meaning
• Renamed the extractConfiguration method to next, which is short and sweet
• Return an empty map instead of null when there are no more possible configurations. Empty collections are more ergonomic in general, because checking null values is often tedious, ugly, and an unnecessary additional check. It's good to avoid using null values whenever possible.

These unit tests are easy to rerun, so now I can boldly go and make changes, with the comfort of knowing that the unit tests will scream at me if I break something.

Improvements

The variable storing the mapping of data centers to hostnames can be improved:

private Map<K, List<V>> lists;

This can be final, as later in your code you initialize it once, and you don't need to reassign it. final elements make the code more robust by preventing unintended changes by accident.

Since duplicate hostnames won't make sense for your use case, so a Set will be better. Later in your code where you remove hostnames from the list, a Set will be more efficient.

private final Map<K, Set<V>> lists;

---

There are several efficiency and coding style issues here:

public ConfigurationGenerator(Map<K, List<V>> lists) {
 this.lists = new LinkedHashMap<K, List<V>>();
 for (K key : lists.keySet()) 
 this.lists.put(key, new ArrayList<>(lists.get(key)));
}

It's strongly recommended to use braces around for and if statements.

You use Java 7 style diamond operator in new ArrayList<>, but not for the LinkedHashMap. Why not just use the diamond operator everywhere.

In the loop you iterate over the keys, and then lookup elements in the input map using that key. It's more efficient to iterate over the entries, so that you don't need to perform an additional lookup by key. Like this:

this.lists = new LinkedHashMap<>();
for (Map.Entry<K, List<V>> entry : lists.entrySet()) {
 K key = entry.getKey();
 List<V> list = entry.getValue();
 this.lists.put(key, new TreeSet<>(list));
}

---

In extractConfiguration:

Map<K, V> output = new HashMap<K, V>();
Set<V> takenValues = new HashSet<>();
for (K key : lists.keySet()) {
 List<V> list = lists.get(key);
 V chosenValue = null;
 for (V value : list) {
 if (!takenValues.contains(value)) {
 chosenValue = value;
 break;
 }
 }
 if (chosenValue != null) {
 takenValues.add(chosenValue);
 list.remove(chosenValue);
 output.put(key, chosenValue);
 }
}

You don't need the chosenValue variable. You could remove it, and move its code in front of the break statement.

Again, the loop will be more efficient to iterate over the entries instead of the keys and then doing a lookup.

Finally, for unit tests to work well, the results need to be in a predictable order. The ordering of HashMap elements is undefined, so we should use something else instead.

Suggested implementation

Based on the above suggestions, and a few other minor changes, here's an alternative implementation:

class ConfigGenerator<K, V> {
 private final Map<K, Set<V>> lists = new LinkedHashMap<>();
 public ConfigGenerator(Map<K, List<V>> lists) {
 for (Map.Entry<K, List<V>> entry : lists.entrySet()) {
 K key = entry.getKey();
 List<V> list = entry.getValue();
 this.lists.put(key, new TreeSet<>(list));
 }
 }
 public Map<K, V> next() {
 Map<K, V> output = new LinkedHashMap<>();
 Set<V> taken = new HashSet<>();
 for (Map.Entry<K, Set<V>> entry : lists.entrySet()) {
 K key = entry.getKey();
 Set<V> values = entry.getValue();
 for (V value : values) {
 if (!taken.contains(value)) {
 taken.add(value);
 values.remove(value);
 output.put(key, value);
 break;
 }
 }
 }
 return output;
 }
}