Еще одно решение задачи о педантичном пассажире

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

Как я тогда и предположил, такой простой ответ можно получить почти без вычислений. Достаточно установить взаимно однозначное соответствие между перестановкой, описывающей рассадку пассажиров, и некоторой другой вспомогательной перестановкой, как изображено на схеме в примере:

$$\tikzcdset{arrow style=tikz,diagrams={>=stealth}} \begin{matrix} \left(\begin{tikzcd}[row sep=14pt,column sep=12pt] 1\ar[d] & 2\ar[d] & 3\ar[d] & 4\ar[d] & 5 & 6\ar[d] & 7 & 8 \\ \textcolor{blue}{4}\ar[urrr,dotted,looseness=1,in=155] & \textcolor{blue}{6}\ar[urrrr,dotted,looseness=1,in=160] & \textcolor{blue}{1}\ar[ull,dotted] & \textcolor{blue}{2}\ar[ull,dotted] & \bf{5} & \textcolor{blue}{3}\ar[ulll,dotted] & \bf{8} & \bf{7} \end{tikzcd}\right) &\longleftrightarrow& \begin{tikzcd}[column sep=8pt] \bf{5} & \bf{8} & \bf{7} & \textcolor{blue}{1}\ar[r,dotted] & \textcolor{blue}{4}\ar[r,dotted] & \textcolor{blue}{2}\ar[r,dotted] & \textcolor{blue}{6}\ar[r,dotted] & \textcolor{blue}{3}\ar[llll,dotted,looseness=0.5,in=-60,out=-120] \end{tikzcd} \end{matrix}$$

Здесь я нарисовал стрелками, как в цикле переходят элементы друг в друга. Чтобы получить вспомогательную перестановку, нужно переместить в конец элементы цикла, содержащего элемент 1, начиная как раз с него.

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

Таким образом, мы установили биекцию (взаимно однозначное соответствие) между перестановками, при которой элементы цикла, содержащего элемент 1, переходят в элемент 1 и всех соседей справа. При усреднении по всем перестановкам любой элемент, в том числе 1, оказывается в середине (на каждую перестановку, где этот элемент сдвинут влево от центра, есть зеркальная перестановка, где он сдвинут на такое же расстояние вправо). Поэтому среднее количество соседей слева и справа совпадает и равно $$(n-1)/2$$.

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

RSS, формулы и Feedly

Постоянные читатели помнят, что у меня есть сервис по превращению математических формул в картинки и редактор для создания математических текстов. С заменой формул на картинки на обычных веб-страницах проблем нет, вопрос в том, как поступать с RSS?

Еще в 2011 году я стал отдавать в RSS растровые картинки, потому что непонятно, в каком окружении будет отображаться контент оттуда. А на обычных веб-страницах js-код определял, есть ли в браузере поддержка SVG, и в этом случае подключал красивые векторные картинки.

Когда в 2013 году прекратила работать rss-читалка Google Reader, народ в основном стал использовать Feedly. Напомню, что тогда Feedly работал через API Google Reader. Они подсуетились и написали свой бэкенд, чтобы не только не растерять свою аудиторию, но и подхватить доставшуюся даром аудиторию сервиса гугла.

У Feedly была одна особенность с отображением картинок: они принудительно становились плавающими (включалось css-свойство float). Если в тексте встречается одна иллюстрация, это может быть нормально. Но математические тексты с обилием формул превращались в нечитаемую кашу. Я написал им в поддержку, никакого ответа не получил. И мне пришлось отключить преобразование формул в картинки: я отдавал вместо формул вроде $$E=mc^2$$ их исходный код $$E=mc^2$$.

Сейчас я решил проверить, не научился ли Feedly отображать нормально картинки. Оказалось, что научился. Если вы читаете этот текст через RSS в Feedly, можете в этом убедиться в предыдущем абзаце.

Чтобы два раза не вставать, я попросил ChatGPT составить xslt-преобразование для xml-кода rss-канала, которое бы облагородило внешний вид при открытии RSS в браузере. Я оставил по ссылке нейтральный стиль, но никто не мешает использовать CSS с фирменным дизайном. У меня получился такой xslt-файл:

<?xml version="1.0" encoding="UTF-8"?>
<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
    <xsl:template match="/">
        <html>
            <head>
                <title><xsl:value-of select="rss/channel/title" /></title>
                <style type="text/css">
                    a {
                        color: #56d;
                        text-decoration-thickness: 1px;
                        text-decoration-color: rgba(85, 102, 221, 0.5);
                    }
                    body {
                        max-width: 720px;
                        font: 16px/1.5 sans-serif;
                        margin: 0 auto;
                    }
                    h1, h2, h3 {
                        margin: 1em 0 0.25em;
                    }
                    p {
                        margin: 0 0 0.75em;
                    }
                </style>
            </head>
            <body>
                <h1>
                    <a href="{rss/channel/link}">
                        <xsl:value-of select="rss/channel/title" />
                    </a>
                </h1>
                <xsl:for-each select="rss/channel/item">
                    <div class="item">
                        <h2><a href="{link}"><xsl:value-of select="title" /></a></h2>
                        <div><xsl:value-of select="description" disable-output-escaping="yes" /></div>
                    </div>
                </xsl:for-each>
            </body>
        </html>
    </xsl:template>
</xsl:stylesheet>

Чтобы это заработало, нужно добавить ссылку на такой xslt-файл в RSS:

<?xml version="1.0" encoding="utf-8"?>
<?xml-stylesheet href="/_styles/rss.xslt" type="text/xsl"?>
<rss version="2.0">
    <channel>
	...
    </channel>
</rss>

Кстати, пока со всем этим возился, обнаружил, что в RSS сломалось отображение исходного кода: перестало работать сохранение переносов строк внутри тегов <pre><code>. Долго пытался понять, где ошибка, пока не осознал, что это сломался сам Feedly. Похоже, эта проблема наблюдается в любых источниках в Feedly за последние недели две. Заодно сейчас и проверим, нормально ли будет отформатирован код в этой заметке.

В заключение полезный совет: если хотите отладить RSS и не хотите ждать, пока Feedly проиндексирует новую запись, можете на экране добавления нового источника добавить в URL не меняющую смысла часть запроса. Тогда Feedly распарсит RSS на лету и отобразит три последних записи:

Добавлено позднее: оказывается, Feedly нормально отображает картинки только в веб-версии. В приложении на андроиде формулы ни в каком варианте не отображаются, не работает ни SVG и PNG в тегах img, ни SVG, добавленный напрямую в HTML. Буду считать, что это баг на их стороне, и ничего с этим делать не буду.

← сюда туда →