Алгоритмы транспонирования матриц

#c_sharp #алгоритм

Есть ли какой-нибудь другой способ транспонирования квадратной матрицы? 

for (int i = 0; i < N; i++)
{
    for (int j = 0; j < i; j++)
    {
        tmp = a[i, j];
        a[i, j] = a[j, i];
        a[j, i] = tmp;
    }
}

    

Ответы

Ответ 1

Можно изменить алгоритм таким образом:


Начинать i = 1 вместо i = 0
Использовать обмена при помощи исключающего ИЛИ вместо обычного обмена


Зачем изменить алгоритм так? Не знаю, но раз вы хотите другой способ, вот вам:

for (int i = 1; i < N; i++)
{
  for (int j = 0; j < i; j++)
  {
    a[i, j] ^= a[j, i];
    a[j, i] ^= a[i, j];
    a[i, j] ^= a[j, i];
  }
}


Ответ 2

Ненормальное программирование1 на C#? Их есть у меня! Встречайте - транспонирование
матрицы в функциональном стиле.

using System;
using System.Collections.Generic;
using System.Linq;

namespace Main
{
    static class MyLinqExtensions
    {
        public static IEnumerable> Batch(this IEnumerable source,
int batchSize)
        {
            using(var enumerator = source.GetEnumerator())
            {
                while(enumerator.MoveNext())
                {
                    yield return YieldBatchElements(enumerator, batchSize - 1);
                }   
            }
        }

        private static IEnumerable YieldBatchElements(IEnumerator source,
int batchSize)
        {
            yield return source.Current;
            for(int i = 0; i < batchSize && source.MoveNext(); i++)
            {
                yield return source.Current;
            }
        }

        public static IEnumerable> ZipMany(this IEnumerable>
enumerables)
        {
            return enumerables.Select(inner => inner.Select((s, i) => new {s, i}))
                              .SelectMany(a => a.ToList())
                              .GroupBy(a => a.i, a => a.s)
                              .Select(a => a.ToList()).ToList();
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            var matrix = new[,]
            {
                {1, 2},
                {3, 4},
                {5, 6},
                {7, 8},
                {9, 0}
            };

            var transposedMatrix = matrix.Cast()
                                         .Batch(matrix.GetLength(1))
                                         .ZipMany()
                                         .Select(xs => xs.ToList())
                                         .ToList();

            foreach(var row in transposedMatrix)
            {
                Console.WriteLine(string.Join(", ", row.Select(e => e.ToString())));
            }

        }
    }
}


Самый короткий способ транспонировать матрицу - вызвать функцию zip для списка строк.
На Python это занимает одну строку:

In [1]: matrix = [
   ...:     [1, 2],
   ...:     [3, 4],
   ...:     [5, 6],
   ...:     [7, 8],
   ...:     [9, 0]
   ...: ]

In [2]: zip(*matrix)
Out[2]: 

In [3]: list(zip(*matrix))
Out[3]: [(1, 3, 5, 7, 9), (2, 4, 6, 8, 0)]


Но в случае с C# мы сталкиваемся с рядом проблем:


Исходная матрица представлена в виде 2D массива, а они не поддерживают построчную
обработку, тем более через LINQ
Функция Zip может свести только два списка.


Это значит, что пришло время несколько разнообразить стандартные LINQ расширения:


Вводим расширение, которое преобразует int[,] в IEnumerable>. Код
достаточно простой - используется дополнительная функция, которая для каждого переданного
объекта IEnumerator отсчитывает нужное количетство элементов. Осталось вызвать ее
для переданного объекта IEnumerable, пока он не опустеет. Данный код взят из этого
ответа.
Вводим расширение ZipMany, которое будет зипповать все переданные перечисления. Реализация
также достаточно примитивна - каждый элемент каждой строки ассоциируется с его порядковым
номером, а затем все эти элементы группируются по их порядковым номерам. Данный код
взят из этого ответа.


Осталось только вызвать их для нашего массива. Вызов Cast необходим, потому
что многомерные массивы не могут работать с LINQ напрямую.



1: В общем случае, ФП на C# выглядит красиво. Но в данном случае нам пришлось написать
кучу вспомогательного кода, из-за того, что .NET не предоставляет нужного нам функцонала.
Поэтому в данном случае, императивный подход выглядит лучше, я уж молчу про бейнчмарки.


Ответ 3

Let the izvrat begin!

class Matrix
{
    T[,] payload;
    bool isTransposed = false;

    public Matrix(int n) : this(n, n) { }
    public Matrix(int m, int n) { payload = new T[m, n]; }

    // это вызовется, если кто-то обратится к матрице по индексу:
    // Matrix m = new Matrix(5);
    // m[0, 2] = 42;  // <- здесь
    public T this[int i, int j]
    {
        // если стоит флаг, что матрица транспонирована, меняем местами индексы:
        get { return isTransposed ? payload[j, i] : payload[i, j]; }
        set { if (isTransposed) payload[j, i] = value; else payload[i, j] = value; }
    }

    public void Transpose() { isTransposed = !isTransposed; }
}


