Background
“Create a function to generate a n*n spiral matrix with successive numbers starting from 1”. This was a coding question when I applied master of data science degree free years ago. I forgot this for years and I suddenly reminded this when I would like to find some coding challenges recently. I was not able to answer this question at that time but I think I am not managed to answer this after few years of study in python.
Procedure and explanation
Step 1
First of all, I will set a parameter n in the function to configure the dimension of the matrix. I will make use of numpy to create a n*n matrix square zero matrix by using the function numpy.zeros. This will provide a basic n*n matrix for filling in the numbers.
Step 2
Next, I will set up several additional parameters for to specify the starting and ending number of the rows and columns. Also, there will be a num parameter set as 1 initially so it can be added up successively.
Step 3
We will start from the number at the upper left corner and fill in the number from left to right. The row number will be locked as the row_start ‘0’ number and the column number will be filled in starting from col_start (0) to col_end-1. After one number has been filled in, the num parameter will be added by 1 so that the number will be filled up sequentially.
Step 4
Then, we will start filling in the number from the upper right corner to the lower right corner. Since we have already filled in one number in the first row, we will fill in n-1 number in this turn. Similar to step 3, the column number will be locked as col_end -1 and the row number will be filled in since the number of row_start+1 until the row_end-1.
Step 5
After that, we fill in numbers from the lower right corner to the left. Unlike step 3 and 4, we loop the number backward from the right to the left by using range(x,y,-1). We started from the col_end-2 and filling numbers along to col_start-1 (range(col_end-2, col_start-1,-1).
Step 6
We are going to fill in the numbers from the lower left corner up but this time we only need to fill in row number-2.
Step 7
After each lap has been finished, the start parameters of rows and columns will be added by 1 and end parameters will be minus by 1 so that the same procedure will be carried out again in a smaller square. This procedure will be looped continuously until all n*n numbers have been filled up.
To summarise this, the complete function will be:
Conclusion
After making the function, I noted that this function can only make a matrix filling in by clockwise order. How about if I want to add a parameter to control if it is filling in clockwise or anti-clockwise order? I changed a bit the python code so that the newer version of the function can handle that as well. For more details, please refer to my github repository.
creating a spiral array in python?
Me and my mate were trying to create a fun game in python where the elements entered in the array are accessed in a spiral manner. I have tried few methods like one given below (source).
The above statement accesses the elements in spiral loop and prints them for a defined array AE. I would like to know how can I transform a given array AE to a spiral one
9 Answers 9
You can build a spiral by starting near the center of the matrix and always turning right unless the element has been visited already:
Introductory remarks
The question is closely related to a problem of printing an array in spiral order. In fact, if we already have a function which does it, then the problem in question is relatively simple.
There is a multitude of resources on how to produce a spiral matrix or how to loop or print an array in spiral order. Even so, I decided to write my own version, using numpy arrays. The idea is not original but use of numpy makes the code more concise.
The other reason is that most of examples of producing a spiral matrix I found (including the code in the question and in the other answers) deal only with square matrices of size n x n for odd n. Finding the start (or end) point in matrices of other sizes may be tricky. For example, for a 3×5 matrix it can’t be the middle cell. The code below is general and the position of the starting (ending) point depends on the choice of the function spiral_xxx .
The first function unwraps an array in spiral order clockwise:
We can write this function on eight different ways depending on where we start and how we rotate the matrix. I’ll give another one, which is consistent (it will be evident later) with the matrix transformation in the image in the question. So, further on, I will be using this version:
Note that the end (or start) point is not the middle cell. This function works for all type of matrices but we will need a helper function that generates spiral indices:
Now come the two main functions. One transforms a matrix to a spiral form of the same dimensions, the other reverts the transformation:
Заполнение квадратной матрицы по спирали (Python)
Коротко объясню, для чего нужна переменная m. Обратите внимание на результирующую матрицу при n = 5:
Начиная со значения 17 мы заполняем новый виток до значения 19. То есть, имеем всего 3 значения: 17, 18, 19.
Для этого и используется коэффициент m, чтобы заново не штудировать все 5 значений.
Заполнение квадратной матрицы по спирали (Python): 7 комментариев
Никак не могу понять зачем вы делаете инкременты «i+=»1 и «v+=1», если используются «i in range» и «v in range».
Я ни в коем случае не критикую ваш код. Просто пытаюсь разобраться как это работает, поскольку являюсь очень начинающим программистом.
Заранее спасибо за ответ.
Добрый день, Лера.
Когда я писал алгоритм в коде сначала были конструкции i+=2 или i+=3, пока я не понял, что прибавлять единицу — это оптимальный вариант, но забыл, что цикл единицу и без меня прекрасно добавляет)
Поэтому вы правильно заметили, i+=1 и v+=1 там не нужны.
Они просто заставляют цикл каждый раз начинать работу «заново», просто с другим значением.
Если планируете использовать данный алгоритм, i+=1 и v+=1 вам не нужны.
Name already in use
learning-to-make-programs / README.md
- Go to file T
- Go to line L
- Copy path
- Copy permalink
- Open with Desktop
- View raw
- Copy raw contents Copy raw contents
Copy raw contents
Copy raw contents
learning to make programs
1. Заполнение произвольной матрицы по спирали.
Нужно средствами какого-нибудь языка программирования заполнять произвольную матрицу по спирали во внутрь начиная с первого элемента по часовой стрелке.
За не имением особых препочтений или требований языком программирования для решения задач выбираю Python, потому,что хочу потренироваться писать программы с его помощью.
В условии задачи не сказанно чем заполнять, откуда брать элементы, какого они типа.
Возможно следует создать нечто, что будет последовательно выдавать элементы для заполнения. Напрашивается метод get_element() он будет генератором элементов для заполнения матрицы.
Матрицу нужно гдето хранить, в какойто структуре. Так как природа элементов заранее не ясна, логично хранить строки матрицы как списки, а саму матрицу, как список списков
Информацию о размерах матрицы нужно получать от пользователя или иным способом, отнесем это к отдельному методу, чтобы иметь возможность модификации под меняющиеся варианты ввода, назовем метод get_sises(), пусть он возвращает кортеж (row_count,columns_count)
Итак есть генератор элементов, есть размеры матрицы, теперь нужно ее заполнить. Вот бы был некий метод, который зная куда был вставлен предыдущий элемент, выдавал координаты следующего.
Вообще способов заполнения матрицы может быть множество, оставим себе гибкость, пусть будет метод create_matrix(dimentions,generator,change_status=change_status_for_spiral), который примет размеры матрицы, генератор элементов и функцию перехода от статуса к статусу, а вернет заполненную матрицу.
Хорошо бы теперь эту матрицу пользователю показать, сделаем метод print_matrix(Matrix) который получив матрицу, выводит ее на печать.
Программа будет выглядеть как вызов одного метода:
Листинг скрипта на Python в jupiter реализующий заполнение 10 матриц случайных размерностей по спирали целыми числами начиная с 0:spiral_matrix.ipynb
Альтернативное решение, с использованием 4х специализированных функций, которые отвечают за заполнение одного направления от границы до границы и по очереди вызывают друг друга:
2. Быстрая сортировка с произвольной функцией сравнения.
Реализовать функцию быстрой сортировки с произвольной функцией сравнения
Сортировать будем список, так как он может хранить элементы любой природы.
Принципиально не имеет значения будет ли функция сравнения отвечать больше ли первый элемент второго или меньше, но для определенности пусть функция возвращает true если ее первый аргумент меньше второго и false в остальных случаях.
Чтобы проверить меньше ли второй аргумент первого, достаточно просто поменять их местами.
Будем считать однопорядковыми элементы которые не больше и не меньше друг друга.
Реализуем функцию быстрой сортировки которая берет случайный элемент списка и разделяет все элементы на три списка в первом все элементы меньше выбранного, во втором все однопорядковые с ним, в третьем все больше него, затем соберем их в один список предварительно рекурсивно применив эту функцию к первому и третьему списку.
Листинг скрипта на Python в jupiter реализующий алгоритм быстрой сортировки:sort.ipynb
3. Ранжирование текстов.
Задача: нужно ранжировать тексты.
Для начала нужно ранжировать тексты по частоте встречающегося в нем слова, в перспективе нужно ранжировать текст по какой то мере относительно нескольких слов
Задача будет состоять в том, что предварительно будет проведена индексация неких текстов, затем пользователь передает строку_запроса получет в ответ список названий текстов отранжированных по убыванию соответствия словам в строке запроса.
Где и как хранятся тексты в задаче не сказано, для простоты буду считать, что это txt файлы в одной общей папке.
Задачу можно разбить на две части: ИНДЕКСАЦИЯ, ЗАПРОС.
Но так по мере практической реализации, оказалось, что процесс индексации довольно длительный, то ИНДЕКСАЦИЮ пришлось разбить на 2 части: ИНДЕКСАЦИЯ И СОХРАНЕНИЕ РЕЗУЛЬТАТОВ, ЗАГРУЗКА ДАННЫХ ИНДЕКСАЦИИ
Теперь одна задача разделилась на 3 подзадачи:
1. ИНДЕКСАЦИЯ И СОХРАНЕНИЕ РЕЗУЛЬТАТОВ
2. ЗАГРУЗКА ДАННЫХ ИНДЕКСАЦИИ
Для решения задачи я создал 4 файла:
Он просто запускает главный скрипт main.py на исполнение
Подгружает некоторые общие для всех скриптов библиотеки и методы, вызывает диалог с пользователем и в зависимости от резултатов запускает с помощью метода exec() остальные скрипты, например скрипт Query.py:
С помощью PyQt5.QtWidgets.QFileDialog запрашивает директорию с файлами и директорию для сохранения результатов индексации, индексирует и сохраняет.
Запрашивает директорию с результатами индексации, загружает их для использования. В виду не маленького размера файла, в память загружаются только список слов, список файлов и список начальных позицый для загрузки ранжированных по убыванию частоты соответствующего слова в них, номеров файлов.
Скрипт запустится только если перед ним произошла загрузка результатов индексации. Запросит текстовую строку, разобьет ее на слова, произведет суммирование для всех встретившихся файлов частот вхождения каждого слова строки запроса и выведет 10 файлов ранжированных по убыванию суммарной частоты слов запроса в них.
Немного некрасиво, что часть интерфейса реализовано командной строкой, часть tkinter, часть PyQt5, но я не хотел сильно углубляться в объектноориентированные глубины tkinter и PyQt5, но и реализовывать сугубо терминальный диалог тоже не хотел.