Хитрое транспонирование матрицы

@JIawliet · Регистрация: 20.07.2016

Author24 — интернет-сервис помощи студентам

Значится так, есть матрица загнанная в вектор... есть ли способ транспонировать ее не создавая новый вектор, то есть просто обменивая элементы в исходном?

P.S: Матрица не обязательно квадратная!!!

Добавлено через 25 минут
а задачка то не тривиальная))))

наведу простой пример, чтоб было понятней:

C++

/*
      исходная матрица
      1 2
      3 4
      5 6
 
      нужно (выходная матрица)
      1  3  5
      2  4  6
 
      представление в векторе (исходная матрица):
      1 2 3 4 5 6
 
      представление в векторе (матрица-результат):
      1 3 5 2 4 6
*/

разумеется нужен общий алгоритм, а не под какой-то конкретный случай)

@Ferrari F1 · 13.08.2016, 13:16

Сообщение от JIawliet

его код сверху, что вам мешает посмотреть?

неудобно читать такой код (не в обиду мр.иксу

)

@JIawliet · 13.08.2016, 13:20 **[ТС]**

Сообщение от Ferrari F1

неудобно читать такой код

на самом деле это так кажется)) поначалу да, а как привыкнешь - очень даже удобно... определенно у такого стиля есть некий порог вхождения)

@Ferrari F1 · 13.08.2016, 13:28

JIawliet, мне интересно, по какому алгоритму ты будиш писать свой код, я просто не оч понил про твой способ без хранения индексов

@JIawliet · 13.08.2016, 16:36 **[ТС]**

Ferrari F1, а я сам еще не знаю)))) как доделаю напишу)

Добавлено через 3 часа 0 минут
Ferrari F1,
И так, вот что получилось (+ еще один интересный вариант, такого не предлогали):

C++

    template <typename T>
    Matrix<T>& Matrix<T>::conjugateMatr ()
    {
        /*checkMatr();
 
        auto newPvt = std::unique_ptr<std::vector<T>>(new std::vector<T>());
 
        for (size_t k = 0; k != columns; ++k)
            for (size_t j = 0; j != rows; ++j)
                newPvt -> push_back((*this)(j, k));
 
        upvt.reset(newPvt.release());
 
        std::swap(rows, columns);
 
        return *this;*/
 
 
        checkMatr();
 
        if (rows != 1 && columns != 1)
        {
            std::map<T, size_t> indexes;
            for (size_t j = 1; j != upvt -> size() - 1; ++j)
                indexes[(*upvt)[j]] = rows * (j % columns) + j / columns;
 
 
            for (auto it = indexes.begin(), itend = indexes.end();
                 it != itend; ++it)
                if ((*upvt)[it -> second] != it -> first)
                    std::swap(*(std::find(upvt -> begin(),
                                          upvt -> end(),
                                          it -> first)),
                        (*upvt)[it -> second]);
        }
 
        std::swap(rows, columns);
 
        return *this;
    }

Закомментированный вариант: создается дополнительный вектор и из первого копируем элементы во второй в правильном порядке. Просто.

Другой вариант: создается map и каждому элементу из исходной матрицы присваивается индекс (где он будет стоять в транспонированной матрице), первый и последний элементы стоят на месте, поэтому их игнорируем. Далее просто запускаем цикл по всему map и переставляем элементы из вектора в нужные позиции.

