Ben Nadel
On User Experience (UX) Design, JavaScript, ColdFusion, Node.js, Life, and Love.
I am the chief technical officer at InVision App, Inc - a prototyping and collaboration platform for designers, built by designers. I also rock out in JavaScript and ColdFusion 24x7.
Meanwhile on Twitter
Loading latest tweet...
Ben Nadel at CFUNITED 2010 (Landsdown, VA) with:

Ask Ben: Iterating Over An Unknown Number Of Nested Lists

By Ben Nadel on

Hi There, I've think I've looked at this problem way too long and hoping a set of fresh eyes can help. Basically, I have a eCommerce site where I want to auto create product SKUs based on the product options. Each of those options have their own set of options. Example: For a tshirt with the options of Color, Size and Gender we have the following options:

Color (Blue, Black, Red)
Size (Small, Med, Large)
Gender (Men's, Women's)

If the user adds a new shirt that comes in Blue or Black / Small, Med, Large / Men's I want to create a table showing all possible options. Something like this:

1 Blue Small Men's
2 Blue Med Men's
3 Blue Large Men's
4 Black Small Men's
5 Black Med Men's
6 Black Large Men's

Okay, that's simple enough. The part that is throwing me off is that a shirt doesnt always have 3 options (Color, Size and Gender). Sometimes it might have 2 options, sometimes 4. Basically what I'm getting at is that I need to figure out a way to build the SKU's based on all options that is passed to the script. I hope I explained that okay. Thank you in advance for your time.

When I read this, I wasn't quite sure how I wanted to solve the problem. When you have an unknown number of nested loops, the first thing that jumps to mind is: recursive algorithm. But, I didn't really want to go that way. The problem with a recursive algorithm is that you can't really step through it because it sort of solves itself backwards. Also, when we are dealing with combinations of unknown sets, things can get wildly out of hand before you know it.

I wanted to be able to loop through these lists in a really straightforward and performant way. So, I thought - ColdFusion custom tag. But, before I even messed around with the ColdFusion custom tag, I coded the calling page. This helped me to figure out how I wanted this functionality to work:

  • <!--- Import our loop library. --->
  • <cfimport
  • taglib="./"
  • prefix="nlist"
  • />
  •  
  •  
  • <!--- Build our array of lists. --->
  • <cfset arrLists = [
  • "Blue,Black",
  • "Small,Medium,Large",
  • "Mens,Womens",
  • "Full Sleeve,Short Sleeve"
  • ] />
  •  
  •  
  • <!---
  • Let's loop over our array of lists and find the
  • combination for each iteration. The arrLists variable
  • is our ARRAY of lists and the arrCombo is an array of
  • the current values from each list iteration.
  • --->
  • <nlist:loop
  • index="arrCombo"
  • lists="#arrLists#"
  • delimiters=",">
  •  
  • <!---
  • Loop over our combination to output the current
  • values from each list.
  • --->
  • <cfloop
  • index="intIndex"
  • from="1"
  • to="#ArrayLen( arrCombo )#"
  • step="1">
  •  
  • <!--- Check for formatting needs. --->
  • <cfif (intIndex GT 1)>
  • -
  • </cfif>
  •  
  • #arrCombo[ intIndex ]#
  •  
  • </cfloop>
  •  
  • <br />
  •  
  • </nlist:loop>

Since the coder is not sure how many lists are going to be present for any given product, I figured the easiest way to pass around the nested lists was as an array. And, for the same reasons, I figured the easiest way to reference the current combination would be to return an array of "combination values".

