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)#">

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>

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

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

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)#">

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>

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.

@Rick : Awesome... : )

Here is my solution:

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

It uses two loops and the MOD operator.

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

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)#">

@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 :)

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

@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 :)

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

thank you

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?

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.

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>

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.

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