Friday Puzzler - Listing all posibilities of a set
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
2AB
3AC
4BA
5BB
6BC
7CA
8CB
9CC
Good luck!
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)#">
<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>
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>
<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)#">
<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>
<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.
http://www.bennadel.com/index.cfm?dax=blog:661.vie...
It uses two loops and the MOD operator.
Oh wait - I'll be at cf.Objective. Never mind then. :)
<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)#">
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 :)
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 :)
thank you
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?
<cfif x mod 2>
even
<cfelse>
odd
</cfif>
This is useful when looping over a query and doing alternating background colors.
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>
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.
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...