Array 2D pairwise function

Question

I found myself in the need of a function to pairwise an array 2D so I created one:

public static IEnumerable<TOut> Pairwise<TIn, TOut>(this TIn[,] source ,Func<TIn, TIn, TOut> selector)
{
    Point[] deltas =
    {
        new Point(-1, -1), new Point(0, -1), new Point(1, -1),
        new Point(-1, 0),                    new Point(1, 0),
        new Point(-1, 1),  new Point(0, 1),  new Point(1, 1)
    };


    int width = source.GetLength(0);
    int height = source.GetLength(1);

    for (int x = 0; x < width; x++)
    {
        for (int y = 0; y < height; y++)
        {
            Point[] neighbors =
                deltas
                    .Select(point => new Point(point.X + x, point.Y + y))
                    .Where(point => !(point.X < 0 || point.X >= width || point.Y < 0 || point.Y >= height))
                    .ToArray();

            TIn current = source[x, y];
            foreach (var element in neighbors.Select(point => selector(current, source[point.X, point.Y])))
            {
                yield return element;
            }

        }
    }
}

But, as you can see, this function returns duplicates and its performance is not so good. So, I tried a new approach. Instead of getting the neighbors of each element and returning them, it occurred to me that if I pairwise the rows, columns, and diagonals. The columns and rows were easy, but getting the diagonals was a challenge.

This is what I came up with:

public static IEnumerable<IEnumerable<T>> Diagonals<T>(this T[,] source, bool inverse = false)
    {

    int width = source.GetLength(0);
    int height = source.GetLength(1);

    //this code I found returns the diagonals but not the inverse them so I couldnt use it 

    //for (int slice = 0; slice < width + height - 1; ++slice)
    //{
    //    var curSlice = new List<T>();
    //    int z1 = slice < height ? 0 : slice - height + 1;
    //    int z2 = slice < width ? 0 : slice - width + 1;
    //    for (int j = slice - z2; j >= z1; --j)
    //    {
    //        curSlice.Add(source[j, slice - j]);
    //    }
    //    yield return curSlice;
    //}

    List<Tuple<Point, T>> curSlice = new List<Tuple<Point, T>>();

    curSlice.Add(!inverse
        ? Tuple.Create(new Point(0, 0), source[0, 0])
        : Tuple.Create(new Point(width - 1, 0), source[width - 1, 0]));

    while (curSlice.Count > 0)
    {

        List<Tuple<Point, T>> prevSlice = curSlice;
        curSlice = new List<Tuple<Point, T>>();
        bool isFirst = true;
        foreach (Point ele in prevSlice.Select(tuple => tuple.Item1))
        {
            int? newY = ele.Y + 1 >= height ? (int?) null : ele.Y + 1 ;
            int? newX = !inverse
                ? (ele.X + 1 >= width ? (int?) null : ele.X + 1)
                : (ele.X - 1 < 0 ? (int?) null : ele.X - 1);

            if (isFirst)
            {
                if (newX != null)
                    curSlice.Add(Tuple.Create(new Point(newX.Value, ele.Y), source[newX.Value, ele.Y]));
                isFirst = false;
            }

            if (newY != null)
                curSlice.Add(Tuple.Create(new Point(ele.X, newY.Value), source[ele.X, newY.Value]));

        }
        yield return curSlice.Select(tuple => tuple.Item2);

    }


}

Finally, this was my solution. Is this the simplest solution or did I over-complicate things?

public static IEnumerable<TOut> Pairwise2<TIn, TOut>(this TIn[,] source, Func<TIn, TIn, TOut> selector)
{

    int width = source.GetLength(0);
    int height = source.GetLength(1);

    var horizontalSeq = Enumerable.Range(0, width).Pairwise(Tuple.Create).ToArray();
    var verticalSeq = Enumerable.Range(0, height).Pairwise(Tuple.Create).ToArray();


    for (int y = 0; y < height; y++)
    {
        int y1 = y;
        foreach (var e in horizontalSeq.Select(tuple => selector(source[tuple.Item1, y1], source[tuple.Item2, y1])))
            yield return e;
    }



    for (int x = 0; x < width; x++)
    {
        int x1 = x;
        foreach (var e in verticalSeq.Select(tuple => selector(source[x1, tuple.Item1], source[x1, tuple.Item2])))
            yield return e;
    }



    foreach (var e in source.Diagonals().SelectMany(ins => ins.Pairwise(selector)))
    {
        yield return e;
    }


    foreach (var e in source.Diagonals(inverse: true).SelectMany(ins => ins.Pairwise(selector)))
    {
        yield return e;
    }


}

Example for this array:

00 03 06 09

01 04 07 10

02 05 08 11

The pairs would be:

(0, 3) (3, 6) (6, 9) (1, 4) (4, 7) (7, 10) (2, 5) (5, 8) (8, 11) (0, 1) (1, 2) 
(3, 4) (4, 5) (6, 7) (7, 8) (9, 10) (10, 11) (3, 1) (6, 4) (4, 2) (9, 7) (7, 5) (10, 8) 
(6, 10) (3, 7) (7, 11) (0, 4) (4, 8) (1, 5)

To clarify, for each element x in the 2D-array, and for each neighbour y of x, you want the result of f(x, y) (and you're assuming that f(x, y) = f(y, x), since you say that Pairwise returns duplicates)? — mjolka, Jul 25 '14 at 5:32
In your example, I would expect (6, 10) to be a pair. Am I wrong? — mjolka, Jul 25 '14 at 5:50

mjolka · Accepted Answer · 2014-07-25 09:15:45Z

Let's think about this geometrically.

Since we're treating a pair of neighbours (x, y) as equivalent to (y, x), we can think of our neighbour-relation as being directed. That is, from up/down we can pick one (let's pick down); similarly for left/right, up-left/down-right, and up-right/down-left.

