Dominant number in array

Hi all!

I am trying to find the dominant element of an array. My idea is to scan the original array and put every individual element in another array. If there is already the element I increase a counter. When counter>Array.length/2 then it is the dominant.
This should work with any array.

my effort so far
function mainFunc() {
var result = 0;
var myArray=[4,5,6,4,2,4,5,6,7];
//result = test(myArray);
//alert("{ " + myArray + " } --> " + result);
}

function test(A) {

var tempArray = new Array;

for(var i=0;i<A.length;i++){
// 1. check if A[i] exists in tempArray
for(var j=0;j<tempArray.length;j++){
if(A[i]==tempArray[j])
{

}

}

// 2. If A[i] exists, increase counter
if(A[i]!=tempArray[])

// 3. Check if counter > A.length/2
// 4. Return A[i]

// 5. If not, add A[i] to tempArray and set counter=1
//


}

return -1;
}

I can't find a way to make the second array correctly to extract the element with the correct counter.
Any ideas?

by dominant do you mean most common, like the Mode in maths?

The most common still might not necessarily be > half the elements.

like in 2,3,4,2,3,4,2,1
number 2 is the most common but still 3 instances are not as much as 4 which is half the array length

Yes exactly. I mean more times than the half

Yes but the most common number may not be as common as half of them.
This is my effort and it finds the Mode


var i,j=0,finds=0,found;
var array = [1,4,2,3,4,1,4,2,4,4];
var temparray = new Array();
var counter = new Array();


function mode(){
for(i in array){
found=false;
for(j in temparray){
if(temparray[j]==array[i]){
counter[j]++;
found=true;}
}
if(found==false){
// if array[i] not found in temparray add it and increment the number of finds
temparray[finds]=array[i];
counter[finds]=1;
finds++;}
}
alert("variants found "+finds);

}

mode();
var highestIndex=0;
for(j=0;j<finds;j++){
if(counter[j]>=counter[highestIndex]){
highestIndex=j;}
}

alert("The Mode was"+temparray[highestIndex]);

See http://javascriptexample.net/extobjects83.php for code to find the mode that returns the value in an array (in case two or more numbers all occur the same number of times and more than any other number)

I propose this two lines script with a backreference regular expression
<script type="text/javascript">
//array to test
var arr=[1,41,222,33,40,18,22,41,2,2,41,42,27,41,58];

var lgt=0,nmb='',str=arr.sort().join(',').replace(/(,\d+)(\1+)/g,
function(a,b){var m;if (lgt<(m=a.length/b.length)) {lgt=m;nmb=b.substr(1)}});
alert('This number '+nmb+' appaers '+lgt+' times');

</script>

var lgt=0,nmb='',str=arr.sort().join(',').replace(/(,\d+)(\1+)/g,
function(a,b){var m;if (lgt<(m=a.length/b.length)) {lgt=m;nmb=b.substr(1)}});
alert('This number '+nmb+' appaers '+lgt+' times');

</script>[/CODE]

That is very clever Monsieur J, how does that work? In particular what does the replace / , \d \1 lot do? Not sure what backslashes do there?

Well, (,\d) means "find a comma followed y one or more digits."

So it will match ",2" or ",41".

The (\1+) means "find the same thing matched by (,\d) one or more times.

So if you have ",2,2,2" that expression will first find ",2" and then see that there are two more occurrences of ",2" and end up matching all of ",2,2,2".

