Friday Puzzler - Listing all posibilities of a set

coldfusion (This post is more than 2 years old.)

Today's puzzle is pretty simple, but I'm curious to see how people solve it. Write a UDF that takes two arguments. The first argument is a set - and by that I mean a list of possible values. So a set could be: A,B,C. The second argument is the length of a string to generate. So given: arrResults = func("A,B,C",2) the result would be an array of every possible string combination. Like so:

AA AB AC BA BB BC CA CB CC

Good luck!

Hire Me!

I'm currently looking for my next role in developer evangelism and advocacy. I have a long history of helping companies work with developers and love to write, create demos, and present at conferences. You can find my resume to learn more and drop me an email (raymondcamden@gmail.com) to reach out.

Support this Content!

If you like this content, please consider supporting me. You can become a Patron, visit my Amazon wishlist, or buy me a coffee! Any support helps!

Want to get a copy of every new post? Use the form below to sign up for my newsletter.

Archived Comments

Comment 1 by Tom Litt posted on 4/27/2007 at 4:18 PM

This is my first go at entering one of these things, so go easy on me...

Is it considered cheating to write two UDFs? Have I _way_ overcomplicated things?

<cffunction name="setfunc" access="public" output="true">
<cfargument name="SetList" required="yes" type="string">
<cfargument name="Depth" required="yes" type="numeric" default="1">
<cfif Arguments.Depth EQ 1>
<cfreturn ListToArray(Arguments.SetList)>
<cfelse>
<cfreturn ArrayCrossJoin(ListToArray(Arguments.SetList),setfunc(Arguments.SetList,Arguments.Depth-1))>
</cfif>
</cffunction>

<cffunction name="ArrayCrossJoin" access="private" output="false">
<cfargument name="Array1" required="yes" type="array">
<cfargument name="Array2" required="yes" type="array">
<cfset var OutputArray = ArrayNew(1)>
<cfset var joinloop = 0>
<cfset var arrayloop = 0>
<cfloop from="1" to="#ArrayLen(Arguments.Array1)#" index="joinloop">
<cfloop from="1" to="#ArrayLen(Arguments.Array2)#" index="arrayloop">
<cfset ArrayAppend(OutputArray,Arguments.Array1[joinloop] & Arguments.Array2[arrayloop])>
</cfloop>
</cfloop>
<cfreturn OutputArray>
</cffunction>

<cfset ThisList = "A,B,C,D">
<Cfset ThisDepth = 2>

<cfdump var="#setfunc(ThisList,ThisDepth)#">

Comment 2 by Brian Panulla posted on 4/27/2007 at 4:51 PM

I assume recursion is fair game? How's this:

<cffunction name="getPermutations" output="false" returntype="array">
<cfargument name="srcArray" type="array" required="true" />
<cfargument name="destItemlength" type="numeric" required="true" />
<cfargument name="destArray" type="array" required="false" default="#arrayNew(1)#" />

<cfset var tempArray = arrayNew(1) />
<cfset var outArray = arrayNew(1) />

<cfset var i = 0 />
<cfset var j = 0 />

<cfif arguments.destItemLength GT 1>
<!--- Go recursive... set aside the results in a temp array as we build the array returned by this invocation --->
<cfset tempArray = getPermutations(arguments.srcArray, arguments.destItemLength - 1, arguments.destArray) />

<!--- Build the output array, prepending each of the original items to the items
in the result of the previous invocation --->
<cfloop index="i" from="1" to="#arrayLen(arguments.srcArray)#">
<cfloop index="j" from="1" to="#arrayLen(tempArray)#">
<cfset arrayAppend(outArray, arguments.srcArray[i] & tempArray[j]) />
</cfloop>
</cfloop>

<cfelseif arguments.destItemLength EQ 1>
<!--- The result is just the source array --->
<cfset outArray = arguments.srcArray />

