Skip to main content
Ben Nadel at the New York ColdFusion User Group (May. 2009) with: Gert Franz and Peter Bell and Mark Drew
Ben Nadel at the New York ColdFusion User Group (May. 2009) with: Gert Franz ( @gert_railo ) Peter Bell ( @peterbell ) Mark Drew ( @markdrew )

Ask Ben: Iterating Over An Unknown Number Of Nested Lists

By 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.

Want to use code from this post? Check out the license.

Reader Comments

153 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>

15,640 Comments

@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.

153 Comments

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, ...)

15,640 Comments

@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!

153 Comments

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.

15,640 Comments

@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.

1 Comments

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.

15,640 Comments

@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.

I believe in love. I believe in compassion. I believe in human rights. I believe that we can afford to give more of these gifts to the world around us because it costs us nothing to be decent and kind and understanding. And, I want you to know that when you land on this site, you are accepted for who you are, no matter how you identify, what truths you live, or whatever kind of goofy shit makes you feel alive! Rock on with your bad self!
Ben Nadel