# How to generate valid number of combinations basis on the rules?

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.

Problem Statement:

Now I have got all the above logic working fine in my below code:

public static List<Map<String, String>> createDatacenterIdMappings(Map<String, List<String>> input, boolean debug) {
// Output holder
ArrayList<Map<String, String>> output = new ArrayList<Map<String, String>>();

// Initialize variables
int szRaw = input.size();
int minReq = -1;
for (List<String> dataCenters : input.values()) {
minReq = dataCenters.size() > minReq ? dataCenters.size() : minReq; // Find minimum size required
}
minReq = input.size() > minReq ? input.size() : minReq;

// Flip map from datacenters : id to id : datacenters if
// required
boolean flipped = false;
if (minReq == input.size()) {
Map<String, List<String>> temp = new LinkedHashMap<String, List<String>>();
Set<String> dataCenters = input.keySet();
for (String dataCenter : dataCenters) {
List<String> id = input.get(dataCenter);
for (String machine : id) {
if (!temp.containsKey(machine)) {
temp.put(machine, new ArrayList<String>());
}
}
}
input = temp;
flipped = true;
}

ArrayList<String> keys = new ArrayList<String>(input.keySet());
int k = 0;
// For each row in output process
for (int i = 0; i < minReq; i++) {
// A map to hold output, and another to track status, TODO: can be
// reduced to one
Map<String, String> map = new LinkedHashMap<String, String>();
Map<String, String> outputMap = new LinkedHashMap<String, String>();
for (int j = 0; j < keys.size(); j++) {

List<String> list = input.get(keys.get(j));
int sz = list.size();
if (sz == 0)
continue;

// Find next eligible value for current key (if key is
// datacenter then valid value)
String valueToUse = null;
k = k % sz;
int initK = k;
boolean found = false;
do {
valueToUse = list.get(k);
if (!map.values().contains(valueToUse)) {
found = true;
break;
}
k = (k + 1) % sz;
} while (k != initK);
if (!found)
continue;
map.put(keys.get(j), valueToUse);
if (flipped)
outputMap.put(valueToUse, keys.get(j));
else
outputMap.put(keys.get(j), valueToUse);
list.remove(k);
}
}
return output;
}


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 am opting for code review to see whether we 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 id's 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);

• A few othe data cases that may throw off a few people: dc1, dc2, dc3 with each having hosts h1, h2 – Vogel612 Jul 8 '14 at 22:23
• Additionally something that will throw off even more sophisticated solutions: remove one of the hosts in dc2 for additional boggling :) – Vogel612 Jul 8 '14 at 22:30
• Follow-up question – 200_success Jul 12 '14 at 11:17

Your code is so complicated that I did not understand it (I did not try that long). I decided to write my own solution since I thought it would take less time than understanding your code. My method takes about 15 lines. Also, I used good OO decomposition and wrapped this generation of configurations in a class called... ConfigurationGenerator. I defined a class in part because I make copies of the lists.

So if you want an actual code review: your code is much too complicated for the task at hand. I guess only experience allows you to recognize early on that you are on the wrong (or too complicated) path.

public static class ConfigurationGenerator<K, V> {
private Map<K, List<V>> lists;

public ConfigurationGenerator(Map<K, List<V>> lists) {
// 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) {
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);
}
}

• What you write here is plain incorrect. Actually each line of code, except for about 8 in that 80LoC method has their full reason for existence. after I spent two hours dissecting the code and having a rename-orgy I know! Actually I am sure your code will not produce the same output for a few test cases I have come up with. I will post an answer tomorrow to prove – Vogel612 Jul 8 '14 at 22:19

Your code is very hard to understand. As I mentioned in a comment, I needed roundabout 2 hours to unwrap it, and that was just for understanding. In that process I renamed a big part of your variables, so: here goes the review, be prepared

# Naming:

Overall the naming quality of this code is between acceptable and hellishly gruesome.

int minReq = -1;


This name is a drastic shortening, and missing too much context to describe exactly what it does. I renamed to requiredIterations, and suddenly the for-loop 20 LoC later was a little clearer. Everytime you read minReq, you need to remember: "minReq stands for the minimum required iterations". If you read requiredIterations then you know: "this stands for the minimum required iterations".

int k = 0;


Later you use k to do some very useful, but hard to understand stuff. Do you actually know what k is? I can tell you. It's an index, that's persistent through the different for-loops you have. I thusly named it persistentIndex.

And this is where it gets fishy. Your requirements don't match the currently used code! This totally boggled me.

Map<String, String> map = new LinkedHashMap<String, String>();
Map<String, String> outputMap = new LinkedHashMap<String, String>();


These are horrible too. What is in your Map map? You comment there "tracking status in one map, output in the other". This is not a comment, it's a name! your map is better off with statusTrackingMap.

Then there is that outputMap. I confused that one with the output fairly often, because they both start with output. What do you put in there? The current data-center:host combinations. Then name it, so it contains what it says on the tin!: currentCombinationsMap is definitely better.

List<String> list = input.get(keys.get(j));


ouch. First Map map and now List list? Again rename it. I chose machines from the comment you wrote before flipped.

int sz = list.size();


or rather, now:

int sz = machines.size();