Once I had this example in place, I coded the ColdFusion custom tag that would allow it to run:

  • <!---
  • This method will be used in both the start and end modes
  • of this tag. It takes the current list set up and builds
  • the index combo.
  • --->
  • <cffunction
  • name="BuildCombo"
  • access="public"
  • returntype="array"
  • output="false"
  • hint="I build the Combo array based on the current list indexes.">
  •  
  • <!--- Define the local scope. --->
  • <cfset var LOCAL = {} />
  •  
  • <!--- Build the current combination. --->
  • <cfset LOCAL.Combo = [] />
  •  
  • <!--- Loop over list to get start values. --->
  • <cfloop
  • index="LOCAL.ThisList"
  • array="#VARIABLES.Lists#">
  •  
  • <cfset ArrayAppend(
  • LOCAL.Combo,
  • LOCAL.ThisList.List[ LOCAL.ThisList.Index ]
  • ) />
  •  
  • </cfloop>
  •  
  • <!--- Return combo. --->
  • <cfreturn LOCAL.Combo />
  • </cffunction>
  •  
  •  
  •  
  • <!--- Check to see which mode the tag is executing. --->
  • <cfif (THISTAG.ExecutionMode EQ "Start")>
  •  
  • <!---
  • We only care about the tag attributes the first time
  • around - in the Start mode.
  • --->
  •  
  • <!---
  • This is the name of the value that will be contain
  • the current list values in the CALLER scope.
  • --->
  • <cfparam
  • name="ATTRIBUTES.Index"
  • type="variablename"
  • />
  •  
  • <!---
  • This is the array of lists over which we are going
  • to iterate (loop).
  • --->
  • <cfparam
  • name="ATTRIBUTES.Lists"
  • type="array"
  • />
  •  
  • <!---
  • These are the delimiters that will be use for the
  • individual list iterations.
  • --->
  • <cfparam
  • name="ATTRIBUTES.Delimiters"
  • type="string"
  • default=","
  • />
  •  
  •  
  • <!---
  • First, we want to break our lists up into arrays for
  • faster looping. And, since this will be very index-
  • intensive alogrithm, it will help to have a data
  • structure that we can quickly access by index.
  • --->
  • <cfset VARIABLES.Lists = [] />
  •  
  • <!--- Loop over lists to move to new data struct. --->
  • <cfloop
  • index="VARIABLES.List"
  • array="#ATTRIBUTES.Lists#">
  •  
  • <!---
  • When we break the lists up, we also want to store
  • some other convenience values such as the current
  • index of that loop and the length.
  • --->
  • <cfset VARIABLES.ThisList = {
  • List = ListToArray(
  • VARIABLES.List,
  • ATTRIBUTES.Delimiters
  • ),
  • Index = 1,
  • Length = 0
  • } />
  •  
  • <!--- Update the lenth property. --->
  • <cfset VARIABLES.ThisList.Length = ArrayLen(
  • VARIABLES.ThisList.List
  • ) />
  •  
  • <!---
  • Before we add to the list, let's just double check
  • to make sure that we have a length for this item.
  • If the list has no lenth, it cannot be output.
  • --->
  • <cfif VARIABLES.ThisList.Length>
  •  
  • <cfset ArrayAppend(
  • VARIABLES.Lists,
  • VARIABLES.ThisList
  • ) />
  •  
  • </cfif>
  •  
  • </cfloop>
  •  
  •  
  • <!--- Check to see if we have any lists to work with. --->
  • <cfif NOT ArrayLen( VARIABLES.Lists )>
  •  
  • <!---
  • The passed-in lists did not result in any usable
  • combinations. Break out of tag.
  • --->
  • <cfexit method="exittag" />
  •  
  • </cfif>
  •  
  •  
  • <!---
  • ASSERT: At this point, we know that we have enough data
  • in our lists to perform at least one loop iteration.
  • The variable VARIABLES.Lists holds the lists over which
  • we need to iterate.
  • --->
  •  
  •  
  • <!---
  • Store the index of the list over which we are currently
  • iterating. To start off, this will be the last list.
  • --->
  • <cfset VARIABLES.CurrentList = ArrayLen( VARIABLES.Lists ) />
  •  
  • <!--- Build the current combination and store in CALLER. --->
  • <cfset CALLER[ ATTRIBUTES.Index ] = VARIABLES.BuildCombo() />
  •  
  • <cfelse>
  •  
  • <!--- The END mode of the tag. --->
  •  
  • <!---
  • Keep trying to increment the "current" list value until
  • we break out of the loop. We are doing this because we
  • might have to move over more than one place (list)
  • depending on the list lengths.
  • --->
  • <cfloop condition="true">
  •  
  • <!--- Increment the index of the current list. --->
  • <cfset VARIABLES.Lists[ VARIABLES.CurrentList ].Index++ />
  •  
  • <!---
  • Check to see if we have gone too high with the
  • current list index. If the index extends past the
  • length of the list, we have fully iterated over
  • the current list.
  • --->
  • <cfif (VARIABLES.Lists[ VARIABLES.CurrentList ].Index GT VARIABLES.Lists[ VARIABLES.CurrentList ].Length)>
  •  
  • <!---
  • Since we are out of bounds on the current list,
  • we want to set the current list index back to 1
  • (reset the iteration) and then move to next list
  • to continue iteration.
  • --->
  • <cfset VARIABLES.Lists[ VARIABLES.CurrentList ].Index = 1 />
  •  
  • <!--- Move the current list over one. --->
  • <cfset VARIABLES.CurrentList-- />
  •  
  • <!---
  • Check to see if we have a current list. If we do
  • not, then we moved out of bounds and we are done
  • with the iteration.
  • --->
  • <cfif NOT VARIABLES.CurrentList>
  •  
  • <!---
  • We have fully iterated over every possible
  • combination of the list. Break out of the
  • current tag.
  • --->
  • <cfexit method="exittag" />
  •  
  • </cfif>
  •  
  • <cfelse>
  •  
  • <!---
  • We have increment the current list successfully.
  • Now, we want to go all the way back to the
  • beginning again.
  • --->
  • <cfset VARIABLES.CurrentList = ArrayLen(
  • VARIABLES.Lists
  • ) />
  •  
  • <!--- Break out of this loop. --->
  • <cfbreak />
  •  
  • </cfif>
  •  
  • </cfloop>
  •  
  •  
  • <!---
  • ASSERT: If we have made it this far, then we have another
  • iteration to perform.
  • --->
  •  
  •  
  • <!--- Build the current combination and store in CALLER. --->
  • <cfset CALLER[ ATTRIBUTES.Index ] = VARIABLES.BuildCombo() />
  •  
  • <!--- Loop. --->
  • <cfexit method="loop" />
  •  
  • </cfif>