Без сохранения индексов (создания map) не осилил(

Замечено, что для транспонирования матрицы-вектора с количеством элементов n, нужно всего n / 2 обменов элементов... оставим поиски этого мега-алгоритма людям, у которых больше свободного времени и есть невиданное желание транспонировать матрицы

@Mr.X · 13.08.2016, 17:50

Сообщение от JIawliet

оставим поиски этого мега-алгоритма людям, у которых больше свободного времени и есть невиданное желание транспонировать матрицы

Главное, это не опускать руки!
Вот, сделал практически без использования памяти. Память выделяется только в vector<bool> по одному биту на элемент матрицы только для того, чтобы отмечать индексы уже обработанных элементов. Если быть принципиальным, то можно и без этого вектора обойтись, и хранить только первые индексы обработанных циклов. Но тогда работать будет дольше: каждый индекс вектора надо будет прогонять по циклу, пока он опять не перейдет в себя, и следить, не содержатся ли в цикле начальные элементы уже обработанных циклов.
Мой вариант:

C++

///////////////////////////////////////////////////////////////////////////////
//4.
///////////////////////////////////////////////////////////////////////////////
//есть матрица загнанная в вектор... есть ли способ транспонировать
//ее не создавая новый вектор, то есть просто обменивая элементы в исходном?
//P.S: Матрица не обязательно квадратная!!!
///////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <vector>
///////////////////////////////////////////////////////////////////////////////
typedef int                             T_val;
typedef std::vector     < T_val     >   T_values;
typedef std::vector     < bool      >   T_ind_is_processed;
///////////////////////////////////////////////////////////////////////////////
typedef T_values                        T_row;
typedef std::vector     < T_row     >   T_matr;
///////////////////////////////////////////////////////////////////////////////
struct  T_lin_matr
{
    //-------------------------------------------------------------------------
    int         cols_total_;
    T_values    values_;
    //-------------------------------------------------------------------------
    template    < typename  TT_matr >
    T_lin_matr
        (
            int                     rows_total,
            int                     cols_total,
            TT_matr     const   &   matr
        )
        :
        cols_total_     ( cols_total ),
 
        values_         (
                                rows_total
                            *   cols_total
                        )
    {
        for( int  i{}; i < rows_total; ++i )
        {
            for( int  j{}; j < cols_total; ++j )
            {
                operator()( i, j )   =   matr[i][j];
            }//for
        }//for
    }
    //-------------------------------------------------------------------------
    int     rows_total()
    {
        return      values_.size()
                /   cols_total_;
    }
    //-------------------------------------------------------------------------
    T_val   &   operator()
        (
            int     i,
            int     j
        )
    {
        return  values_[ i * cols_total_ + j ];
    }
    //-------------------------------------------------------------------------
    void    transp()
    {
        T_ind_is_processed  ind_is_processed    (
                                                    values_.size()
                                                );
 
        int         unprocessed_ind_min     {};
 
        for(;;)
        {
            unprocessed_ind_min
 
                =       std::find_if
                            (
                                    ind_is_processed.begin      ()
                                +   unprocessed_ind_min,
 
                                ind_is_processed.end            (),
 
                                []                              ( auto  val )
                                {
                                    return  val     ==  0;
                                }
                            )
 
                    -   ind_is_processed.begin();
 
            if  (
                        unprocessed_ind_min
 
                    ==  int (
                                values_.size()
                            )
                )
            {
                cols_total_     =   rows_total();
                break;
            }
 
            execute_loop
                (
                    unprocessed_ind_min,
                    ind_is_processed
                );
        }//for
    }
    //-------------------------------------------------------------------------
    void    execute_loop
        (
            int                     first_loop_ind,
            T_ind_is_processed  &   ind_is_processed
 
        )//I
    {
        auto    last_loop_ind   =   ind_of_transp_ind( first_loop_ind );
        int     cur_loop_ind    =   last_loop_ind;
        ind_is_processed[ first_loop_ind ]  =   1;
 
        do
        {
            std::swap   (
                            values_[ cur_loop_ind   ],
                            values_[ first_loop_ind ]
                        );
 
            ind_is_processed[ cur_loop_ind ]    =   1;
 
            cur_loop_ind    =   ind_of_transp_ind( cur_loop_ind );
        }
        while   (
                        cur_loop_ind
                    !=  first_loop_ind
                );
    }
    //-------------------------------------------------------------------------
    int     ind_of_transp_ind( int  t )
    {
        return  t / cols_total_ + t % cols_total_ * rows_total();
    }
    //-------------------------------------------------------------------------
    int     transp_ind_of_ind( int     k )
    {
        return  k / rows_total() + k %  rows_total() * cols_total_;
    }
    //-------------------------------------------------------------------------
    void    print()
    {
        for( size_t  k{}; k < values_.size(); ++k )
        {
            std::cout   <<  values_[k]
                        <<  '\t';
 
            if  (
                    (k + 1)     %   cols_total_     ==  0
                )
            {
                std::cout   <<  std::endl;
            }
        }//for
 
        std::cout   <<  std::endl;
    }
    //-------------------------------------------------------------------------
};
///////////////////////////////////////////////////////////////////////////////
int     main()
{
    srand(unsigned(time(0)));
 
    for(;;)
    {
        const   int     rows_total{ rand() % 5 + 2 };
        const   int     cols_total{ rand() % 5 + 2 };
 
        T_matr  matr    (
                            rows_total,
                            T_row( cols_total )
                        );
 
        for( int  i{}; i < rows_total; ++i )
        {
            for( int  j{}; j < cols_total; ++j )
            {
                matr[i][j]  =   rand()  %   10  +   1;
            }
        }//for
 
        T_lin_matr  lin_matr    (
                                    rows_total,
                                    cols_total,
                                    matr
                                );
 
        lin_matr.print      ();
        lin_matr.transp     ();
        lin_matr.print      ();
 
        system("pause");
    }//for
}

@Ferrari F1 · 13.08.2016, 19:22

Сообщение от JIawliet

Без сохранения индексов (создания map) не осилил(

а знаешь, почему так?

Допустим есть такой вектор-матрица 4х2

1, 2, 3, 4, 5, 6, 7, 8

из него должен получиться вектор-матрица 2х4

1, 3, 5, 7, 2, 4, 6, 8

таким образом, элемент со значением 2 переместиться с 1ого индекса на 4
если мы обменяем эти два значения, получится

1, 5, 3, 4, 2, 6, 7, 8

Таким образом, мы потеряли ту связь с элементом со значением 5, теперь он по первому индексу, когда в оригинале он находится на четвертому,
тем самым мы потеряли закономерность по которой надо переставлять элементы.

Стоит еще заметить, что это и есть цена за обмен значений внутри матрицы, не выходя за ее пределы (т.е. без копирования ее элементов)

@JIawliet · 13.08.2016, 19:28 **[ТС]**

Mr.X, ага - оно самое!) минимум обменов, лишней памяти не выделяется, сказка)))

