views:

231

answers:

2

How could I do the following in javascript in efficient way?

I've counter of 7 items(item0, item1, item2...item6) in order.. like in counts = [0,2,0,5,6,0,9];

There are 3 mutually exclusive groups: group1: item0, item1, item2 group2: item3, 4, 5 group3: item6

A group is considered selected if and only if counters of the group member elements are >= 0.

Now I want to know which group is selected?

+1  A: 

After clarification by understack, the OP, a group is selected if [at least] one of its elements is selected.
This in turn makes the "mutually exclusive" part of the question ambiguous, because the example supplied (counts = [0,2,0,5,6,0,9]) all 3 group would be selected...

Never the less...
The problem of identifying which group is selected can be optimally resolved by relying on on JavaScript short-circuit evaluation of boolean expressions.

A tentative solution would look like the following:

counts = [0,2,0,5,6,0,9];  // as stated an bad value for counts,
                           // if groups are to be mutually exclusive
if (counts[0] || counts[1] || counts[2])
{
   GroupSelected = 1;
}
else if (counts[3] || counts[4] || counts[5])
{
   GroupSelected = 2;
}
else if (counts[6] > 0)
{
   GroupSelected = 3;
}
else
{
   GroupSelected = -1;  //  none of the groups is selected !!!
}

Note: A possible optimization would come from a "prior" knowledge of the probabilities of a given element to be selected (relative to others, in its group), as well as the probability for a given group to be selected.
With such knowledge, the above snippet can be rewritten to first test for the most likely groups first, and within each group to test for the most likely elements first.

mjv
Wow... where'd that downvote came from?
mjv
@mjv: "A group is considered selected if and only if counters of the group member elements are >= 0 and atleast one element counter is > 0".I get the idea here. Thanks
understack
I think I've found the better solution. In count array, make each counter either 0 or 1. Counter 1 means actual count is >0. Now do the xor with groups. so group 1 would be 0000111 consisting of first 3 elements.
understack
@understack. See my edits following you clarification (on what constitute a selected group). Your idea with XOR is a good one, but... a) To my knowledge the only XOR operator in js is a bitwise operator, you'd then need to replace your array by an integer, and then use bitwise ops to set/reset given "elements". b) rather than an XOR you may be looking at an bitwise AND, to serve as a mask c) this is shifting the nature of the problem a bit (pun intended) since now your "array" doesn't convey a numeric info, but merely a boolean one.
mjv
@mjv: I think I gave bad sample counter array. Info you gave is really helpful. Thanks.
understack
+1  A: 

Here is a data structure to do what you want.

var DS = {
    Items: {},
    Groups: {},
    setItem: functon(index, item, group){
     this.Items[index] = item;
     if ( typeof this.Groups[group] === 'undefined' )
      this.Groups[group] = [index];
     else
      this.Groups[group].push(index);
    },
    isSelected: function(item) {
     return item >= 0;
    },
    isSelectedGroup: function(group) {
     var Group = this.Groups[group];
     for ( var i in Group ) {
      var Item = this.Items[i];
      if ( this.isSelected(Item) ) {
       return true;
      }
     }
    },
    getSelectedGroups: function(){
     var selected = [];
     for ( var group in this.Groups ) {
      var Group = this.Groups[group];
      if ( this.isSelectedGroup(Group) ) {
       selected.push(group);
      }
     }
     return selected;
    }
}

To use with your items: 0,2,0,5,6,0,9. Do the following:

DS.setItem(0,0,1);
DS.setItem(1,2,1);
DS.setItem(2,0,1);
DS.setItem(3,5,2);
DS.setItem(4,6,2);
DS.setItem(5,0,2);
DS.setItem(6,9,3);

To test:

DS.isSelectedGroup(3);
// or to get all selected groups
DS.getSelectedGroups();

Should work, if not you should be able to figure it out :)

balupton