The only flaw in this code is that if NO string is found more than once, it will report back with [b[This number appaers 0 times[/b] (of course, the word should be "appears").

It also doesn't fulfill the requirement that the number be found more than half the time, but that's easy to do in a separate test.

An alert(arr.sort().join(',')) give the string 1,18,2,2,22,222,27,33,40,41,41,41,41,42,58 which is an alphanumeric sort (sort(function(a,b){return a-b}) will assume a numeric increasing sort).

The \1+ after the first sub-pattern (,\d+) in the regular expression /(,\d+)(\1+)/g is a back-reference (1 for first sub-pattern) which allows to match all repeated set of one comma followed by one or more digits.

Then the anonymous function is called only for the duplicated numbers
function(a,b){var m;if (lgt<(m=a.length/b.length)) {lgt=m;nmb=b.substr(1)}}The first argument a is the matched pattern (for example ,2,2 and b the first sub-pattern (the first curly bracket : ,2 in this case). The count of repetitions is also a.length/b.length, we do not use the replace function (See this page for further explanations (https://developer.mozilla.org/en-US/docs/JavaScript/Reference/Global_Objects/String/replace)) but define lgt (for lengthsQuotient) and nmb (for one «dominant» number).

NB : Its easy to define lgt=1 and nmb=arr[0] (with a nmb=+b.substr(1) to store a number) to replace a «This number appaers 0 times» by a better «This number 1 appears 1 time» with an alert('This number '+nmb+' appears '+lgt+' time'+(1<lgt?'s':'');
It is also possible to define the half-length of the array and test only the larger values.

This script can certainly be improved. Especially, with a (,[^,]+) instead of (,\d+) to work with all kind of comma separated values to find duplicates elements...

Apologies English is not my mother tongue

WHOOPS! I am wrong! And that code is fatally flawed!

Change the array to
var arr=[1,41,222,33,40,18,22,41,2,2,42,27,58];
and it gives the answer
This number 2 appears 3 times

Reason: After sorting the array and converting it to a string, you get:

1,18,2,2,22,222,27,33,40,41,41,42,58

And, as I mentioned, when it sees ",2" it looks for repetitions and indeed FALSELY finds 3:

1,18,2,2,22,222,27,33,40,41,41,42,58

Okay...here's a small challenge: Fix that code!

HINT: The fix is nearly trivial.

Though the code is flawed in another way: If there are two sets of numbers with the same count, it only finds the first such. This, too, could be fixed.

W.T.H. This was fun.

My version that fixes both flaws. Not as compact, but easier to understand, I hope:

<script type="text/javascript">
function zonk(a,b)
{
var m = a.length / b.length;
if (lgt <= m )
{
if ( lgt < m ) { nmb = [ ]; }
lgt = m;
nmb.push( b.replace(/,/g,"") );
}
}

//array to test
var arr=[1,41,222,33,40,18,22,41,2,2,42,27,58];

document.write('<hr/>In the array<br/>[' + arr + ']<br/>');

var lgt = 0;
var nmb = [ ];
var str = arr.sort();
str = "," + str.join(',,') + ","
str.replace( /(,\d+,)(\1+)/g, zonk );

document.write('the number(s) ' + nmb.join(" and ") + ' appear(s) '+lgt+' times<hr/>');
</script>

Than you all,

I tried a bit harder. That's my code


function mainFunc() {
var result = 0;
var myArray=[2,4,3,3,3,5,3,5,3,3];
result = test(myArray);
alert("{ " + myArray + " } --> " + result);
}

function test(A) {

var tempArray = new Array;

for(var i=0;i<A.length;i++){
var index = -1;

// 1. check if A[i] exists in tempArray
for(var j=0;j<tempArray.length;j++){

if(A[i]==tempArray[j][0])
{
index = j;
}
}

if(index == -1)
{
tempArray.push(A[i]);
tempArray[tempArray.length-1][1] = 1;
}
else
{
tempArray[index][1]++;
if(tempArray[index][1] > A.length/2)
{
return tempArray[index][1];
}
}


}

return -1;
}

The problem is that tempArray can't get the second dimension.
I need it to be:

tempArray[[4,1],[2,1],[3,2],[5,5]....]
and when the second element of one sub-array is bigger than A.length/2 to return this element.

A shorter script with Old Pedant observations
var arr=[1,41,222,33,41,41,41,40,41,18,41,41,41,22,41,2,2,41,42,27,41,58];

var dominant=null,halfLength=arr.length/2,str=arr.sort().join(',').replace(/(,\d+)(\1+)(?=,)/g,
function(a,b){if (halfLength<=a.length/b.length) {dominant=+b.substr(1)}});

var msg=dominant?'Dominant number : '+dominant:'No dominant number !'
alert(msg);

EDIT : A new corrections repetition followed by a comma or a word boundary. An assertion like (\1+)(?=,|\b) matches a repetition followed by a comma or a word boundary, but does not include the comma in the match. There is never two dominant numbers !

Is *THIS* what you are after:

<script type="text/javascript">

function findMode( arr )
{
var counts = [ ];
for ( var a = 0; a < arr.length; ++a )
{
var elem = "E" + arr[a];
if ( counts[ elem ] == null )
{
counts[ elem ] = 1;
} else {
++counts[ elem ];
}
}
var half = 0.5 * arr.length;
for ( var elem in counts )
{
// I don't think >= half works...what if the array is simply [1,2] ?? SO I used >
if ( counts[elem] > half ) { return elem.substring(1); }
}
return "NONE";
}

var atest = [ 1, 37, 3, 2, 44, 1, 99, 1 ];
document.write( "Mode of [" + atest + "] is " + findMode(atest) + "<hr>" );

atest = [ 77, 101, 191, 91, 91, 191, 191, 191, 191 ];
document.write( "Mode of [" + atest + "] is " + findMode(atest) + "<hr>" );
</script>

There is never two dominant numbers !

Well, true, if the definition of dominant is "more than half the length of the array". But I was just following the lead of your original code.

Thank you, exactly this. Much better way than mine.

why do you keep talking about more than half?
as i pointed out earlier the Mode isnt always as common as half the elements

Dominant number is not actually a known mathematical term so i assume he ment mode?

why do you keep talking about more than half?
as i pointed out earlier the Mode isnt always as common as half the elements

Dominant number is not actually a known mathematical term so i assume he ment mode?

Not so. :(

http://stackoverflow.com/questions/9599559/decimal-dominant-number-in-an-array

A real number in the array is called a decimal dominant if it occurs more than n/10 times in the array.

But I am not sure what the practical use of this.

This kind of script can be useful to study relative frequencies of letters in the English language... Here is an example (http://mamisab.chez-alice.fr/letterfrequencies.htm).

The issue is: The frequency variations can they give an indication of the author's speech?

is there anything map/filter can't do?

r=[ 77, 101, 191, 91, 91, 191, 191, 191, 191,343 ]
.map(function(a){return this[a]?(this[a]+=1):(this[a]=1),this;},[])[0]

r.indexOf(Math.max.apply(0,r.filter(Number))); // === 191

is there anything map/filter can't do?

r=[ 77, 101, 191, 91, 91, 191, 191, 191, 191,343 ]
.map(function(a){return this[a]?(this[a]+=1):(this[a]=1),this;},[])[0]

r.indexOf(Math.max.apply(0,r.filter(Number))); // === 191


Yes - report the mode when two values occur the same number of times. Obviously you can have more than one mode.
Having two modes is called "bimodal". More than 2 modes is called "multi-modal".

felgall's and Old Pedant's scripts do this.

Yes - report the mode when two values occur the same number of times. Obviously you can have more than one mode.
Having two modes is called "bimodal". More than 2 modes is called "multi-modal".

felgall's and Old Pedant's scripts do this.

my bad, i didn't understand that was required. i've never been good at math...

that does make a bit more work.
what a good opportunity to expand my functional example!

to compare a collection, i needed a variable (counts), and a way get the unique values, unique. i went ahead and named count() and pulled it out of the body to reduce clutter.

isn't it neat how those new pieces bolt right on to the existing solution? that's functional programming for ya.

function unique(a){return this[a]?0:(this[a]=1)}
function count(a){ return this[a]?(this[a]+=1):(this[a]=1),this;}

r=[ 77, 101, 141, 91, 91, 191, 191,343 ]

counts=r.map( count, [])[0];

r.filter(function(a,b){
return counts[a]==this;
},
Math.max.apply(0, counts.filter(Number))
).filter( unique, {});

this should output 91 and 191, right? it does.

and given[ 77, 101, 141, 91, 91, 191, 191,343, 44,44,65 ], it gives [91, 191, 44], so it's appears to be a scale-able solution.

this should output 91 and 191, right? it does.

and given[ 77, 101, 141, 91, 91, 191, 191, 343, 44, 44, 65 ], it gives [91, 191, 44], so it's appears to be a scale-able solution.

Yep, it does! :)

Thanks ! is it very necessary to return many values with map ?

var r=[ 77, 101, 141, 91, 91, 191, 191, 343, 44, 44, 65 ],lttFrq=[];// an array or an object
function count(a){lttFrq[a]?lttFrq[a]+=1:(lttFrq[a]=1);}
r.map(count);
alert(lttFrq);

Then (for IE only9 web users) filter give the «dominant» value, or all others frequencies...

Thanks ! is it very necessary to return many values with map ?


no, i returned an array to avoid a variable.

Of course, the original poster *did* make the requirement that, *FOR HIM*, "dominant" implied that the number had to appear more than half the time.

Qoute from post #3:

Yes exactly. I mean more times than the half


So all the stuff I did, and RndMe did, to produce multiple answers in the case of duplicates is fun but not, per his statement, needed.