Обменяли скорость транспозиции на скорость доступа.


Ответ 4

А можно сделать параллельный (на threads) вариант. Немного не в тему, поскольку на
Си (GNU), но коду  автора в вопросе в чем-то соответствует -)

#include 
#include 

#define SWAP(p1,p2) ({typeof(*p1) *_p1 = (p1), *_p2 = (p2), t = *_p1;   \
      *_p1 = *_p2; *_p2 = t;})
#define MEMDUP(p) (memcpy(malloc(sizeof(p)), &p, sizeof(p)))

struct arg {
  int *base;
  int dim;
  int row;
};

// так в соответствии с pthreads API должна оформляться функция, запускаемая в потоке
void *
trow (void *a)
{
  struct arg *pa = (typeof(pa))a;
  int i = pa->row, j;

  // получили строку, транспонируем ее хвост за диагональю
  for (j = i + 1; j < pa->dim; j++)
    SWAP(pa->base + pa->dim * i + j, pa->base + pa->dim * j + i);

  free(a);
  return 0;
}

void
ptrans (int n, int a[n][n])  // gcc позволяет передавать матрицы таким образом
{
  pthread_t tid[n - 1];
  struct arg arg = {&a[0][0], n, 0};

  // очевидно, что последнюю строку из 1-го элемента можно не трогать
  for (arg.row = 0; arg.row < n - 1; arg.row++)
    pthread_create(tid + arg.row, 0, trow, MEMDUP(arg));

  --n;
  while (n--)
    pthread_join(tid[n], 0);

}


При желании с помощью макросов это легко можно привести к template-виду  для заданного
(скалярного?) типа.


Ответ 5

По мотивам ответа от @VladD, только без лишней проверки.

Сначала добавим несколько вспомогательных классов:

interface IAccessor
{
    T this[int i, int j] { get; set; }
}

class DirectAccessor : IAccessor
{
    public DirectAccessor(T[,] payload)
    {
        m_Payload = payload;
    }

    public T this[int i, int j]
    {
        get { return m_Payload[i, j]; }
        set { m_Payload[i, j] = value; }
    }

    T[,] m_Payload;
}

class TransposedAccessor : IAccessor
{
    public TransposedAccessor(T[,] payload)
    {
        m_Payload = payload;
    }

    public T this[int i, int j]
    {
        get { return m_Payload[j, i]; }
        set { m_Payload[j, i] = value; }
    }

    T[,] m_Payload;
}


А теперь сам класс матрицы:

class Matrix
{
    public Matrix(int n) : this(n, n) { }

    public Matrix(int m, int n)
    {
        m_Payload = new T[m, n];
        m_Accessor = new DirectAccessor(m_Payload);
    }

    public T this[int i, int j]
    {
        get { return m_Accessor[i, j]; }
        set { m_Accessor[i, j] = value; }
    }

    public void Transpose()
    {
        if(m_Accessor is DirectAccessor)
            m_Accessor = new TransposedAccessor(m_Payload);
        else
            m_Accessor = new DirectAccessor(m_Payload);

    }

    private IAccessor m_Accessor;
    private T[,] m_Payload;
}




И ещё один вариант класса матрицы:

class Matrix
{
    public Matrix(int n) : this(n, n) { }

    public Matrix(int m, int n)
    {
        var payload = new T[m, n];
        m_ActiveAccessor = new DirectAccessor(payload);
        m_PassiveAccessor = new TransposedAccessor(payload);
    }

    public T this[int i, int j]
    {
        get { return m_ActiveAccessor[i, j]; }
        set { m_ActiveAccessor[i, j] = value; }
    }

    public void Transpose()
    {
        var tmp = m_ActiveAccessor;
        m_ActiveAccessor = m_PassiveAccessor;
        m_PassiveAccessor = tmp;

    }

    private IAccessor m_ActiveAccessor;
    private IAccessor m_PassiveAccessor;
}


Ответ 6

Ну если немного погуглить, то можно найти к примеру такой вариант:

 // в шарпе эта же функция объявляется так:
 //public static unsafe void transpose(float* src, float* dst, int N, int M)
 void transpose(float *src, float *dst, const int N, const int M) {

    for(int n = 0; n
Ответ 7

Иммутабельный вариант:

var newMatrix = new int[N, N];

for (int i = 0; i < N; i++)
{
    for (int j = 0; j < N; j++)
    {
        newMatrix[i, j] = a[j, i];
    }
}

// по желанию 
a = newMatrix;


Если чуть причесать:

static int[,] Transpose(int[,] matrix)
{
    if (matrix.GetUpperBound(0) != matrix.GetUpperBound(1))
    {
        throw new InvalidOperationException("Non-square matrix");
    }

    if (matrix.GetLowerBound(0) != 0 || matrix.GetLowerBound(1) != 0)
    {
        throw new InvalidOperationException("Non-zero-based matrix");
    }

    int N = matrix.GetUpperBound(0) + 1;

    var newMatrix = new int[N, N];

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            newMatrix[i, j] = matrix[j, i];
        }
    }

    return newMatrix;
}

// .....
// вызов:
a = Transpose(a);