Now most elements have three neighbours: down, right, and down-right

$$ \begin{pmatrix} 0 & \rightarrow & 3 & \rightarrow & 6 & \rightarrow & 9 \\ \downarrow & \searrow & \downarrow & \searrow & \downarrow & \searrow \\ 1 & \rightarrow & 4 & \rightarrow & 7 & \rightarrow & 10 \\ \downarrow & \searrow & \downarrow & \searrow & \downarrow & \searrow \\ 2 & & 5 & & 8 & & 11 \end{pmatrix} $$

We can find those neighbours with the following code:

public static IEnumerable<TOut> Pairwise2<TIn, TOut>(TIn[,] source, Func<TIn, TIn, TOut> selector)
{
    var lastRow = source.GetLength(0) - 1;
    var lastColumn = source.GetLength(1) - 1;

    for (var i = 0; i < lastRow; i++)
    {
        for (var j = 0; j < lastColumn; j++)
        {
            var current = source[i, j];
            yield return selector(current, source[i, j + 1]);
            yield return selector(current, source[i + 1, j]);
            yield return selector(current, source[i + 1, j + 1]);
        }
    }
}

Now we need the down-left neighbours:

$$ \begin{pmatrix} 0 & & 3 & & 6 & & 9 \\ & \swarrow & & \swarrow & & \swarrow \\ 1 & & 4 & & 7 & & 10 \\ & \swarrow & & \swarrow & & \swarrow \\ 2 & & 5 & & 8 & & 11 \end{pmatrix} $$

Handily, we can get down-left neighbours by adding one line

public static IEnumerable<TOut> Pairwise2<TIn, TOut>(TIn[,] source, Func<TIn, TIn, TOut> selector)
{
    var lastRow = source.GetLength(0) - 1;
    var lastColumn = source.GetLength(1) - 1;

    for (var i = 0; i < lastRow; i++)
    {
        for (var j = 0; j < lastColumn; j++)
        {
            var current = source[i, j];
            yield return selector(current, source[i, j + 1]);
            yield return selector(current, source[i + 1, j]);
            yield return selector(current, source[i + 1, j + 1]);
            yield return selector(source[i, j + 1], source[i + 1, j]);
        }
    }
}

Now we need to get the down-neighbours for the right column, and the right-neighbours for the bottom row

$$ \begin{pmatrix} 0 & & 3 & & 6 & & 9 \\ & & & & & & \downarrow \\ 1 & & 4 & & 7 & & 10 \\ & & & & & & \downarrow \\ 2 & \rightarrow & 5 & \rightarrow & 8 & \rightarrow & 11 \end{pmatrix} $$

which gives us our final code:

public static IEnumerable<TOut> Pairwise2<TIn, TOut>(TIn[,] source, Func<TIn, TIn, TOut> selector)
{
    var lastRow = source.GetLength(0) - 1;
    var lastColumn = source.GetLength(1) - 1;

    for (var i = 0; i < lastRow; i++)
    {
        for (var j = 0; j < lastColumn; j++)
        {
            var current = source[i, j];
            yield return selector(current, source[i, j + 1]);
            yield return selector(current, source[i + 1, j]);
            yield return selector(current, source[i + 1, j + 1]);
            yield return selector(source[i, j + 1], source[i + 1, j]);
        }

        yield return selector(source[i, lastColumn], source[i + 1, lastColumn]);
    }

    for (var j = 0; j < lastColumn; j++)
    {
        yield return selector(source[lastRow, j], source[lastRow, j + 1]);
    }
}

@Vogel612 the other two selectors are for the right column and bottom row, which are special given the directions I chose. There might be a clearer way to write it, I'll have a think. I do like that this way has no conditionals. — mjolka, Jul 25 '14 at 8:38
Indeed this way is much more faster and simpler, I don't know why I always complicate things, thanks! — elios264, Jul 25 '14 at 21:44

Vogel612 · Answer 2 · 2014-07-25 08:14:32Z

Taking from what I see in @mjolka's answer and based on the fact, that I found your first implementation (with duplicate pairings) to be the most readable, I think the answer to your problem is relatively simple.

Assuming we have a single element, on a infinite plain, then for each element we have 8 directions we can "move" from the element. These directions are:

Up-Left        Up        Up-Right

Left           x         Right

Down-Left      Down      Down-Right

Now if we were to pair our items using this, we'd get duplicates. It's only half of all Pairings, but it's duplicates.

This is because each of the directions has an inverse.

Up-Left \$\mapsto\$ Down-Right
Left \$\mapsto\$ Right
Up \$\mapsto\$ Down
Up-Right \$\mapsto\$ Down-Left

We can now remove all the directions one one side of the arrow, as to prevent duplicate pairings.

Which leaves us with:

       x     R

DL     D     DR

Long story short, you should be able to use your first approach if you change your deltas for pair-calculation to:

Point[] deltas =
{
                                         new Point(1, 0),
    new Point(-1, 1),  new Point(0, 1),  new Point(1, 1)
};

asked	1 year ago
viewed	160 times
active	1 year ago

current community

your communities

more stack exchange communities

Array 2D pairwise function

2 Answers 2

Your Answer

Not the answer you're looking for? Browse other questions tagged c# performance array or ask your own question.

Visit Chat

Hot Network Questions

current community

your communities

more stack exchange communities

Array 2D pairwise function

2 Answers 2

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged c# performance array or ask your own question.

Visit Chat

Related

Hot Network Questions