Returning unique items of an Array

Report · Jun 17, 2012

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)

2)

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)

2)

3)

4)

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

Report · Jun 17, 2012

First sort the arrays and then check for duplicates.

Report · Jun 17, 2012

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.

Report · Jun 18, 2012

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-Tupel-generie... (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

Report · Jun 18, 2012

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] = 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 =

;

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

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

return totallist
}

Report · Jun 18, 2012

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

Report · Jun 18, 2012

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] = 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?)

Report · Jun 18, 2012

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 = t = [];
        s = (1+i).toString(2);
        p = (j=s.length) - 1;
        while( j-- ) '1'==s && 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

Report · Jun 18, 2012

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

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

Returning unique items of an Array

1 Correct answer

Photos