Finding every possible combination of array entries from multiple lists with unknown bounds in Java

I am sure this post will resonate with pretty much any developer that reads it. Have you ever had a problem where you had to really step back and think about for a long time? A problem where the wealth of the internet helps a little but just isn’t what you were looking for? One big problem is I had recursion on my brain and I was convinced for a long time recursion would be needed. Seeing many similar problems solved with recursion I thought it was the way to go.. “Much to learn you still have…my old padawan.” – Yoda.

A long time for me is hours or even days. Usually I have some level of experience in the past that helps me quickly figure out coding tasks. Well for some reason this thing got me thinking for almost an entire day. And when I say entire day I mean I still do other things but its embedded in the back of my brain. I had my notebook with me the entire day drawing out boxes, arrows, and visualizing walking through loops. It wasn’t until later that night when I realized what I had to do. This was that kind of problem.

Head shots thoughtful, thinking, finding solution man

In the commerce world you have products and SKU’s. A product is the base definition of something you are selling and the SKU’s are the same product but with different attributes that represent the different defining attribute a shopper can select like size, color, length, width, etc. So imagine a pair of pants with three attributes: waist, length, and color. Let’s say each attribute has the following values:

waist = 34,36,38,32,40
length = 30,32,34,36
color = Black,Royal Blue,Khaki,Navy,Charcoal,Dark Brown,Dark Navy

This means if we had a SKU for every combination of waist, length, and color we would have a total number of SKUs equaling 160 = 5x4x8. In order to get all possible combinations we need to find an algorithm that can generate them and the problem is we don’t know up front how many attributes there are, or how many values each attribute has. I took a few stabs at this, a couple times with recursion and then I actually settled on a solution without recursion.

So imagine, the end result for each sku might look like this (SKU count is not actual here for this problem):

SKU_1 = 34,30,Black
SKU_2 = 34,30,Royal Blue
SKU_3 = 34,30,Khaki
SKU_3 = 34,30,…

SKU_70 = 34,32,Black
SKU_71 = 34,32,Royal Blue
SKU_72 = 34,32,Khaki
SKU_73 = 34,32,…

SKU_140 = 36,30,Black
SKU_141 = 36,30,Royal Blue
SKU_142 = 36,30,Khaki
SKU_143 = 36,30,…
etc

First I started by getting a list of all of the attributes assigned to a product:

List definingAttributes = getDefiningAttribites(product);

Then I set up these two arrays to track where we are in the process. They are both integer arrays; curIndex will keep track of where we are in the attribute collection (ie. the position in the list) and maxItems will let us know when to reset the curIndex back to zero once we get through all of its values. definingAttributes.size() in this example would be 3 (waste, length, color).

int curIndex[] = new int[definingAttributes.size()];
int maxItems[] = new int[definingAttributes.size()];

Next we iterate through each attribute to get its maxItems – essentially the total number of values in each attribute. maxItems in this case ends up looking like this:

maxItems[] = {5, 4, 7}

Next, I iterate through an array for the total SKU count dimensions and create a SKU for each combination. This is where it got a little tricky at first but in the end the code is very simple and easy to follow. Since Java integer arrays all initialize zero I realized I just need to treat it like a register where the values to the left increment as the ones to the right reach their max value. So if we look at the same SKU combinations as before in the form of array indexes curIndex[] would look like this:

SKU_1 = 0,0,1
SKU_2 = 0,0,2
SKU_3 = 0,0,3
SKU_3 = 0,0,4,…

SKU_70 = 0,1,1
SKU_71 = 0,1,2
SKU_72 = 0,1,3
SKU_73 = 0,1,4

SKU_140 = 1,1,1
SKU_141 = 1,1,2
SKU_142 = 1,1,3
SKU_143 = 1,1,4
etc

So in the end, I just created each SKU, referenced the current indexes in curIndex array and pulled the literal value from the appropriate attribute values collection, then at the end of the loop I had a function called checkLevels() that did the bounds and checks on those two int arrays, then increment when appropriate.

Level is the maximum number of attributes minus one (meaning the last attribute since Java arrays start at an index of zero). We then just increment the current level and then check it against the maxItems for that attribute, once we get to the maxItem value we increment the index to the left (the previous level). This will automatically count up each attribute for all possible combinations.

[codesyntax lang=”java”]

	private void checkLevels(int level, int[] curIndex, int[] maxItems) {
		int previous = level;
		boolean incrementPreviousLevel = false;
		
		while(previous >=0){
			if (incrementPreviousLevel)
				curIndex[previous]++;
			
			if (curIndex[previous] > maxItems[previous]){
				curIndex[previous] = 0;
				incrementPreviousLevel = true;
			}else{
				incrementPreviousLevel = false;
			}
			
			previous--;
		}
	}

[/codesyntax]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s