Хочу вас кое о чем попросить, потому что за вами я поправлять код не решился

:
a) убрать из кода функцию:

C++

 int     transp_ind_of_ind( int     k )
    {
        return  k / rows_total() + k %  rows_total() * cols_total_;
    }

она не нужна и если честно ее предназначения осталось для меня загадкой)

b) в функцию execute_loop перед циклом do - while добавить следующую проверку:

C++

1 2	if (cur_loop_ind == first_loop_ind) return;

ну смысл понятен, незачем менять местами элементы, которые уже находятся там, где надо) (это относится в основном к первому и последнему элементу; как вариант можно в векторе ind_is_processed первый и последний элемент в true сразу ставить)

Большое спасибо за то, что не пожалели время и довели решение задачи до ума, нет - до идеального состояния) Само собой я отмечу лучший ответ)

Добавлено через 4 минуты
Ferrari F1, да это ясно)) вон Mr.X, предложил пожалуй идеальный вариант решения... распечатайте код, не поленитесь разобраться, это реально круто)

память выделялась только под std::vector<bool> в котором просто отмечалось обработан ли конкретный элемент или нет...

@Ferrari F1 · 13.08.2016, 19:43

JIawliet, у меня еще есть такой вариант упрощения алгоритма:
о всякой матрице с обоими размерами хотя бы больше одного можно говорить, что она содержит в себе квадратную матрицу
В таком случае эту кв. матрицу поменяем кодом, что кинул zss, а остатки, что выходят из квадратной области, шлифануть каким-нить другим алгоритмом.

Хотя, могу и ошибиться что это будет верным для решения

@JIawliet · 13.08.2016, 19:51 **[ТС]**

Ferrari F1, а я так уже пробовал, но до ума не довел... тут дело в том, что те элементы, которые не входят в квадратную матрицу, потом переставляют элементы, которые входили в квадратную матрицу, с их законных мест)

@Ferrari F1 · 13.08.2016, 19:53

JIawliet, вобщемя я уже задалбался чесна гря) моих сил хватило на этот код с картой
Пашел ка я рубиться в ксску_)

@JIawliet · 13.08.2016, 20:02 **[ТС]**

Ferrari F1, ну задача решена - решена, причем было предложено множество вариантов решения)

