## Friday Puzzler - Listing all posibilities of a set

04-27-2007 3,839 views ColdFusion

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:

1AA
2AB
3AC
4BA
5BB
6BC
7CA
8CB
9CC

Good luck!

These comments will soon be imported into Disqus. To add a comment, use Disqus above.
• Tom Litt #
Commented on 04-27-2007 at 7:18 AM
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)#">
• Commented on 04-27-2007 at 7:51 AM
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>
• JohnEric #
Commented on 04-27-2007 at 8:55 AM
@Brian - I would hope that recursion is allowed.

<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>
• JohnEric #
Commented on 04-27-2007 at 9:00 AM
Oops. Should have kept the previousResult just before the loop instead of inside it.
• Commented on 04-27-2007 at 9:01 AM
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)#">
• JohnEric #
Commented on 04-27-2007 at 9:16 AM
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>
• Commented on 04-27-2007 at 9:54 AM
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 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.
• Commented on 04-27-2007 at 9:58 AM
@Rick : Awesome... : )
• Commented on 04-27-2007 at 12:41 PM
Here is my solution:

It uses two loops and the MOD operator.
• Commented on 04-27-2007 at 1: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. :)
• Commented on 04-27-2007 at 1: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)#">
• Commented on 04-27-2007 at 1: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 :)
• Commented on 04-27-2007 at 1: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, :).
• Commented on 04-27-2007 at 1: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 :)
• jason #
Commented on 04-27-2007 at 11:54 PM
sorry to interrupt, but can you guys explain mod to a CF newbie?

thank you
• Commented on 04-28-2007 at 11:28 AM
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?
• Commented on 04-28-2007 at 11:40 AM
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.
• Commented on 04-30-2007 at 4:43 AM
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.thaposse.net/personal/permu...

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>
• Commented on 05-08-2007 at 4:37 PM
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.
• vyp #
Commented on 06-07-2007 at 4:18 AM
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