Началось всё с того, что не нашел я библиотеки для JavaScript, которая вычисляет собственные векторы для комплекснозначной матрицы 4х4. Пришлось писать самому.
И в ходе реализации встала передо мной этакая бодренькая микрозадачка – из набора чисел «1, 2, 3, 4» вычеркнули два числа «x, y» (неодинаковых – кто-то придет завтра и задаст эти два числа, а мы сегодня должны приготовиться), требуется объяснить компьютеру, как определить оставшиеся, невычеркнутые числа. И я завис – все идеи, которые приходили мне в голову, казались «неспортивными и чрезмерными» – ну не пузырьковой же сортировкой перебирать четыре числа, должно же быть что-то элегантное. Например, если вычеркнуто не два, а три числа «x, y, z» из четырех «x, y, z, t» (которые «1, 2, 3, 4»), то оставшееся число «t» находится так: t = 10 – (x+y+z). Потому что t+x+y+z = 10 (всегда: 10=1+2+3+4). Вполне элегантно для одного оставшегося числа. А для двух чисел – как быть с элегантностью?!
Решение я нашел – озарило по дороге домой – прям шарахнуло с неба по башке; я даже не поверил сначала, что это оно – показалось мороком усталого мозга. И оно работает не только для четырех чисел – можно решить задачу «из n последовательных чисел вычеркнуто k неупорядоченных различных чисел, требуется вернуть остаток» (что осталось на трубе).
Я предложил эту задачку с «n, k»-условием знакомым программистам в качестве застольного анекдота, для развлечения (сам я не программист, честно – мне просто сильно занадобилось объяснить Яваскрипту, как вычислять собственные векторы комплекснозначной матрицы 4х4). Сначала я выслушал их предложения (предлагали «упорядочивание k чисел с последующим перебором n чисел» и «воспользоваться встроенной функцией вычитания множеств»). Потом я рассказал свое решение. Они сказали: «Ну круто, да».
Не думаю, что я совершил великое открытие – скорее всего, этот подход где-нибудь преподается студентам и давно вшит во все языки программирования – но заинтересованные люди, которые эту мелочь не знали (например, я не знал, мои друзья не знали), мне кажется, получат удовольствие – когда ознакомятся.
Постановка задачи
Есть массив M[i] = i, при i = 1 … n. Числа, которые надо вычеркнуть из массива M, находятся в массиве V. Массив V: размером k, числа в этом массиве не повторяются и не обязательно упорядочены. Требуется вернуть массив невычеркнутых чисел.
Алгоритм
- Перестановки в массиве М:
M[j] = V[j], M[V[j]] = j (при j = 1 … k).
Всего k перестановок.
- Невычеркнутые числа теперь находятся в хвосте массива M:
M[(k+1), n] (этот хвост и вернуть).
Пример действия алгоритма (n=4, k=2)
M = {1, 2, 3, 4},
Задаем V = {4, 3}. (в хвосте после перестановок ожидаем числа: «1» и «2»)
Перестановки:
M[1] = V[1] = 4, M[V[1]]= M[4] = 1; (теперь M = {4, 2, 3, 1}),
M[2] = V[2] = 3, M[V[2]] = M[3] = 2; (теперь M = {4, 3, 2, 1}).
Хвост массива M: M[3,4] = {2, 1} – то, что нужно.
Пример применения в жизни
Вот это я и заюзал, когда объяснял компу, как надо решать систему линейных уравнений методом Гаусса.
Сам код разместил на GitHub пользователь Хабра Сергей (за что ему огромное спасибо) Благодаря ему можно показать код, где это использовано:
функция «zMatrix_minus_lambda_SV» (напр., строки: 266-267).
А надо всё это мне было, чтобы написать калькулятор «Прашкевич», который строит спектры поглощения и отражения света стопкой пластин.
Ссылки:
- Прашкевич на Бегете
- Прашкевич на GitHub
- Статья с описанием Прашкевича (зачем и почему)
- Юмористический рассказ «Как неофит познавал яваскрипт» (как я страдал)
Конец.
