Current mood:

creative

Строка для медитации
Я выпал в осадок (довольно давно, надо сказать). Когда растворился обратно и подумал, что ЭТО нужно записать.

Такая вот маленькая неприментная строчечка из J4C:

y =. 6 6 6 1 0 1 t - (i.~y) { t =. /: /: y 0 1 2 0 0 1

Массив-результат обладает следующим свойством: r[i] это количество элементов равных y[i] с индексами меньшими i. То есть y[1] == 6, и r[1]==1 означает, что до этой шестёрки есть ещё только одна.

Генри Рич, комментируя этот глагол, говорит очевидные вещи, а неочевидные - не говорит :-) Так что пришлось самому. В результате многочасового битья головой об стену размышления я понял это. Попытаюсь изложить.

t это порядковый номер соответствующего элемента в y, есть термин такой, "ординал", так вот: t[i] это ординал y[i]-го. Убедиться в этом достаточно просто, скажу только что эта задача в Этюдах не продержалась и одного дня.

Всё множество элементов в y делятся на классы эквивалентности, а именно y1 и y2 попадают в один класс тогда и только тогда, когда они равны.

t обладает следующим свойством: для каждого класса эквивалентности соответствующие ординалы начинаются с самого левого элемента и идут последовательно. Выделенное было ключом для моего понимания. Смотрите сами: если бы было

/:/: 2 2 2 1 2 0

то это не противоречило бы определению глагола /:, однако вся конструкция бы рассыпалась.

(i.~y) это (y i. y). Важно то, что здесь классы эквивалентности помечаются отдельными числами:

]x =. (i.~y) 6 6 6 1 0 1 0 0 0 3 4 3

Отмечу свойства x: x[i] <= i (очевидно) и числа-метки есть индекс первого числа соответствующего класса эквивалентности (это следует просто из определения i.).

Вот теперь ключевой момент: пусть задан какой-нибудь класс эквивалентности I (множество индексов). Утверждения:

Для любого i1, i2 \in I => y[i1]==y[i2].
Есть минимальный индекс im, im \in I.
В t значения на этих индексах идут по порядку, t[im] самый маленький.
В x значения на этих индексах равны im: x[i]==im для всех i \in I.
Следовательно, z =. x { t будет z[i]==t[im] для всех i \in I.
Следовательно, разность r = t - z будет принимать последовательные значения r[i] = 0, 1, .. ,k на индексах i \in I.

Вот и всё. Спустя некоторое время это станет мегаочевидно, и врядли будет стоить столько слов, сколько я сейчас накатал. Но сейчас оно того стОит!

Тацитная форма

([: /: /:) - i.~ { [: /: /: +- [: +---+- /: | +- /: +- - --+ +- ~ --- i. | +- { +---+ +- [: +-----+- /: +- /:

Quiz: как избавиться от дублирования ([:/:/:)?