Hello and welcome to our community! Is this your first visit?
Register
Enjoy an ad free experience by logging in. Not a member yet? Register.
Page 1 of 2 12 LastLast
Results 1 to 15 of 27
  1. #1
    New to the CF scene
    Join Date
    Dec 2012
    Location
    London
    Posts
    4
    Thanks
    1
    Thanked 0 Times in 0 Posts

    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?
    Last edited by evaaa; 12-01-2012 at 08:02 PM.

  • #2
    New Coder donna1's Avatar
    Join Date
    Nov 2012
    Location
    london
    Posts
    99
    Thanks
    9
    Thanked 4 Times in 4 Posts
    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

  • #3
    New to the CF scene
    Join Date
    Dec 2012
    Location
    London
    Posts
    4
    Thanks
    1
    Thanked 0 Times in 0 Posts
    Yes exactly. I mean more times than the half

  • #4
    New Coder donna1's Avatar
    Join Date
    Nov 2012
    Location
    london
    Posts
    99
    Thanks
    9
    Thanked 4 Times in 4 Posts
    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]);
    Last edited by donna1; 12-01-2012 at 08:53 PM.

  • #5
    Master Coder felgall's Avatar
    Join Date
    Sep 2005
    Location
    Sydney, Australia
    Posts
    6,642
    Thanks
    0
    Thanked 649 Times in 639 Posts
    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)
    Stephen
    Learn Modern JavaScript - http://javascriptexample.net/
    Helping others to solve their computer problem at http://www.felgall.com/

    Don't forget to start your JavaScript code with "use strict"; which makes it easier to find errors in your code.

  • #6
    Regular Coder
    Join Date
    May 2012
    Location
    France
    Posts
    224
    Thanks
    0
    Thanked 32 Times in 30 Posts
    I propose this two lines script with a backreference regular expression
    Code:
    <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>
    Last edited by 007julien; 12-01-2012 at 10:11 PM.

  • #7
    New Coder donna1's Avatar
    Join Date
    Nov 2012
    Location
    london
    Posts
    99
    Thanks
    9
    Thanked 4 Times in 4 Posts
    Quote Originally Posted by 007julien View Post

    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?

  • #8
    Supreme Master coder! Old Pedant's Avatar
    Join Date
    Feb 2009
    Posts
    27,652
    Thanks
    80
    Thanked 4,640 Times in 4,602 Posts
    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 optimist sees the glass as half full.
    A pessimist sees the glass as half empty.
    A realist drinks it no matter how much there is.

  • #9
    Regular Coder
    Join Date
    May 2012
    Location
    France
    Posts
    224
    Thanks
    0
    Thanked 32 Times in 30 Posts
    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
    Code:
    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) 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
    Last edited by 007julien; 12-02-2012 at 12:14 AM.

  • #10
    Supreme Master coder! Old Pedant's Avatar
    Join Date
    Feb 2009
    Posts
    27,652
    Thanks
    80
    Thanked 4,640 Times in 4,602 Posts
    WHOOPS! I am wrong! And that code is fatally flawed!

    Change the array to
    Code:
    var arr=[1,41,222,33,40,18,22,41,2,2,42,27,58];
    and it gives the answer
    Code:
    This number 2 appears 3 times
    Reason: After sorting the array and converting it to a string, you get:
    Code:
    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:
    Code:
    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.
    Last edited by Old Pedant; 12-01-2012 at 11:52 PM.
    An optimist sees the glass as half full.
    A pessimist sees the glass as half empty.
    A realist drinks it no matter how much there is.

  • #11
    Supreme Master coder! Old Pedant's Avatar
    Join Date
    Feb 2009
    Posts
    27,652
    Thanks
    80
    Thanked 4,640 Times in 4,602 Posts
    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.
    An optimist sees the glass as half full.
    A pessimist sees the glass as half empty.
    A realist drinks it no matter how much there is.

  • #12
    Supreme Master coder! Old Pedant's Avatar
    Join Date
    Feb 2009
    Posts
    27,652
    Thanks
    80
    Thanked 4,640 Times in 4,602 Posts
    W.T.H. This was fun.

    My version that fixes both flaws. Not as compact, but easier to understand, I hope:
    Code:
    <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>
    An optimist sees the glass as half full.
    A pessimist sees the glass as half empty.
    A realist drinks it no matter how much there is.

  • #13
    New to the CF scene
    Join Date
    Dec 2012
    Location
    London
    Posts
    4
    Thanks
    1
    Thanked 0 Times in 0 Posts
    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.

  • #14
    Regular Coder
    Join Date
    May 2012
    Location
    France
    Posts
    224
    Thanks
    0
    Thanked 32 Times in 30 Posts
    A shorter script with Old Pedant observations
    Code:
    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 !
    Last edited by 007julien; 12-02-2012 at 01:03 AM. Reason: complements

  • #15
    Supreme Master coder! Old Pedant's Avatar
    Join Date
    Feb 2009
    Posts
    27,652
    Thanks
    80
    Thanked 4,640 Times in 4,602 Posts
    Is *THIS* what you are after:
    Code:
    <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>
    Last edited by Old Pedant; 12-02-2012 at 12:51 AM.
    An optimist sees the glass as half full.
    A pessimist sees the glass as half empty.
    A realist drinks it no matter how much there is.

  • Users who have thanked Old Pedant for this post:

    evaaa (12-02-2012)


  •  
    Page 1 of 2 12 LastLast

    Posting Permissions

    • You may not post new threads
    • You may not post replies
    • You may not post attachments
    • You may not edit your posts
    •