@Babysitter · 13.08.2016, 20:05

Сообщение от Ferrari F1

Babysitter, а у вас что получилось?

я начал утром что-то писать, сейчас продолжу.. может чего и выйдет.

@Mr.X · 13.08.2016, 20:32

Сообщение от JIawliet

убрать из кода функцию

Я тоже вспомнил, что забыл ее выбросить.

Сообщение от JIawliet

в функцию execute_loop перед циклом do - while добавить следующую проверку

Да, на самом деле здесь проверку надо в начале цикла сделать.

C++

///////////////////////////////////////////////////////////////////////////////
//5.
///////////////////////////////////////////////////////////////////////////////
//есть матрица загнанная в вектор... есть ли способ транспонировать
//ее не создавая новый вектор, то есть просто обменивая элементы в исходном?
//P.S: Матрица не обязательно квадратная!!!
///////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <vector>
///////////////////////////////////////////////////////////////////////////////
typedef int                             T_val;
typedef std::vector     < T_val     >   T_values;
typedef std::vector     < bool      >   T_ind_is_processed;
///////////////////////////////////////////////////////////////////////////////
typedef T_values                        T_row;
typedef std::vector     < T_row     >   T_matr;
///////////////////////////////////////////////////////////////////////////////
struct  T_lin_matr
{
    //-------------------------------------------------------------------------
    int         cols_total_;
    T_values    values_;
    //-------------------------------------------------------------------------
    template    < typename  TT_matr >
    T_lin_matr
        (
            int                     rows_total,
            int                     cols_total,
            TT_matr     const   &   matr
        )
        :
        cols_total_     ( cols_total ),
 
        values_         (
                                rows_total
                            *   cols_total
                        )
    {
        for( int  i{}; i < rows_total; ++i )
        {
            for( int  j{}; j < cols_total; ++j )
            {
                operator()( i, j )   =   matr[i][j];
            }//for
        }//for
    }
    //-------------------------------------------------------------------------
    int     rows_total()
    {
        return      values_.size()
                /   cols_total_;
    }
    //-------------------------------------------------------------------------
    T_val   &   operator()
        (
            int     i,
            int     j
        )
    {
        return  values_[ i * cols_total_ + j ];
    }
    //-------------------------------------------------------------------------
    void    transp()
    {
        T_ind_is_processed  ind_is_processed        (
                                                        values_.size()
                                                    );
 
        int                 unprocessed_ind_min     {};
 
        for(;;)
        {
            unprocessed_ind_min
 
                =       std::find_if
                            (
                                    ind_is_processed.begin      ()
                                +   unprocessed_ind_min,
 
                                ind_is_processed.end            (),
 
                                []                              ( auto  val )
                                {
                                    return  val     ==  0;
                                }
                            )
 
                    -   ind_is_processed.begin();
 
            if  (
                        unprocessed_ind_min
 
                    ==  int (
                                values_.size()
                            )
                )
            {
                cols_total_     =   rows_total();
                break;
            }
 
            execute_loop
                (
                    unprocessed_ind_min,
                    ind_is_processed
                );
        }//for
    }
    //-------------------------------------------------------------------------
    void    execute_loop
        (
            int                     first_loop_ind,
            T_ind_is_processed  &   ind_is_processed
        )
    {
        auto    cur_loop_ind    =   ind_of_transp_ind( first_loop_ind );
        ind_is_processed[ first_loop_ind ]  =   1;
 
        while   (
                        cur_loop_ind
                    !=  first_loop_ind
                )
        {
            std::swap   (
                            values_[ cur_loop_ind   ],
                            values_[ first_loop_ind ]
                        );
 
            ind_is_processed[ cur_loop_ind ]    =   1;
 
            cur_loop_ind    =   ind_of_transp_ind( cur_loop_ind );
        }//while
    }
    //-------------------------------------------------------------------------
    int     ind_of_transp_ind( int  t )
    {
        return  t / cols_total_ + t % cols_total_ * rows_total();
    }
    //-------------------------------------------------------------------------
    void    print()
    {
        for( size_t  k{}; k < values_.size(); ++k )
        {
            std::cout   <<  values_[k]
                        <<  '\t';
 
            if  (
                    (k + 1)     %   cols_total_     ==  0
                )
            {
                std::cout   <<  std::endl;
            }
        }//for
 
        std::cout   <<  std::endl;
    }
    //-------------------------------------------------------------------------
};
///////////////////////////////////////////////////////////////////////////////
int     main()
{
    srand(unsigned(time(0)));
 
    for(;;)
    {
        const   int     rows_total{ rand() % 5 + 2 };
        const   int     cols_total{ rand() % 5 + 2 };
 
        T_matr  matr    (
                            rows_total,
                            T_row( cols_total )
                        );
 
        for( int  i{}; i < rows_total; ++i )
        {
            for( int  j{}; j < cols_total; ++j )
            {
                matr[i][j]  =   rand()  %   10  +   1;
            }
        }//for
 
        T_lin_matr  lin_matr    (
                                    rows_total,
                                    cols_total,
                                    matr
                                );
 
        lin_matr.print      ();
        lin_matr.transp     ();
        lin_matr.print      ();
 
        system("pause");
    }//for
}

