8 Replies Latest reply on Jun 18, 2012 4:31 PM by Trevorׅ

    Returning unique items of an Array

    Trevorׅ Adobe Community Professional

      I would like to know how to get combanations of any Array without repeats of same elements in a different order.

       

      The array is made of object properties and could have variable number of elements.

       

      In other words if I have an Array of for example 2 elements

      [a, b]

      I want to receive 3 new sub arrays

      1) [a]

      2) [b]

      3) [a, b]

       

      I don't want to receive [b, a] as that has the same elements as [a, b] just in a different order.

       

      Well if there just 2 elements in the array then that's easy enough but when there are more then it's beyond me!!

       

       

      An Array of for example 4 elements

      [a, b, c, d]

      would need to produce a new array made of the following 15 sub arrays

       

      1) [a]

      2) [b]

      3) [c]

      4) [d]

      5) [a, b]

      6) [a, c]

      7) [a, d]

      8) [b, c]

      9) [b, d]

      10) [c, d]

      11) [a,b, c]

      12) [a, b, d]

      13) [a, c,d]

      14) [b, c, d]

      15) [a, b, c, d]

       

      A 5 element array would give me 24 sub arrays and so on.

       

      I have tried numerous ways with diddlysquat results

       

      Slice, splice and all things nice !!

       

      If any of you could share this trade secret with me, I would much appreciate it.

       

      Trevor

        • 1. Re: Returning unique items of an Array
          Fred Goldman Level 3

          First sort the arrays and then check for duplicates.

          • 2. Re: Returning unique items of an Array
            Trevorׅ Adobe Community Professional

            Hi Fred,

             

            1) I can't make the sub arrays in the first place to sort them!

            2) I'm pretty sure that when they are made by a looping process the "duplicates" can be avoided in the first place with out the need to sort them afterwards.

             

             

            I noticed an obious pattern for the  results that I need.

             

            I shall illustrate the pattern with an eyample.

             

            myArray = [Red, Green, Blue, Black]

            Y = myArray.length // = 4

             

            In a array of  Y elements there a Y number of single element sub arrays.

             

            1) [Red]

            2) [Green]

            3) [Blue]

            4) [Black]

             

            there are Y-1+Y-2+Y-3 = (4-1+4-2+4-3)  = 6 two element arrays

            That is a series of  (((Y-1)*Y)-((Y-1)*Y)/2)

            ((4-1)*4)  - (((4-1)*4)/2) = (3*4) - (3*4/2)   = 12 - 6 = 6 two element arrays

             

            1) [Red, Green]

            2) [Red, Blue]

            3) [Red, Black] // untill here a loop of  Y-1 (=3) 2 element arrays

            4) [Green, Blue] // start loop here at 2nd element to avoid [Green, Red] which is "the same" as [Red, Green] which we already have.

            5) [Green, Black] //untill here another loop of Y-2 (=2) 2 element arrays

            6) [Blue, Black] // A "loop" of Y-3 (=1) 2 element array.

            The we have a series of  Y-2+Y-3 = (4-2+4-3) = 3 three element arrays

            That is ((Y-2)*Y)-(((Y-2)*Y)/2) = ((4-2)*4)-(((4-2)*4)/2)  = ((2*4) - ((2*4)/2)  = 8-4 = 4 3element array

             

            1) [Red, Green, Blue]

            2) [Red, Green, Black]

            3) [Red, Blue, Black] // 3 till here!!

            4) [Green, Blue, Black]

             

            And finally 1 element of  Y (4) Arrays

            1) [Red, Green, Blue, Black]

             

            In total (Y*Y)-1 = 15 Sub arrays

             

            I'm sure this information hold the key to the solution but can't get any further.

            • 3. Re: Returning unique items of an Array
              tobias.wantzen

              Trevor!

               

              Your search term in google should be something like »generate tupels« or »algorithm tuples« ...

              This is from http://foren.activevb.de/archiv/vb-classic/thread-394022/beitrag-394128/Re-Algorithmus-Tup el-generieren/ (I translated the comments to english):

               

               

                Dim i As Long, j As Long, N As Long, Kombi As Long
                Dim Z1() As Long, Element() As String
                Dim Digit() As String, Lsg() As String
                
                N = 4   ' number of elements
                Kombi = 2 ^ N - 1   ' number of combinations
                ReDim Element(N - 1), Digit(N - 1), Z1(N - 1), Lsg(Kombi - 1)
                
                ' generate elements
                For i = 0 To N - 1
                  Element(i) = Chr$(Asc("A") + i)
                Next i
                
                ' generate solutions
                For i = 0 To Kombi - 1
                  For j = 0 To N - 1
                    Z1(j) = Z1(j) Xor 1
                    If Z1(j) Then
                      Digit(j) = Element(j)
                      Exit For
                    End If
                    Digit(j) = ""
                  Next j
                  Lsg(i) = Join(Digit, "")
                Next i
                
                ' output solutions
                For i = 0 To Kombi - 1
                  Debug.Print Lsg(i)
                Next i
              

              The Code is VB, but I think you can figure out, how to transform to JS.

               

              Cheers

              Tobias

              1 person found this helpful
              • 4. Re: Returning unique items of an Array
                [Jongware] Most Valuable Participant

                1. A nice trick to get unique elements is to store them as keys in an object. Something like

                 

                uniqueObject = {};

                myArray = [Red, Green, Blue, Black]

                for (i=0; i<myArray.length; i++)

                  uniqueObject[myArray[i]] = true;

                 

                for all of your myArrays -- I understand you have more than one.

                 

                This works because every name inside an object will be unique. The value itself is inconsequential.

                 

                2. If you have a list of items [a,b,c, ... n] and you want all permutations, you can view it as a binary number, where each element is present (1) or absent (0). That way you can quickly calculate the number of permutations: [a,b,c, .. n] will have 2ⁿ permutations. (But you want to use 2ⁿ-1, because all zeros should not be in there).

                 

                To get the list of all permutations, consider this: all the variations of a list can easily be found by realizing that the variations for a list [a,b,c, ... n] are the list itself, plus each list minus one of its elements. The latter can be recursively applied!

                 

                In sort of pseudo-code ('cause I thought it over while waiting for the train to work but now I am here I should be doing some work )

                 

                allPermutations = getPermutation(list)

                {

                  var totallist = [list];

                  for (item=0; item<list.length; item++)

                    totallist = totallist.concat (getPermutation(list - item));

                  return totallist
                }

                • 5. Re: Returning unique items of an Array
                  Trevorׅ Adobe Community Professional

                  Thanks Tobias and Jongware

                   

                  Tobias:

                   

                  Unfortunately my understanding of VB isn't even VB it's VB i.e it's not even Very Basic it's Very Bad.

                  I learnt Basic on a Sinclair ZX81 back in 1981 but never kept up with things when the V got added to the B and a few years, err, decades have passed since then.

                  Don't Spend time converting to js, as you wrote I should be able to manage  to convert it myself. (With somewhat more difficulty that you thought)

                   

                  Jongware:

                   

                  I followed and liked the logic of your 2nd point but the 1st point was double Dutch to me

                   

                  Could you explain it a little more.

                   

                  I shall hopefully come up with a concrete code in the next day or 2 (Very busy now!) and shall post it then.

                  If I don't manage then I shall resort to begging.

                   

                  Regards Trevor

                  • 6. Re: Returning unique items of an Array
                    [Jongware] Most Valuable Participant

                    Hmmmm ... mmm ... it sounded so good in my head -- but I hit a snag!

                     

                    The first part relies on Javascript's unique internal object handling. You can store any string as key in an object -- a variable name --, and all keys must be unique -- you can only have one property 'geometricBounds' for every object of type Rectangle. So even if you add a key twice, or three times, or 15,543 times, it will only be stored once. Then you can interrogate the object to return all of its key names. See the makeUniqueList function.

                     

                    The snag in question is the result of 'makePermutations'. Given three letters 'a', 'b', and 'c', it correctly returns 'abc', 'ab', 'bc', and 'ac' by removing one item at a time. However, in the next round it does so again for each of the intermediate results 'ab', 'bc' and 'ac', so you get a next generation list of 'a','b', 'b','c', 'a','c'. For 4 unique sets, you'd get three duplicate singles and two duplicate tuplets; and so on!

                     

                    So far my recursion idea. (That's why "recursion" is derived from the word "curse".)

                     

                    var myArray = [ 'a', 'b', 'c', 'b', 'b', 'b','b', 'c' ];
                    uniqueArray = makeUniqueList(myArray);
                    alert (uniqueArray);
                    permutationArray = makePermutations (uniqueArray);
                    alert (permutationArray.join('\r'));
                    
                    function makeUniqueList (in_array)
                    {
                    var uniqueObject = {}, i, result = [];
                    for (i=0; i<in_array.length; i++)
                      uniqueObject[in_array[i]] = true;
                    for (i in uniqueObject)
                      result.push(i);
                    return result;
                    }
                    
                    function makePermutations (in_array)
                    {
                    var i,out_array = [], next_array;
                    out_array.push ( [in_array] );
                    for (i=0; i<in_array.length; i++)
                    {
                      next_array = in_array.slice();
                      next_array.splice(i,1);
                      if (next_array.length > 0)
                       out_array = out_array.concat (makePermutations(next_array));
                    }
                    return out_array;
                    }
                    

                     

                    Message was edited by: [Jongware] Obligatory Edit to work around missing Syntax Highlight button bug in Jive. (Any news on that, moderators?)

                    1 person found this helpful
                    • 7. Re: Returning unique items of an Array
                      Marc Autret Level 4

                      Nice challenge!

                       

                      One could try this:

                       

                      function arrayParts(/*arr*/a, r,i,j,t,s,p)
                      // -------------------------------------
                      // Note: a is supposed to contain unique items
                      // [if necessary, apply a makeUnique routine first]
                      {
                          if(! (i = Math.pow(2,a.length)-1) ){ return null; }
                          (r=[]).toString = function(){return this.join('\r');};
                      
                          while(i--)
                              {
                              r[i] = t = [];
                              s = (1+i).toString(2);
                              p = (j=s.length) - 1;
                              while( j-- ) '1'==s[j] && t[t.length]=a[p-j];
                              }
                      
                          // Reorder by length [if needed!]
                          // ---
                          r.sort( function(x,y){return x.length-y.length;} );
                      
                          return  r;
                      }
                      
                      // Sample code
                      // ---
                      var arrTest = ['Blue','Red','Yellow','Green','Black'];
                      alert( arrayParts(arrTest) );
                      

                       

                      Really not optimized, but it was pretty fun to write ;-)

                       

                      @+

                      Marc

                      • 8. Re: Returning unique items of an Array
                        Trevorׅ Adobe Community Professional

                        Marc,

                         

                        Spectacular! Works great!  Short and sweet!

                         

                        Jongware,

                         

                        Nearly Spectacular! Nearly works great!

                        Still interested to see the final code if you finish it off.

                         

                        The uniqueObject function is much clearer to me now.

                         

                        Important:


                        Jongware wrote:

                         

                        Message was edited by: [Jongware]  Obligatory Edit to work around missing Syntax Highlight button bug in Jive. (Any news on that, moderators?)

                         

                        After seeing this post http://forums.adobe.com/thread/999431?start=0&tstart=0 a collection off a few hundred complaints about the new skin one sees the solution to the "Edit" problem

                         

                        There it writes in bright orange letter on a dull and dreary grey backround

                         

                        "PLEASE NOTE: You may need to clear your browser cache to see some of the updates/fixes as they are released in the forum."

                         

                        On firefox you need to press Ctrl (Option I guess on a Mac) Shift Delete to get the clear history panel

                        ScreenShot032.png

                        As far as I know the important one to click is the site preferences option.

                        Worked for me. ,

                        Should be a "Sticky topic" and not hidden in some obscure forum that is not even listed on the forums menu!!

                        sums it up, (The lack of publicizing of the fix).

                         

                        Tobias

                         

                        You shall be hearing from me soon !

                         

                        Thanks to all of you,

                         

                        Trevor