Индексация вращательной симметрии в одномерном "квадратном" массиве

Question

У меня есть одномерный массив длины size * size, представляющий квадратное поле значений. Моя цель - повернуть массив на месте ( предыдущий вопрос ). В настоящее время у меня есть проблемы с получением правильного индекса во внутренних кольцах. В чем ошибка в моем алгоритме?

Это мой код, пропустите ниже для объяснения и примеров.

Код (Rust 1.41.0)

fn rotate_square_slice<T>(slice: &mut [T], size: usize) {
    for r in 0..(size + 1) / 2 {
        // current ring side length
        let l = size - 1 - r;
        for i in r..l {             
            let a = size *    r    +  r+i ;
            let b = size *  (r+i)  +  l-r ;
            let c = size *  (l-r)  + l-r-i;
            let d = size * (l-r-i) +   r  ;

            slice.swap(a, b);
            slice.swap(a, c);
            slice.swap(a, d);
        }
    }
}

Объяснение

array = [A, B, C, D, E,
         A, B, C, D, E,
         A, B, C, D, E,
         A, B, C, D, E,
         A, B, C, D, E]

ring 0:         |   symmetries:
                |
    A B C D E   |   A . . . E     . B . . .     . . C . .
    A . . . E   |   . . . . .     . . . . E     . . . . .        
    A . . . E   |   . . . . .  +  . . . . .  +  A . . . E  +  etc...
    A . . . E   |   . . . . .     A . . . .     . . . . .
    A B C D E   |   A . . . E     . . . D .     . . C . . 

ring 1:         |   symmetries:
                |
    . . . . .   |   . . . . .   . . . . . 
    . B C D .   |   . B . D .   . . C . .
    . B . D .   |   . . . . .   . B . D .
    . B C D .   |   . B . D .   . . C . .
    . . . . .   |   . . . . .   . . . . . 

Пример шага итерации

   0 1 2 3 4

0  . a . . .
1  . . . . b
2  . . . . .
3  d . . . .
4  . . . c .

size = 5    |    position(a) = (  r  ,  r+i ) = (0, 1)
r    = 0    |    position(b) = ( r+i ,  l-r ) = (1, 4)
l    = 4    |    position(c) = ( l-r , l-r-i) = (4, 3)
i    = 1    |    position(d) = (l-r-i,   r  ) = (3, 0)

Пример вывода

Используя 1D-индексирование для 5 * 5 "квадратного" массива, здесь приведены желаемые и текущие выходные данные всех наборов индексов (a, b, c, d):

desired output   | current output   | parameters
                 |                  | r  l  i
( 0,  4, 24, 20) | ( 0,  4, 24, 20) | 0  4  0
( 1,  9, 23, 15) | ( 1,  9, 23, 15) | 0  4  1
( 2, 14, 22, 10) | ( 2, 14, 22, 10) | 0  4  2
( 3, 19, 21,  5) | ( 2, 14, 22, 10) | 0  4  3
                 |                  |
( 6,  8, 18, 16) | ( 7, 12, 11,  6) | 1  3  1 <- mistake
( 7, 13, 17, 11) | ( 8, 17, 10,  1) | 1  3  2 <- mistake
                 |                  |

Я надеюсь, что иллюстрации ASCII помогут продемонстрировать, чего я хочу. Если требуется уточнение, пожалуйста, дайте мне знать.

Answer 1

Проблема была вызвана использованием l в расчетах вообще.

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

Как упомянуто @Gene в комментариях, вращая строку i ', оставленную с шагом i, и столбец j' вниз на j шаги, можно было бы достичь аналогичного результата. Я по-прежнему считаю, что подход, который я представляю ниже, имеет свои достоинства, поскольку его можно легко расширить, чтобы можно было произвольно проверять условия, какие кортежи элементов вращаются.

enum Rotation {
    Clockwise,
    Counterclockwise,
}

fn rotate_square_slice<T>(slice: &mut [T], s: usize, rotation: Rotation) {
    // iterate ringwise, from outer to inner
    // skip center when size % 2 == 1
    for r in 0..s / 2 { 
        // for all unique indices under rotational symmetry ...
        for i in 0..s - (2 * r) - 1{
            // ... get their 4 corresponding positions ...
            let a = s * (   r   ) +   r+i   ;
            let b = s * (  r+i  ) +  s-r-1  ;
            let c = s * ( s-r-1 ) + s-r-i-1 ;
            let d = s * (s-r-i-1) +    r    ;

            //... and swap them in the correct direction.
            match rotation {
                Rotation::Clockwise => {
                    slice.swap(a, b);
                    slice.swap(a, c);
                    slice.swap(a, d);
                },
                Rotation::Counterclockwise => {
                    slice.swap(a, b);
                    slice.swap(c, d);
                    slice.swap(b, d);
                }
            }
        }
    }
}

Огромное спасибо @Jmb! Не видел дерева для деревьев.

Из-за линейного расположения среза легко повернуть подлису некоторого Ve c, используя chunks(). Ухоженная!