Permutations from a list

A list l : List α can be interpreted as an Equiv.Perm α where each element in the list is permuted to the next one, defined as formPerm. When we have that Nodup l, we prove that Equiv.Perm.support (formPerm l) = l.toFinset, and that formPerm l is rotationally invariant, in formPerm_rotate.

When there are duplicate elements in l, how and in what arrangement with respect to the other elements they appear in the list determines the formed permutation. This is because List.formPerm is implemented as a product of Equiv.swaps. That means that presence of a sublist of two adjacent duplicates like [..., x, x, ...] will produce the same permutation as if the adjacent duplicates were not present.

The List.formPerm definition is meant to primarily be used with Nodup l, so that the resulting permutation is cyclic (if l has at least two elements). The presence of duplicates in a particular placement can lead List.formPerm to produce a nontrivial permutation that is noncyclic.

def List.formPerm {α : Type u_1} [DecidableEq α] (l : List α) : Equiv.Perm α

A list l : List α can be interpreted as an Equiv.Perm α where each element in the list is permuted to the next one, defined as formPerm. When we have that Nodup l, we prove that Equiv.Perm.support (formPerm l) = l.toFinset, and that formPerm l is rotationally invariant, in formPerm_rotate.

Equations

• l.formPerm = (List.zipWith Equiv.swap l l.tail).prod

@[simp]

theorem List.formPerm_nil {α : Type u_1} [DecidableEq α] : [].formPerm = 1

@[simp]

theorem List.formPerm_singleton {α : Type u_1} [DecidableEq α] (x : α) : [x].formPerm = 1

@[simp]

theorem List.formPerm_cons_cons {α : Type u_1} [DecidableEq α] (x y : α) (l : List α) : (x :: y :: l).formPerm = Equiv.swap x y * (y :: l).formPerm

theorem List.formPerm_pair {α : Type u_1} [DecidableEq α] (x y : α) : [x, y].formPerm = Equiv.swap x y

theorem List.mem_or_mem_of_zipWith_swap_prod_ne {α : Type u_1} [DecidableEq α] {l l' : List α} {x : α} : (List.zipWith Equiv.swap l l').prod x ≠ x → x ∈ l ∨ x ∈ l'

theorem List.zipWith_swap_prod_support' {α : Type u_1} [DecidableEq α] (l l' : List α) : {x : α | (List.zipWith Equiv.swap l l').prod x ≠ x} ≤ ↑(l.toFinset ⊔ l'.toFinset)

theorem List.zipWith_swap_prod_support {α : Type u_1} [DecidableEq α] [Fintype α] (l l' : List α) : (List.zipWith Equiv.swap l l').prod.support ≤ l.toFinset ⊔ l'.toFinset

theorem List.support_formPerm_le' {α : Type u_1} [DecidableEq α] (l : List α) : {x : α | l.formPerm x ≠ x} ≤ ↑l.toFinset

theorem List.support_formPerm_le {α : Type u_1} [DecidableEq α] (l : List α) [Fintype α] : l.formPerm.support ≤ l.toFinset

theorem List.mem_of_formPerm_apply_ne {α : Type u_1} [DecidableEq α] {l : List α} {x : α} (h : l.formPerm x ≠ x) : x ∈ l

theorem List.formPerm_apply_of_not_mem {α : Type u_1} [DecidableEq α] {l : List α} {x : α} (h : x ∉ l) : l.formPerm x = x

theorem List.formPerm_apply_mem_of_mem {α : Type u_1} [DecidableEq α] {l : List α} {x : α} (h : x ∈ l) : l.formPerm x ∈ l

theorem List.mem_of_formPerm_apply_mem {α : Type u_1} [DecidableEq α] {l : List α} {x : α} (h : l.formPerm x ∈ l) : x ∈ l

@[simp]

theorem List.formPerm_mem_iff_mem {α : Type u_1} [DecidableEq α] {l : List α} {x : α} : l.formPerm x ∈ l ↔ x ∈ l

@[simp]

theorem List.formPerm_cons_concat_apply_last {α : Type u_1} [DecidableEq α] (x y : α) (xs : List α) : (x :: (xs ++ [y])).formPerm y = x

@[simp]

theorem List.formPerm_apply_getLast {α : Type u_1} [DecidableEq α] (x : α) (xs : List α) : (x :: xs).formPerm ((x :: xs).getLast ⋯) = x

@[simp]

theorem List.formPerm_apply_getElem_length {α : Type u_1} [DecidableEq α] (x : α) (xs : List α) : (x :: xs).formPerm (x :: xs)[xs.length] = x

@[deprecated List.formPerm_apply_getElem_length]

theorem List.formPerm_apply_get_length {α : Type u_1} [DecidableEq α] (x : α) (xs : List α) : (x :: xs).formPerm ((x :: xs).get ⟨xs.length, ⋯⟩) = x

theorem List.formPerm_apply_head {α : Type u_1} [DecidableEq α] (x y : α) (xs : List α) (h : (x :: y :: xs).Nodup) : (x :: y :: xs).formPerm x = y

theorem List.formPerm_apply_getElem_zero {α : Type u_1} [DecidableEq α] (l : List α) (h : l.Nodup) (hl : 1 < l.length) : l.formPerm l[0] = l[1]

@[deprecated List.formPerm_apply_getElem_zero]

theorem List.formPerm_apply_get_zero {α : Type u_1} [DecidableEq α] (l : List α) (h : l.Nodup) (hl : 1 < l.length) : l.formPerm (l.get ⟨0, ⋯⟩) = l.get ⟨1, hl⟩

theorem List.formPerm_eq_head_iff_eq_getLast {α : Type u_1} [DecidableEq α] (l : List α) (x y : α) : (y :: l).formPerm x = y ↔ x = (y :: l).getLast ⋯

theorem List.formPerm_apply_lt_getElem {α : Type u_1} [DecidableEq α] (xs : List α) (h : xs.Nodup) (n : ℕ) (hn : n + 1 < xs.length) : xs.formPerm xs[n] = xs[n + 1]

@[deprecated List.formPerm_apply_lt_getElem]

theorem List.formPerm_apply_lt_get {α : Type u_1} [DecidableEq α] (xs : List α) (h : xs.Nodup) (n : ℕ) (hn : n + 1 < xs.length) : xs.formPerm (xs.get ⟨n, ⋯⟩) = xs.get ⟨n + 1, hn⟩

theorem List.formPerm_apply_getElem {α : Type u_1} [DecidableEq α] (xs : List α) (w : xs.Nodup) (i : ℕ) (h : i < xs.length) : xs.formPerm xs[i] = xs[(i + 1) % xs.length]

@[deprecated List.formPerm_apply_getElem]

theorem List.formPerm_apply_get {α : Type u_1} [DecidableEq α] (xs : List α) (h : xs.Nodup) (i : Fin xs.length) : xs.formPerm (xs.get i) = xs.get ⟨(↑i + 1) % xs.length, ⋯⟩

theorem List.support_formPerm_of_nodup' {α : Type u_1} [DecidableEq α] (l : List α) (h : l.Nodup) (h' : ∀ (x : α), l ≠ [x]) : {x : α | l.formPerm x ≠ x} = ↑l.toFinset

