Я заинтересован в следующей проблеме. В качестве входных данных нам дается «целевая перестановка» , а также упорядоченный список индексов i 1 , … , i m ∈ [ n - 1 ] . Затем, начиная со списка L = ( 1 , 2 , … , n ) (т. Е. Перестановки тождеств), на каждом временном шаге t ∈ [ m ] мы меняем элемент i...
Грубо говоря, сопоставление шаблонов перестановок имеет дело с проблемами следующего вида: При заданных перестановках в S n и в с содержит ли подпоследовательность длины , элементы которой упорядочены по σ ?ππ\piSNSNS_nσσ\sigmaSмSмS_mm ≤ nм≤Nm\leq nππ\pi mττ\tauммmσσ\sigma Например, если и σ = ⟨ 2...
Пусть - симметрический многочлен , т. Е. Такой многочлен, что для всех и все перестановки . Для удобства можно предположить, что является конечным полем, чтобы избежать решения проблем с моделью вычислений.е: KN→ Кf:Kn→Kf:\mathbb{K}^n \to \mathbb{K}x ∈ K n σ ∈ S n Kе( х ) = е( σ( х )...
Вот фон для этого вопроса. Мы с друзьями играли в игру, где каждый должен сделать подарок другим людям. Для того, чтобы определить, кто кому должен подарить подарок, мы решили провести жеребьевку. Но проблема в том, что кто-то может в итоге подарить себе подарки, что не смешно. Вы можете видеть,...
Учитывая сильные генераторы для группы ( G ≤SN, * )(G≤Sn,∗)(G \leq S_n, *) действуя на нити длины Nnn и элемент s ∈ { 0 , 1}Ns∈{0,1}ns \in \{0, 1\}^nНасколько сложно вычислить лексикографически минимальный элемент G . sG.sG.sорбита sss в гGG?...