Добавлено через 10 минут

Сообщение от JIawliet

Ferrari F1, а я так уже пробовал, но до ума не довел... тут дело в том, что те элементы, которые не входят в квадратную матрицу, потом переставляют элементы, которые входили в квадратную матрицу, с их законных мест)

Да, это только при транспонировании квадратной матрицы циклы перестановки имеют длину 1 и 2. У прямоугольной они подлиннее.

@Babysitter · 14.08.2016, 09:44

окей, вчера ночью это заработало. какая наивная идея у меня была
пусть есть у нас N=2 M=3
1 2 3 4 5 6
я начинаю с первого элемента и перемещаю его на новое место, на место тройки в данном случае.
но куда девать тройку? повторяем процедуру и так до тех пор пока все не замкнется (так я думал)
[1] -> [2]
[2] -> [4]
[4] -> [3]
[3] -> [1]

воот. но естественно на другом примере такое 'замыкание' совсем не означает, что все элементы
пройдены и матрица транспонирована. пришлось ввести битовый вектор, который при таком дедлоке
продолжал бы работу до победного конца.

пытался писать аккуратно, но на многое забил, чтобы кода было поменьше.

C++

#include <algorithm>
#include <iostream>
#include <vector>
 
template <typename Type>
using Iterator = typename Type::iterator;
 
template <typename T>
class Matrix
{
    using Vect = typename std::vector<T>;
    using Iter = Iterator<std::vector<T>>;
    Vect data_;
    size_t N_;
    size_t M_;
    size_t coords_to_index(size_t i, size_t j, size_t M) const { return i*M + j; }
    void index_to_coords(size_t d, size_t M, size_t& i, size_t& j) const { i = d / M; j = d - (d / M)*M; }
public:
    Matrix(size_t N, size_t M) : N_(N), M_(M), data_(N*M) {}
    size_t N() { return N_; };
    size_t M() { return M_; };
    Iter operator[](size_t i) { return data_.begin() + i*M_; } 
    void transpose()
    {
        size_t oldN{ N_ }, oldM{ M_ };
        std::swap(N_, M_);
 
        std::vector<bool> done(data_.size(), false);
        done[0] = true;
 
        for (auto it = done.begin() + 1; (it = std::find(done.begin(), done.end(), false)) != done.end();)
        {
            size_t what_to_mov = it - done.begin();
            size_t i{ 0 }, j { 0 };
            index_to_coords(what_to_mov, oldM, i, j);
            T temp = data_[what_to_mov];
            do {
                size_t where_to_mov = coords_to_index(j, i, M_);
                std::swap(temp, data_[where_to_mov]);
                index_to_coords(where_to_mov, oldM, i, j);
                done[what_to_mov] = true;
                what_to_mov = where_to_mov;
            } while(!done[what_to_mov]);
        }
    }
};
 
template <typename T>
static inline void print(Matrix<T>& a)
{
    for(size_t i = 0; i < a.N(); ++i)
    {
        for(size_t j = 0; j < a.M(); ++j)
            std::cout << a[i][j] << '\t';
        std::cout << std::endl;
    }
}
 
