2

I know that is a horrible title. I am not trained in CS so I haven't taken an algorithms course to know what this might be.

Let me explain:

I have an array that holds sets of 6 numbers:

 var theList = [{[1,2,3,4,5,6],[1,2,3,4,5,7],[1,2,3,4,6,7],[1,3,4,5,6,7]}];

This array can be large. I then go through each item in the array and count the occurrences of the different groups of three in there. ie 1 2 3 appears 3 times, 2 3 4 appears 3 times, etc. I hold this information in another array with the count it appears as index 3 :

var countList = [{[1,2,3,3],[2,3,4,3]}]

The next thing I do is I go through each group of six (from theList) and I check my countList for the number of occurrences each of the groups of three. If they are all greater than 1, I delete this group of six, decrease the count in my countList and go on to the next number.

This seems to work, however the numbers that remain contain numerous amounts of groups of three from the higher end of the numbers. For instance if the numbers are from 1-10, when the calculations are complete there are few occurrences of the lower groups of three ([1,2,3],[1,2,4][1,2,5]), etc but there are many occurrences of the higher groups of three ([6,7,8],[7,8,9][8,9,10]) so what I end up is a bunch of groups of six that start with low numbers that seem to be taken out from the duplicate search, but they all end in the same few high numbers.

My take on it is that because the countList is sorted and the groups of six list (theList) is sorted, it "sees" those lower groups of threes more often and removes the sixes with them, but by the time it gets to the higher numbers the lower ones have all been removed so they "have" to be there.

Is there an algorithm I can look into for this?

I apologize if this is confusing, and thanks for the help.

NiteTrip
  • 198
  • 1
  • 1
  • 10

1 Answers1

1

As you state, since theList is sorted, you have a bias of removing lower runs than higher runs. If you would like symmetry, then one way would be to randomly shuffle theList before starting the removal phase.

Randomly shuffling a (Javascript) array is a well-known problem. See this community Wiki question, for ready-to-use answers.

Community
  • 1
  • 1
Ami Tavory
  • 74,578
  • 11
  • 141
  • 185
  • Thank-you. I had thought of randomizing it, but I was wondering if this is some kind of well-known algorithm that I could research. – NiteTrip Jun 28 '15 at 19:33
  • I am going to mark this as the answer. I randomized it and it is working very well, and it gives me different answers sometimes, meaning sometimes it will remove all but x number of elements each time and x can be a different value. I am looking to get by with just the minimum amount of elements and I can quickly find that just by running through the algorithm a few times. – NiteTrip Jun 28 '15 at 22:31