This tag loops through the given lists the same way we increment the digits of a number - first, we increment the ones digit. Once we have gone as high as we can in that digit, we increment the tens digit once and reset the ones digit to zero. Once we have incremented the tens digit as much as we can, we increment the hundreds digit once and reset the tens digit back to zero. The only difference is that this ColdFusion custom tag is incrementing the index reference for the given list (ie. digit).

When we run the above code, we get the following output:

Blue - Small - Mens - Full Sleeve
Blue - Small - Mens - Short Sleeve
Blue - Small - Womens - Full Sleeve
Blue - Small - Womens - Short Sleeve
Blue - Medium - Mens - Full Sleeve
Blue - Medium - Mens - Short Sleeve
Blue - Medium - Womens - Full Sleeve
Blue - Medium - Womens - Short Sleeve
Blue - Large - Mens - Full Sleeve
Blue - Large - Mens - Short Sleeve
Blue - Large - Womens - Full Sleeve
Blue - Large - Womens - Short Sleeve
Black - Small - Mens - Full Sleeve
Black - Small - Mens - Short Sleeve
Black - Small - Womens - Full Sleeve
Black - Small - Womens - Short Sleeve
Black - Medium - Mens - Full Sleeve
Black - Medium - Mens - Short Sleeve
Black - Medium - Womens - Full Sleeve
Black - Medium - Womens - Short Sleeve
Black - Large - Mens - Full Sleeve
Black - Large - Mens - Short Sleeve
Black - Large - Womens - Full Sleeve
Black - Large - Womens - Short Sleeve

I hope that this helps in some way.




Reader Comments

Sounds like a job for QOQ:

<cfset q=queryNew("idx")>
<cfloop from="1" to="#arrayLen(arrLists)#" index="i">
<cfset queryAddRow(q)>
<cfset querySetCell(q,"idx",i,q.RecordCount)>
</cfloop>
<cfloop from="1" to="#arrayLen(arrLists)#" index="i">
<cfset p=queryNew("a#i#")>
<cfloop list="#arrLists[i]#" index="j">
<cfset queryAddRow(p)>
<cfset querySetCell(p,"a#i#",j,p.RecordCount)>
</cfloop>
<cfquery dbtype="query" name="q">
SELECT *
FROM q, p
</cfquery>
</cfloop>

@Rick,

That looks pretty brilliant. Even after running it, I am having trouble following it a bit. I see that you basically keep joining queries to queries in the second loop. Very clever! I need to study it a bit more to think about the intermediary queries that are being created.