This one is the worst after k. Use machineCount or something along these lines instead!

int initK = k;


That one is also kinda evil. This is the break-marker for the following do-while loop, given the case persistentIndex rolls back to 0. I called it startingPersistentIndex, which still isn't good, but definitely better than initK.

int szRaw = input.size();


You never use that variable. That was the first thing I could remove.

# Code-Smells:

You have a few not-very-nice code-smells in that code, one of them is this here:

if (!found) {
continue;
}
//following code


This is in fact a guard clause, and a not even quite bad at that. But it's overly complicated to track back. What you actually want to say is:

if(found){
//following code
}


IMO this is easier to understand.

While we're at it:

if (!map.values().contains(valueToUse)) {
found = true;
break;
}


is in fact nothing else but:

found = !map.containsValue(valueToUse);


for the following program. And here we see, that the name is wrong. It says found on the tin, but it tells you if the valueToUse was not found in the statusTrackingMap.

Aaand another rename:

if(!map.containsValue(valueToUse)){
valueToUseNotFound = true;
break;
}


And continuing from that, this could be refactored to sit somewhere different, but then your behavior changes. As I don't know how that would be seen, it might be difficult, but in fact, this is just a break-condition for your do-while loop.
It could be rewritten to:

do {
//stuff
} while (persistentIndex != startingPersistentIndex && !valueToUseNotFound)


But this includes another increment of the persistentIndex and I was reluctant to change the behavior of the code.

Your innermost for-loop then ends with:

if (valueToUseNotFound) {
statusTrackingMap.put(dataCenters.get(j), valueToUse);
if(flipped) {
currentCombinationsMap.put(valueToUse);
} else {
currentCombinationsMap.put(dataCenters.get(j), valueToUse);
}
machines.remove(persistentIndex);
}


And this is where I lost it, when I examined WHY IN GOD'S NAME THE HELL the expected output when calling your old method with the same input as my refactored method and asserting: assertEquals(oldOutput.toString(), newOutput.toString()) was [{}, {}, {}]

So here is your lesson for all eternity, and if it wasn't you who committed this crime, then slap that person with a boulder!

# DON'T TINKER WITH INPUT!

### Keep references intact, somebody outside may want to reuse them!

It's like you gave some person a reference to your bag of Keys, asking him to tell you how he would reorder them on different bunches, and when you check your keybag, suddenly all the keys have vanished.

</rant>


What you do is: you copy the data, and you leave the original references intact. How? like this:

Map<String, List<String>> clone = new LinkedHashMap<>();
for (String key : input.keySet()) {
clone.put(key, new ArrayList<>(input.get(key)));
}


# Declaring output variables:

The general rule in Java is: Declare variables as close as possible to their usage.

This especially applies for your output. Why do you declare it at the top of your method, and use it the first time 70 lines later. until then everybody will have forgotten what that actually was, let alone be able to know the type of it.

Most All of the comments you wrote were useless after I renamed the variables that were explained to meaningful names. The only comment where that was not the case, was your //TODO and that should have been deprecated before you posted to CR, so I just ignored it.

# Final Code:

Applying all this, I could break down your code from ~80 Lines to ~55 Lines, without losing any functionality while drastically increasing readability:

public static List<Map<String, String>> createDatacenterIdMappings (
final Map<String, List<String>> original) {

Map<String, List<String>> input = new LinkedHashMap<>();
for (String key : original.keySet()) {
input.put(key, new ArrayList<>(original.get(key)));
}

int requiredIterations = -1;
for (List<String> dataCenters : input.values()) {
requiredIterations = dataCenters.size() > requiredIterations
? dataCenters.size()
: requiredIterations;
}
requiredIterations = input.size() > requiredIterations
? input.size()
: requiredIterations;

ArrayList<Map<String, String>> output = new ArrayList<>();
ArrayList<String> dataCenters = new ArrayList<>(input.keySet());
int persistentIndex = 0;

for (int i = 0; i < requiredIterations; i++) {
Map<String, String> statusTrackingMap = new LinkedHashMap<>();
Map<String, String> currentCombinationsMap = new LinkedHashMap<>();
for (int j = 0; j < dataCenters.size(); j++) {
List<String> machines = input.get(dataCenters.get(j));
int machineCount = machines.size();
if (machineCount == 0) {
continue;
}

String valueToUse = null;
persistentIndex = persistentIndex % machineCount;
int persistentIndexIterationStartMarker = persistentIndex;
boolean valueToUseNotFound = false;
do {
valueToUse = machines.get(persistentIndex);
if (!statusTrackingMap.containsValue(valueToUse)) {
valueToUseNotFound = true;
break;
}
persistentIndex = (persistentIndex + 1) % machineCount;
} while (persistentIndex != persistentIndexIterationStartMarker);

if (valueToUseNotFound) {
statusTrackingMap.put(dataCenters.get(j), valueToUse);
currentCombinationsMap.put(dataCenters.get(j), valueToUse);
machines.remove(persistentIndex);
}
}

• Thanks for help. Appreciated a lot with your detailed suggestion and feedback. One minor issue which I am noticing is, if I try with example 4 as in my question, it always misses h5 for dc3 somehow. Any thoughts why? – arsenal Jul 9 '14 at 7:09