<cfelse>
<!--- In case the recursion goes awry, don't do anything --->
<cfset outArray = arguments.destArray />
</cfif>

<cfreturn outArray />
</cffunction>

Comment 3 by JohnEric posted on 4/27/2007 at 5:55 PM

@Brian - I would hope that recursion is allowed.

Here's my answer.

<cffunction name="getCombinations" returntype="array" output="false">
<cfargument name="originalSet" type="any" required="true" />
<cfargument name="combinationLen" type="numeric" required="true" />
<cfargument name="delimiter" type="string" default="," />

<cfscript>
var unCombined = '';
var previousResult = '';
var combinations = arrayNew(1);
var i = 0;
var j = 0;

if (isSimpleValue(arguments.originalSet)) {
unCombined = listToArray(arguments.originalSet);
} else if (isArray(arguments.originalSet)) {
unCombined = arguments.originalSet;
}
</cfscript>

<cfif NOT isArray(unCombined)>
<cfthrow errorcode="invalidArg" message="The original set argument must be either an array or a list" />
</cfif>

<cfscript>
//Inductive step, n=1
if (arguments.combinationLen EQ 1)
return unCombined;

//Solve for step n
for(i=1; i LTE arrayLen(unCombined); i=i+1) {
//Solve for step n-1
previousResult = getCombinations(originalSet=unCombined, combinationLen=arguments.combinationLen-1);
for (j=1; j LTE arrayLen(previousResult); j=j+1) {
arrayAppend(combinations, unCombined[i] & previousResult[j]);
}
}

return combinations;
</cfscript>
</cffunction>

Comment 4 by JohnEric posted on 4/27/2007 at 6:00 PM

Oops. Should have kept the previousResult just before the loop instead of inside it.

Comment 5 by JanVC posted on 4/27/2007 at 6:01 PM

Here's my solution:

<cffunction name="pairGen">
<cfargument name="chars" required="yes" type="string">
<cfargument name="depth" required="yes" type="numeric" default="1">
<cfset var letters= arguments.chars>
<cfset var pairs= arguments.depth>
<cfset var result=letters/>
<cfset var n = 0/>
<cfset var m = 0/>
<cfset var o = 0/>
<cfset var tmp = ""/>

<cfloop index="n" from="1" to="#DecrementValue(pairs)#">
<cfset tmp = "">
<cfloop index="m" list="#letters#">
<cfloop index="o" list="#result#">
<cfset tmp = ListAppend(tmp,m&o)>
</cfloop>
</cfloop>
<cfset result = tmp>
</cfloop>

<cfreturn ListToArray(result)>
</cffunction>

<cfdump var="#pairGen('A,B,C',2)#">

Comment 6 by JohnEric posted on 4/27/2007 at 6:16 PM

And here's a non-recursive method.

<cffunction name="getCombinationsNonRecursive" returntype="array" output="false">
<cfargument name="originalSet" type="any" required="true" />
<cfargument name="combinationLen" type="numeric" required="true" />
<cfargument name="delimiter" type="string" default="," />

<cfscript>
var unCombined = '';
var previousResult = '';
var combinations = arrayNew(1);
var i = 0;
var j = 0;
var k = 0;

if (isSimpleValue(arguments.originalSet)) {
unCombined = listToArray(arguments.originalSet, arguments.delimiter);
} else if (isArray(arguments.originalSet)) {
unCombined = arguments.originalSet;
}
</cfscript>

<cfif NOT isArray(unCombined)>
<cfthrow errorcode="invalidArg" message="The original set argument must be either an array or a list" />
</cfif>

<cfscript>
previousResult = unCombined;
combinations = previousResult;
for(i=2; i LTE arguments.combinationLen; i=i+1) {
combinations = arrayNew(1);
for (j=1; j LTE arrayLen(unCombined); j=j+1) {
for (k=1; k LTE arrayLen(previousResult); k=k+1) {
arrayAppend(combinations, unCombined[j] & previousResult[k]);
}
}
previousResult = combinations;
}