Actually ... that first cfloop is unnecessary now that I think about it. (Sorry, I didn't bother to run it, I was typing it in the comment box off the top of my head.) Just add a single row to the query with idx = "". Then do the rest of the code, starting with the second loop.

For each iteration in the loop, make a temporary query "p". Query p has one column named "a1" or "a2", etc. Loop over the contents of the list so that you have one row for each item.

When you do the join you are creating a cartesian product between p and q, so you get every row in q repeated p.Recordcount times, with the p values filled in correctly. We cheat by naming the cfquery with name="q" so that we just overwrite q with the new query. In this way, q continues to grow exponentially with each new list.

Visually:

Iteration 1:
q.columnList = "idx"; q.RecordCount = 1

Iteration 2:
q.columnList = "idx,a1"; q.RecordCount = 1 * 2 = 2

Iteration 3:
q.columnList = "idx,a1,a2"; q.RecordCount = 2 * 3 = 6

Iteration 3:
q.columnList = "idx,a1,a2,a3"; q.RecordCount = 6 * 2 = 12

Iteration 4:
q.columnList = "idx,a1,a2,a3,a4"; q.RecordCount = 12 * 2 = 24

The "idx" column is just vestigial and can be removed or ignored.

If you want to be really sneaky, you can build the SKU within the query itself. All it would take is a second column, again "idx", in the p queries. The join would be trickier, as you need to concatenate the idx columns as you go. (SELECT q.idx & p.idx AS idx, ...)

@Rick,

It's definitely cool. I looked at it another time and I saw what it was doing. Still, very clever! I might roll your solution into another blog post (unless you do it first) cause I think its really interesting.

I can't believe you just typed all that into the comments and it ran when I pasted it into a CFM file... dang!

Just so that I can point out the giant gaping hole in my own strategy ...

The problem with my solution is its own elegance -- since we're using set-based operations (QoQ) to do all of our work, we're going to chew through memory. An iterative solution would use far less memory and far fewer processor cycles.

<!--- Use an array of arrays instead --->
<cfset arrLists = arrayNew(1)>
<cfset arrayAppend(arrLists, listToArray("Blue,Black"))>
<cfset arrayAppend(arrLists, listToArray("Small,Medium,Large"))>
<cfset arrayAppend(arrLists, listToArray("Mens,Womens"))>
<cfset arrayAppend(arrLists, listToArray("Full Sleeve,Short Sleeve"))>
<!--- a bit of setup --->
<cfset listCount=arrayLen(arrLists)>
<cfset counts=listToArray(repeatString("1,",listCount))>
<cfset lengths=arrayNew(1)>
<cfset hand=arrayNew(1)>
<cfloop from="1" to="#listCount#" index="i">
<cfset lengths[i]=arrayLen(arrLists[i])>
<cfset hand[i]=arrLists[i][1]>
</cfloop>
<cfset results=arrayNew(1)>
<cfset finger=listCount>
<cfloop condition="finger gt 0">
<cfset arrayAppend(results, arrayToList(hand,", "))>
<cfset finger=listCount>
<cfset continue=true>
<cfloop condition="continue">
<cfset counts[finger]=(counts[finger] MOD lengths[finger]) + 1>
<cfset hand[finger]=arrLists[finger][counts[finger]]>
<cfif counts[finger] gt 1>
<cfset continue=false>
<cfelse>
<cfset finger=finger-1>
<cfset continue=(finger gt 0)>
</cfif>
</cfloop>
</cfloop>
<cfdump var="#results#">

Short explanation: we count on our fingers just like you were taught in elementary school. Except in this case, each finger can be in any number of positions.

We keep a running total ("counts") of each finger's position. We shift the position of our rightmost finger and if we need to reset it we move on to the next and repeat.

Since far more stays the same through each loop than changes, we use our hand to hold the item at the current position of each finger, only changing out the ones that are needed.

We stop when we run out of fingers.

My tests show that the iterative approach is roughly 50 times faster and uses far less memory. Of course, it's also far less sexy. YMMV.

@Rick,

I don't think the QoQ would be too much of a drain on memory as you still only have two queries at any time (well, three, I suppose if you could the during-build before it overwrites the name variable name). But, speed might definitely be an issue. As awesome as query of queries are, they are definitely not speedy.

I like your new solution too. I think that is something that I was trying to move towards as well. In my solution, I am sort of using the "finger" technique in that I am "incrementing" a list index per "place" then moving left (on the hand) when I need to.

Good stuff all around.

This array declaration does not work at all for me:

<cfset arrLists = [
"Blue,Black",
"Small,Medium,Large",
"Mens,Womens",
"Full Sleeve,Short Sleeve"
] />

is this a CF8 only thing?

I am using CF MX 7

and get this error:

Invalid CFML construct found on line 1 at column 19.
ColdFusion was looking at the following text:

[

The CFML compiler was processing:

* a cfset tag beginning on line 1, column 2.

@Bob,

Yes, that is a ColdFusion 8 implicit array creation. It would be similar to the CF7:

<cfset arrLists = ArrayNew( 1 ) />
<cfset ArrayAppend( arrLists, "Blue,Black" ) />
<cfset ArrayAppend( arrLists, "Small,Medium,Large" ) />
<cfset ArrayAppend( arrLists, "Mens,Womens" ) />
<cfset ArrayAppend( arrLists, "Full Sleeve,Short Sleeve" ) />

There are gonna be some other CF8 only things in the code that throw some issues... like the ++ and -- self incrementer and decrementer operators and the array looping.

These can all be replaced with CF7 specific features.