Problem coming up with an array function

Question

Let's say I have an increasing sequence of integers: seq = [1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 4 ... ] not guaranteed to have exactly the same number of each integer but guaranteed to be increasing by 1.

Is there a function F that can operate on this sequence whereby F(seq, x) would give me all 1's when an integer in the sequence equals x and all other integers would be 0.

For example:

t = [1, 1, 1, 1, 2, 2, 3, 3, 3, 4]

F(t, 2) = [0, 0, 0, 0, 1, 1, 0, 0, 0, 0]

EDIT: I probably should have made it more clear. Is there a solution where I can do some algebraic operations on the entire array to get the desired result, without iterating over it?

So, I'm wondering if I can do something like: F(t, x) = t op x ?

In Python (t is a numpy.array) it could be:

(t * -1) % x or something...

EDIT2: I found out that the identity function I(t[i] == x) is acceptable to use as an algebraic operation. Sorry, I did not know about identity functions.

Answer 1

A simple method (with C# code) is to simply iterate over the sequence and test it, returning either 1 or 0.

foreach (int element in sequence)
   if (element == myValue)
       yield return 1;
   else 
       yield return 0;

(Written using LINQ)

sequence.Select(elem => elem == myValue ? 1 : 0);

Answer 2

There's a very simple solution to this that doesn't require most of the restrictions you place upon the domain. Just create a new array of the same size, loop through and test for equality between the element in the array and the value you want to compare against. When they're the same, set the corresponding element in the new array to 1. Otherwise, set it to 0. The actual implementation depends on the language you're working with, but should be fairly simple.

If we do take into account your domain, you can introduce a couple of optimisations. If you start with an array of zeroes, you only need to fill in the ones. You know you don't need to start checking until the (n - 1)th element, where n is the value you're comparing against, because there must be at least one of the numbers 1 to n in increasing order. If you don't have to start at 1, you can still start at (n - start). Similarly, if you haven't come across it at array[n - 1], you can jump n - array[n - 1] more elements. You can repeat this, skipping most of the elements, as much as you need to until you either hit the right value or the end of the list (if it's not in there at all).

After you finish dealing with the value you want, there's no need to check the rest of the array, as you know it'll always be increasing. So you can stop early too.

Answer 3

A dichotomy algorithm can quickly locate the range where t[x] = n making such a function of sub-linear complexity in time.

Answer 4

Are you asking for a readymade c++, java API or are you asking for an algorithm? Or is this homework question?

I see the simple algorithm for scanning the array from start to end and comparing with each. If equals then put as 1 else put as 0. Anyway to put the elements in the array you will have to access each element of the new array atleast one. So overall approach will be O(1).

You can certainly reduce the comparison by starting a binary search. Once you find the required number then simply go forward and backward searching for the same number.

Answer 5

Here is a java method which returns a new array.

public static int[] sequence(int[] seq, int number)
{
    int[] newSequence = new int[seq.length];

    for ( int index = 0; index < seq.length; index++ )
    {
        if ( seq[index] == number )
        {
            newSequence[index] = 1;
        }
        else
        {
            newSequence[index] = 0;
        }
    }

    return newSequence;
}

Answer 6

I would initialize an array of zeroes, then do a binary search on the sequence to find the first element that fits your criteria, and only start setting 1's from there. As soon as you have a not equal condition, stop.

Answer 7

Here is a way to do it in O(log n)

>>> from bisect import bisect
>>> def f(t, n):
...     i = bisect(t,n-1)
...     j = bisect(t,n,lo=i) - i
...     return [0]*i+[1]*j+[0]*(len(t)-j-i)
...         
... 
>>> t = [1, 1, 1, 1, 2, 2, 3, 3, 3, 4]
>>> print f(t, 2)
[0, 0, 0, 0, 1, 1, 0, 0, 0, 0]