return combinations;
</cfscript>
</cffunction>

Comment 7 by Rick Osborne posted on 4/27/2007 at 6:54 PM

Just for your wtf-of-the-day, here's another way to do it:

<cffunction name="combinations" returntype="array" output="false" description="Return an array that is all possible combinations of the given input strings">
<cfargument name="strList" type="string" required="true">
<cfargument name="intLength" type="numeric" required="true">
<cfset var result=ArrayNew(1)>
<cfset var Q1=QueryNew("i")>
<cfset var Q0=Q1>
<cfset var i=0>
<cfif Arguments.intLength GT 0>
<cfset Q0=QueryNew("i")>
<cfloop list="#Arguments.strList#" index="i">
<cfset QueryAddRow(Q0)>
<cfset QuerySetCell(Q0,"i",i,Q0.RecordCount)>
</cfloop>
<cfset Q=Q0>
<cfloop from="2" to="#Arguments.intLength#" index="i">
<cfset Q1=Q0>
<cfquery dbtype="query" name="Q">
SELECT q.i AS i, q1.i AS r
FROM q, q1
ORDER BY q.i, q1.i
</cfquery>
<cfloop query="Q">
<cfset QuerySetCell(Q,"i",Q.i & r,CurrentRow)>
</cfloop>
</cfloop>
<cfset result=ListToArray(ValueList(Q.i))>
</cfif>
<cfreturn result>
</cffunction>

Having the QoQ in a loop instead of just a dynamic QoQ with a bunch of aliased tables is necessary because CF doesn't like joining more than 2 tables. Similarly, the cfloop after the QoQ is because CF doesn't like doing string concatenation, so we have to do it manually.

Comment 8 by JanVC posted on 4/27/2007 at 6:58 PM

@Rick : Awesome... : )

Comment 9 by Ben Nadel posted on 4/27/2007 at 9:41 PM

Here is my solution:

http://www.bennadel.com/ind...

It uses two loops and the MOD operator.

Comment 10 by Raymond Camden posted on 4/27/2007 at 10:10 PM

All nice answers guys. I promise next week it will "really" be a 5 minute answer. ;)

Oh wait - I'll be at cf.Objective. Never mind then. :)

Comment 11 by Phil posted on 4/27/2007 at 10:14 PM

Here's mine, purely mathematical:

<cffunction name="getSet" returntype="array" output="false">
<cfargument name="set" type="string" required="true">
<cfargument name="length" type="numeric" required="true">

<cfset var rows = ListLen(arguments.set)^arguments.length>
<cfset var result = ArrayNew(1)>
<cfset var wholeNum = rows/ListLen(arguments.set)>

<cfloop from="1" to="#rows#" index="i">
<cfset result[i] = "">
<cfloop from="1" to="#arguments.length#" index="j">
<cfset result[i] = result[i] & ListGetAt(arguments.set, Fix(i / (rows/(ListLen(arguments.set)^j))) mod ListLen(arguments.set) + 1)>
</cfloop>
</cfloop>

<cfset ArraySort(result,"text")>
<cfreturn result>
</cffunction>

<cfdump var="#getSet('A,B,C',2)#">

Comment 12 by Ben Nadel posted on 4/27/2007 at 10:20 PM

@Phil,

Sweeet, glad to see someone else using the MOD operator. When I see a sequence, the first thing I think is MOD. I was a little surprised that no one else tried it.

@Ray,

What fun would 5 minutes be :)

Comment 13 by Phil Duba posted on 4/27/2007 at 10:34 PM

@Ben - I saw yours right after I posted mine. I guess it was my engineering background that made me go to a math solution, :).

Comment 14 by Ben Nadel posted on 4/27/2007 at 10:41 PM

@Phil,

Yeah, I'm engineering too, but computer science (not hard core engineering). The MOD stuff was KILLING me at first. My sequence was always one off. I almost gave up - luckily some Chinese food helped refuel the brain :)

