8 Replies Latest reply on Jan 6, 2007 3:10 AM by Newsgroup_User

    Generating unique combinations

    Level 7
      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[j],',')>
      <cfelse>
      <cfset numOfCombos = numOfCombos * listlen(myArray[j],',')>
      </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[k] = listappend(newArray[k],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.
        • 1. Re: Generating unique combinations
          Dan Bracuk Level 5
          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.
          • 2. Generating unique combinations
            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
            • 3. Re: Generating unique combinations
              Level 7
              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
              • 4. Re: Generating unique combinations
                mvierow
                Give this a look...

                • 5. Re: Generating unique combinations
                  Level 7
                  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
                  • 6. Re: Generating unique combinations
                    Level 7
                    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
                    • 7. Re: Generating unique combinations
                      Level 7
                      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.
                      • 8. Re: Generating unique combinations
                        Level 7
                        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.