Generating unique combinations

[Newsgroup_User]

I am building a product configuration module as part of a custom
e-commerce site and I am trying to wrap my brain around a teasing little
problem. When a product is added into the system, the system
administrator is able to select what options are available for that
product. These options are supplied as strings of numbers in the form
scope (by selecting from checkboxes). Each option will have it's own set
of numbers. For example a shirt may be available in three sizes (S M L)
and two colours (blue and red) which would be passed through to the form
like so: 1,2,3 for the sizes and 55,66 for the colours. So far, so good.

What I need to be able to do is generate the unique combinations of
options for each product by selecting one number from each string and
generating a unique combination. These values are to be then stored in a
new single dimension array. I am able to work out the number of unique
combinations (in the above example this would be 6), however I am having
difficulties in generating the unique combos. So far I have the
following code:

<!--- Dummy values for testing (this represents the form values that
would be passed in)--->
<cfset myArray = arraynew(1)>
<!--- This represents colours --->
<cfset myArray[1] = '22'>
<!--- This represents sizes --->
<cfset myArray[2] = '32,33,34,35,36,37'>
<!--- This represents cut (regular/long etc) --->
<cfset myArray[3] = '6,7'>

<!--- Work out the number of unique combinations --->
<!--- Start out at zero --->
<cfset numOfCombos = 0>
<!--- How many sets of options are there... --->
<cfset arrLen = arraylen(myArray)>
<!--- Loop through the sets of options --->
<cfloop from="1" to="#arrLen#" index="j">
<cfif numOfCombos is 0>
<cfset numOfCombos = listlen(myArray,',')>
<cfelse>
<cfset numOfCombos = numOfCombos * listlen(myArray,',')>
</cfif>
</cfloop>

<!--- New Array to hold unique combos --->
<cfset newArray = arraynew(1)>
<!--- Create the number of required array elements --->
<cfloop from="1" to="#numOfCombos#" index="i">
<cfset newArray = ''>
</cfloop>

<!--- Populate new Array with unique combos --->
<cfloop from="1" to="#arrLen#" index="i">
<cfset numOfEach = numOfCombos/(listlen(myArray,','))>
<cfset stepNum = numOfCombos/numOfEach>
<cfloop from="1" to="#listlen(myArray ,',')#" index="x">
<cfset thisValue = listgetat(myArray,x,',')>
<cfloop from="#x#" to="#numOfCombos#" step="#stepNum#" index="k">
<cfset newArray = listappend(newArray,thisValue,',')>
</cfloop>
</cfloop>
</cfloop>

<!--- Output values --->
<!--- Original data --->
<cfdump var="#myArray#" label="myArray - Original Data">
<!--- Number of unique combos --->
<p>Number Of Unique Combos: <cfoutput>#numOfCombos#</cfoutput></p>
<!--- This should be the unique combos --->
<cfdump var="#newArray#" label="newArray - Unique Combos">

The above code correctly generates the required number of combinations,
however, not all of them are unique. Please can someone point me in the
right direction?

Thanks,

Richard.

[Dan_Bracuk]

That's a tough one folks. If it was my job, I would probably use a cold fusion query rather than arrays. It would just be easier to figure out what I was doing if I had column names instead of column numbers.

Using your data of 3 sizes (S,M.L), 2 colours (red, blue), and 2 cuts (reg, wide), I would try something like this.

Build a query with 3 columns, size, colour, and cut. Then add 12 empty rows ( 3 * 2 * 2).

Then I would populate the columns one by one. the size column gets S in rows 1, 4, 7, and 10, M in rows, 2, 5, 8, and 11, and L in 3, 6, 9, and 12. Do the same for each column and you have your unique combos. Plus it is easy to loop through a query for whatever the next step is.

[monkey_woo_too]

if you want to get all the possible combinations i would use sql.

use a function to create a temporary table of one column with the values from a list as the rows for each of your lists.

then cross join those tables to create a recordset with all possible combinations

select distinct a.id [size], b.id color, c.id cut
from splitVarcharList('S,M,L') as a
cross join splitVarcharList('red,blue') as b
cross join splitVarcharList('reg,wide') as c

*i wish i could attach a file*
here is a link to a post with the code of my splitVarCharList
http://www.cfguru.org/index.cfm/2006/6/1/Splitting-a-list-in-SQL

[Newsgroup_User]

This was an interesting question.

Here's another proof-of-concept which borrows from and extends both Dan's
and MWT's solutions to allow for more than three categories of variants.
Obviously their solutions also could be augmented to achieve this, with a
small amount of work.

It shouldn't take too much to massage your data structures to accommodate
this logic.

<cfscript>
stData = structNew();
stData["waist"] = listToArray("28,30,32,34,36");
stData["colour"] = listToArray("Blue,Black,Brown,Charcoal");
stData["length"] = listToArray("29,31,33");
stData["cut"] = listToArray("straight,loose,boot");
stData["weight"] = listToArray("5,7,9.5,10,11.5,12,14.5");
// simply add more keys to add more combos