int main()
{
    const size_t N{ 5 }, M{ 2 };
    Matrix<int> a(N, M);
    for(size_t i = 0; i < N; ++i)
        for(size_t j = 0; j < M; ++j)
            a[i][j] = i*M + j + 1;
    print(a);
    std::cout << std::endl;
    a.transpose();
    print(a);
}

@Ferrari F1 805 / 532 / 158 Регистрация: 27.01.2015 Сообщений: 3,017 Записей в блоге: 1
	13.08.2016, 13:16	21
	Сообщение от JIawliet его код сверху, что вам мешает посмотреть? неудобно читать такой код (не в обиду мр.иксу ) 0

@Ferrari F1 805 / 532 / 158 Регистрация: 27.01.2015 Сообщений: 3,017 Записей в блоге: 1
	13.08.2016, 13:28	23
	JIawliet, мне интересно, по какому алгоритму ты будиш писать свой код, я просто не оч понил про твой способ без хранения индексов 0

@Ferrari F1 805 / 532 / 158 Регистрация: 27.01.2015 Сообщений: 3,017 Записей в блоге: 1
	13.08.2016, 19:22	26
	Сообщение от JIawliet Без сохранения индексов (создания map) не осилил( а знаешь, почему так? Допустим есть такой вектор-матрица 4х2 `1, 2, 3, 4, 5, 6, 7, 8` из него должен получиться вектор-матрица 2х4 `1, 3, 5, 7, 2, 4, 6, 8` таким образом, элемент со значением 2 переместиться с 1ого индекса на 4 если мы обменяем эти два значения, получится `1, 5, 3, 4, 2, 6, 7, 8` Таким образом, мы потеряли ту связь с элементом со значением 5, теперь он по первому индексу, когда в оригинале он находится на четвертому, тем самым мы потеряли закономерность по которой надо переставлять элементы. Стоит еще заметить, что это и есть цена за обмен значений внутри матрицы, не выходя за ее пределы (т.е. без копирования ее элементов) 0

@JIawliet 90 / 88 / 33 Регистрация: 20.07.2016 Сообщений: 403
	13.08.2016, 19:51 [ТС]	29
	Ferrari F1, а я так уже пробовал, но до ума не довел... тут дело в том, что те элементы, которые не входят в квадратную матрицу, потом переставляют элементы, которые входили в квадратную матрицу, с их законных мест) 0

@Ferrari F1 805 / 532 / 158 Регистрация: 27.01.2015 Сообщений: 3,017 Записей в блоге: 1
	13.08.2016, 19:53	30
	JIawliet, вобщемя я уже задалбался чесна гря) моих сил хватило на этот код с картой Пашел ка я рубиться в ксску_) 0

@JIawliet 90 / 88 / 33 Регистрация: 20.07.2016 Сообщений: 403
	13.08.2016, 13:20 [ТС]	22
	Сообщение от Ferrari F1 неудобно читать такой код на самом деле это так кажется)) поначалу да, а как привыкнешь - очень даже удобно... определенно у такого стиля есть некий порог вхождения) 0

@Ferrari F1 805 / 532 / 158 Регистрация: 27.01.2015 Сообщений: 3,017 Записей в блоге: 1
	13.08.2016, 19:43	28
	JIawliet, у меня еще есть такой вариант упрощения алгоритма: о всякой матрице с обоими размерами хотя бы больше одного можно говорить, что она содержит в себе квадратную матрицу В таком случае эту кв. матрицу поменяем кодом, что кинул zss, а остатки, что выходят из квадратной области, шлифануть каким-нить другим алгоритмом. Хотя, могу и ошибиться что это будет верным для решения 0

@JIawliet 90 / 88 / 33 Регистрация: 20.07.2016 Сообщений: 403
	13.08.2016, 20:02 [ТС]	31
	Ferrari F1, ну задача решена - решена, причем было предложено множество вариантов решения) 0

@Babysitter 245 / 139 / 53 Регистрация: 23.11.2015 Сообщений: 394
	13.08.2016, 20:05	32
	Сообщение от Ferrari F1 Babysitter, а у вас что получилось? я начал утром что-то писать, сейчас продолжу.. может чего и выйдет. 0

Хитрое транспонирование матрицы

Решение