Given list, subset of list: return bitmask (bit vector same length as list) corresponding to the subset.

Question

For example,

bitmask({1, 2, 3, 4}, {2, 4})

returns

{False, True, False, True}

The naive way to do this is to map a membership function over the list:

map(lambda(x, member(x, subset)), list)

but that's O(n*m) and it can be done in O(n+m).

What's the best way to implement bitmask() in your favorite language?

PS: It doesn't actually matter if the second list is a subset of the first. However you implement it, any elements of the second list that are not in the first will simply be ignored.

Answer 1

Mathematica

bitmask[list_, subset_] := Module[{f},
  f[_] = False;
  (f[#] = True)& /@ subset;
  f /@ list]

Note that this is the inverse of Pick[list,sel] -- it returns a bitmask that when applied to a list (using Pick), returns the items in the subset.

Answer 2

def bitmask(source, mask):
  ret = []

  vals = set()
  for val in mask:
    vals.add(val)

  for val in source:
    if val in vals:
      ret.append(True)
    else: ret.append(False)

I'm sure there's a better (more pythonic?) way to do this, but I am a Python noob.

Answer 3

Python:

def bitmask(_list, subset):
    s = set(subset)
    return [x in s for x in _list]

N.B. I would prefer to return a generator expression rather than a list, but the question specifically asked for a list.

edit

BTW, it is worth noting that this will work for any iterable sequences, e.g.

>>> bitmask("abcdefgh", "dfgz")
[False, False, False, True, False, True, True, False]

The generator expression version will also work for sequences of infinite length.

def bitmask(_list, subset):
    s = set(subset)
    return (x in s for x in _list)

>>> bitmask(itertools.count(), [2,4,6])
(output omitted due to lack of time and space)