Как сформировать уже повернутую матрицу из массива?

Question

[Алексей Николаев]

Добрый день.
Есть одномерный массив. Элементы массива выводятся по несколько в строку, до заданного предела, затем начинается новая (аналогично array_chunk($array, 3) - т.е. создается матрица).

Нужно в этом цикле создать уже повернутую на 90 градусов по часовой стрелке матрицу, без вложенных циклов и прочих повышающих сложность алгоритма штук. Схема, что хочу сделать: вариант 2 - то, что нужно получить за O(n) именно из исходного массива.

spoiler

Мой работающий вариант, на js. Что хочется сделать в итоге:

var array = ['1','2','3','4','5','6','7','8','9','10','11','12'];

for(var elems = 0; elems < array.length; elems++) {
    var index = ?; // расчет индекса, как будто он находится в повернутой матрице (вариант 2). Т.е. 2 = 6, 3 = 9 и т.п.
}

Пробовал самую разную логику вычисления, не получилось без вложенных циклов.
Буду рад любым советам по теме (в т.ч. и общему описанию возможного алгоритма), спасибо.

Comments

[Денис Загаевский]

В вашем примере непонятно, по какому принципу в первом столбце больше строк, чем в остальных.

[Алексей Николаев]

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

[AVKor]

повернутую на 90 градусов по часовой стрелке матрицу

В примере нет "повернутой на 90 градусов по часовой стрелке матрицы". При повороте таком получается из варианта 1 вовсе не вариант 2.

Answer 1

[Евгений Быков]

Формула для преобразования, изображенного на рисунке (т.е., не поворот на 90 градусов, а транспонирование):

index = 1 + [i / m] + n * (i % m)

В этой формуле индекс i меняется от 0 до size - 1 (size - размер массива), n - число столбцов (а после преобразования - строк), m - число строк (а после преобразования - столбцов), [i / m] - целая часть от деления i на m, i % m - остаток от деления i на m.

Очевидно, что m = [ (size - 1) / n ] + 1

При size = 12, n = 4 (соответственно, m = 3), получим следующую последовательность значений index:

i     [i / 3]    4 * (i % 3)    index
0:  1 +  0    +     4 * 0    =    1
1:  1 +  0    +     4 * 1    =    5
2:  1 +  0    +     4 * 2    =    9
3:  1 +  1    +     4 * 0    =    2
4:  1 +  1    +     4 * 1    =    6
5:  1 +  1    +     4 * 2    =   10
6:  1 +  2    +     4 * 0    =    3
7:  1 +  2    +     4 * 1    =    7
...

, т.е., как в примере работающего варианта

Answer 2

[Дмитрий Беляев]

На рисунке матрица отраженная по диагонали.
Но все таки задание звучит как повернутая на 90 градусов по часовой, вот алгоритм:

//Исходные данные
var arr = ['1','2','3','4','5','6','7','8','9','10','11','12'];
var xlen = 4; //длина строки, или в повернутой матрице столбца

//Предварительные вычисления
var ylen = Math.ceil(arr.length / xlen); //Длина столбца
var matrix = new Array(xlen); //Строки результата
//Заполним строки массивами ячеек
for(var i = xlen; i--;) {
    matrix[i] = new Array(ylen);
}

//я пробегаю массив в обратном порядке
//так как это более оптимально по скорости
for(var i = arr.length; i--;) {
    //Вычислим координаты из i
    var x = ylen - 1 - Math.floor(i / xlen);
    var y = i % xlen;
    //и заполним матрицу
    matrix[y][x] = arr[i];
}

Comments

[Денис Загаевский]

Оптимально по скорости? Почему? И почему бы это не сделать вложенным циклом, избавившись от делений?

[Дмитрий Беляев]

Денис Загаевский: насчет обратного прохода - оптимальность в банальном сокращении операций на итерацию
Насчет вложенных циклов, в условии сказано без них, и за это реально штрафуют в олимпиадных задачах, на которую очень уж похожа данная задача. К тому же, такой подход даст arr.length % (xlen * ylen) бесполезных итераций

[Денис Загаевский]

Дмитрий Беляев: лол, какой бред. Какое сокращение операций? О каких бесполезных итерациях речь? Посчитали бы хоть для начала, что делаете вы и что было бы при нормальном подходе. И в каких олимпиадах штрафуют за код?

[Дмитрий Беляев]

Денис Загаевский: дан массив из 13 элементов, разбиваем его в матрицу 4х4, в Вашем варианте будет 16 итераций, в моем 13. Дан массив из 4001 элементов, разбиваем его в матрицу 201х200...

[Денис Загаевский]

Дмитрий Беляев: в вашем варианте будет 26 делений, 26 вызовов floor и 26 вычитаний, в моём - 4 умножения, 13 сложений и 17 логических "и", это помимо инкрементов, их будет примерно одинаковое количество. Вот и считайте, что выгоднее.