theorem List.support_formPerm_of_nodup {α : Type u_1} [DecidableEq α] [Fintype α] (l : List α) (h : l.Nodup) (h' : ∀ (x : α), l ≠ [x]) : l.formPerm.support = l.toFinset

theorem List.formPerm_rotate_one {α : Type u_1} [DecidableEq α] (l : List α) (h : l.Nodup) : (l.rotate 1).formPerm = l.formPerm

theorem List.formPerm_rotate {α : Type u_1} [DecidableEq α] (l : List α) (h : l.Nodup) (n : ℕ) : (l.rotate n).formPerm = l.formPerm

theorem List.formPerm_eq_of_isRotated {α : Type u_1} [DecidableEq α] {l l' : List α} (hd : l.Nodup) (h : l ~r l') : l.formPerm = l'.formPerm

theorem List.formPerm_append_pair {α : Type u_1} [DecidableEq α] (l : List α) (a b : α) : (l ++ [a, b]).formPerm = (l ++ [a]).formPerm * Equiv.swap a b

theorem List.formPerm_reverse {α : Type u_1} [DecidableEq α] (l : List α) : l.reverse.formPerm = l.formPerm⁻¹

theorem List.formPerm_pow_apply_getElem {α : Type u_1} [DecidableEq α] (l : List α) (w : l.Nodup) (n i : ℕ) (h : i < l.length) : (l.formPerm ^ n) l[i] = l[(i + n) % l.length]

@[deprecated List.formPerm_pow_apply_getElem]

theorem List.formPerm_pow_apply_get {α : Type u_1} [DecidableEq α] (l : List α) (h : l.Nodup) (n : ℕ) (i : Fin l.length) : (l.formPerm ^ n) (l.get i) = l.get ⟨(↑i + n) % l.length, ⋯⟩

theorem List.formPerm_pow_apply_head {α : Type u_1} [DecidableEq α] (x : α) (l : List α) (h : (x :: l).Nodup) (n : ℕ) : ((x :: l).formPerm ^ n) x = (x :: l)[n % (x :: l).length]

theorem List.formPerm_ext_iff {α : Type u_1} [DecidableEq α] {x y x' y' : α} {l l' : List α} (hd : (x :: y :: l).Nodup) (hd' : (x' :: y' :: l').Nodup) : (x :: y :: l).formPerm = (x' :: y' :: l').formPerm ↔ x :: y :: l ~r x' :: y' :: l'

theorem List.formPerm_apply_mem_eq_self_iff {α : Type u_1} [DecidableEq α] (l : List α) (hl : l.Nodup) (x : α) (hx : x ∈ l) : l.formPerm x = x ↔ l.length ≤ 1

theorem List.formPerm_apply_mem_ne_self_iff {α : Type u_1} [DecidableEq α] (l : List α) (hl : l.Nodup) (x : α) (hx : x ∈ l) : l.formPerm x ≠ x ↔ 2 ≤ l.length

theorem List.mem_of_formPerm_ne_self {α : Type u_1} [DecidableEq α] (l : List α) (x : α) (h : l.formPerm x ≠ x) : x ∈ l

theorem List.formPerm_eq_self_of_not_mem {α : Type u_1} [DecidableEq α] (l : List α) (x : α) (h : x ∉ l) : l.formPerm x = x

theorem List.formPerm_eq_one_iff {α : Type u_1} [DecidableEq α] (l : List α) (hl : l.Nodup) : l.formPerm = 1 ↔ l.length ≤ 1

theorem List.formPerm_eq_formPerm_iff {α : Type u_1} [DecidableEq α] {l l' : List α} (hl : l.Nodup) (hl' : l'.Nodup) : l.formPerm = l'.formPerm ↔ l ~r l' ∨ l.length ≤ 1 ∧ l'.length ≤ 1

theorem List.form_perm_zpow_apply_mem_imp_mem {α : Type u_1} [DecidableEq α] (l : List α) (x : α) (hx : x ∈ l) (n : ℤ) : (l.formPerm ^ n) x ∈ l

theorem List.formPerm_pow_length_eq_one_of_nodup {α : Type u_1} [DecidableEq α] (l : List α) (hl : l.Nodup) : l.formPerm ^ l.length = 1