// load dummy data
stQueries = structNew();
for (sCat in stData){
stQueries[sCat] = queryNew(sCat);
for (iVariant=1; iVariant le arrayLen(stData[sCat]); iVariant=iVariant+1)
{
queryAddRow(stQueries[sCat]);
querySetCell(stQueries[sCat], sCat, stData[sCat][iVariant]);
}
}

// give us a place to start
qMerge = queryNew(""); queryAddRow(qMerge);
</cfscript>

<cfloop item="sCat" collection="#stQueries#">
<!--- need to do this as QoQ cannot handle complex query-names --->
<cfset sQueryName = "q_#sCat#">
<cfset "#sQueryName#" = stQueries[sCat]>

<!--- and need to cross-join only two queries @ a time as QoQ can only
handle two at once (SUCK!) --->
<cfquery name="qMerge" dbtype="query">
select distinct qMerge.*, #sQueryName#.#sCat# as #sCat#
from qMerge, #sQueryName#
</cfquery>
</cfloop>
<cfdump var="#qMerge#">

--
Adam

[mvierow]

Give this a look...

[Newsgroup_User]

Dan Bracuk wrote:
> That's a tough one folks. If it was my job, I would probably use a cold fusion
> query rather than arrays. It would just be easier to figure out what I was
> doing if I had column names instead of column numbers.
>
> Using your data of 3 sizes (S,M.L), 2 colours (red, blue), and 2 cuts (reg,
> wide), I would try something like this.
>
> Build a query with 3 columns, size, colour, and cut. Then add 12 empty rows (
> 3 * 2 * 2).
>
> Then I would populate the columns one by one. the size column gets S in rows
> 1, 4, 7, and 10, M in rows, 2, 5, 8, and 11, and L in 3, 6, 9, and 12. Do the
> same for each column and you have your unique combos. Plus it is easy to loop
> through a query for whatever the next step is.
>

Thanks Dan,

Richard

[Newsgroup_User]

monkey woo too wrote:
> if you want to get all the possible combinations i would use sql.
>
> use a function to create a temporary table of one column with the values from
> a list as the rows for each of your lists.
>
> then cross join those tables to create a recordset with all possible
> combinations
>
> select distinct a.id [size], b.id color, c.id cut
> from splitVarcharList('S,M,L') as a
> cross join splitVarcharList('red,blue') as b
> cross join splitVarcharList('reg,wide') as c
>
> *i wish i could attach a file*
>
>
>

Thanks, monkey woo too!

Richard

[Newsgroup_User]

Adam Cameron wrote:
> This was an interesting question.
>
> Here's another proof-of-concept which borrows from and extends both Dan's
> and MWT's solutions to allow for more than three categories of variants.
> Obviously their solutions also could be augmented to achieve this, with a
> small amount of work.
>
> It shouldn't take too much to massage your data structures to accommodate
> this logic.
>
> <cfscript>
> stData = structNew();
> stData["waist"] = listToArray("28,30,32,34,36");
> stData["colour"] = listToArray("Blue,Black,Brown,Charcoal");
> stData["length"] = listToArray("29,31,33");
> stData["cut"] = listToArray("straight,loose,boot");
> stData["weight"] = listToArray("5,7,9.5,10,11.5,12,14.5");
> // simply add more keys to add more combos
>
> // load dummy data
> stQueries = structNew();
> for (sCat in stData){
> stQueries[sCat] = queryNew(sCat);
> for (iVariant=1; iVariant le arrayLen(stData[sCat]); iVariant=iVariant+1)
> {
> queryAddRow(stQueries[sCat]);
> querySetCell(stQueries[sCat], sCat, stData[sCat][iVariant]);
> }
> }
>
> // give us a place to start
> qMerge = queryNew(""); queryAddRow(qMerge);
> </cfscript>
>
> <cfloop item="sCat" collection="#stQueries#">
> <!--- need to do this as QoQ cannot handle complex query-names --->
> <cfset sQueryName = "q_#sCat#">
> <cfset "#sQueryName#" = stQueries[sCat]>
>
> <!--- and need to cross-join only two queries @ a time as QoQ can only
> handle two at once (SUCK!) --->
> <cfquery name="qMerge" dbtype="query">
> select distinct qMerge.*, #sQueryName#.#sCat# as #sCat#
> from qMerge, #sQueryName#
> </cfquery>
> </cfloop>
> <cfdump var="#qMerge#">
>

Thanks Adam, this looks like a real winner!

Richard.

[Newsgroup_User]

mvierow wrote:
> Give this a look...
>
>
>
> <cfloop from="1" to="#arrLen#" index="i">
> <cfset numOfItem = listlen(myArray )>
> <cfset numOfEach = numOfCombos/numOfItem>
> <cfloop from="0" to="#numOfItem-1#" index="x">
> <cfset thisValue = listgetat(myArray,x+1)>
> <cfloop from="1" to="#numOfEach#" index="k">
> <cfset newArray[k+x*numOfEach] =
> listappend(newArray[k+x*numOfEach],thisValue)>
> </cfloop>
> </cfloop>
> </cfloop>
>

Thanks, mvierow!

Richard.