Comment 15 by jason posted on 4/28/2007 at 8:54 AM

sorry to interrupt, but can you guys explain mod to a CF newbie?

thank you

Comment 16 by Ben Nadel posted on 4/28/2007 at 8:28 PM

Sure thing, MOD is an mathematical operator like * or /. What MOD does is it divides one number into the other and returns what ever remains.

For example, 7 MOD 2 = 1. 2 divides into 7 three times (2*3=6). After 2 goes into t7 3 times, only 1 is left (7-6=1).

To say it another way, it's the remainder of one number evenly divided into another number.

You can never do anything MOD 0 (zero) because numbers cannot be divided by zero. Anthing MOD 1 is zero since 1 evenly divides into any number.

Does that help at all?

Comment 17 by Raymond Camden posted on 4/28/2007 at 8:40 PM

To follow up on this - one common use of mod is to do something for even odd rows:

<cfif x mod 2>
even
<cfelse>
odd
</cfif>

This is useful when looping over a query and doing alternating background colors.

Comment 18 by Elliott Sprehn posted on 4/30/2007 at 1:43 PM

I know I'm late to this, but I thought I'd be nice to share my solution so other people who happen to read the entry can see different ways to do it, and share some performance findings as well.

The results of some benchmarking showed the below results in relation to the permute() solution shown at the end of this post:

-3x getCombinationsNonRecursive
-2x GetPermutations
1x permute
2x getSetOp
3x getSet
5x AllSets
10x pairGen

Such that on average this method was 10x faster than pairGen() and 3x slower than getCombinationsNonRecursive().

GetPermutations() and getCombinationsNonRecursive() were both very close (~1.5x) and upon inspection look to be O(n) which means the performance difference was likely related to the recursive nature of GetPermutations().

pairGen() was by far the slowest, however this is probably the result of using lists instead of arrays since CF has to determine the position of the elements of the list by parsing the string each time.

getSetOp() was just an optimized version of getSet(), done by removing some of the extraneous mathematical logic, which showed to be about twice as fast as getSet() on average.

[1] http://enfinitystudios.thap...

Anyway, Kudos to JohnEric and Brian Panulla for the awesome O(n) solutions! :)

<cffunction name="permute" returntype="array" output="false">
<cfargument name="list" type="string" required="true">
<cfargument name="len" type="numeric" required="true">

<cfscript>
var set = listToArray(arguments.list);
var length = arrayLen(set);
var total = length^len;
var result = arrayNew(1);
var shift = total;
var i = 0;
var j = 1;

arraySort( set, "text" );
arraySet( result, 1, total, "" );

for( i=1; i lte arguments.len; i = i + 1 ) {
shift = shift / length;
for( j=1; j lte total; j = j + 1 ) {
result[j] = result[j] & set[1];
if( not (j mod shift) ) {
arrayAppend( set, set[1] );
arrayDeleteAt( set, 1 );
}
}
}

return result;
</cfscript>
</cffunction>

Comment 19 by Rick Osborne posted on 5/9/2007 at 1:37 AM

For completeness, I should point out that I was wrong about QoQ not being able to do string concatenation. It can do it, it's just grumpy about it.

For qualified table names and columns (table_name.column_name) if you try to do string concatenation the official way you might get the error "Incorrect select column, {whatever} cannot be followed by ||". The way around this is to wrap the fully-qualified column in parenthesis.

That is, this generates the error:
SELECT q.i || q1.i AS i

But this does not:
SELECT (q.i) || q1.i AS i

In tests against getCombinationsNonRecursive above, the QoQ version is about 6x-8x slower.

Comment 20 by vyp posted on 6/7/2007 at 1:18 PM

A nice one...

Was wondering if possible not to show repeating letters..

Example: A,B,C

Shows:

ABC
ACB
... so on

and not

AAA
BBB
AAC
... so on

Thanks in advance...