Documentation

Mathlib.GroupTheory.Perm.List

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 α) :

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
Instances For
    @[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 : List α} {l' : List α} {x : α} :
    (List.zipWith Equiv.swap l l').prod x xx l x l'
    theorem List.zipWith_swap_prod_support' {α : Type u_1} [DecidableEq α] (l : List α) (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 : List α) (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 : xl) :
    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
    theorem List.formPerm_apply_get_length {α : Type u_1} [DecidableEq α] (x : α) (xs : List α) :
    (x :: xs).formPerm ((x :: xs).get xs.length, ) = x
    @[simp, deprecated List.formPerm_apply_get_length]
    theorem List.formPerm_apply_nthLe_length {α : Type u_1} [DecidableEq α] (x : α) (xs : List α) :
    (x :: xs).formPerm ((x :: xs).nthLe 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]
    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
    @[deprecated List.formPerm_apply_get_zero]
    theorem List.formPerm_apply_nthLe_zero {α : Type u_1} [DecidableEq α] (l : List α) (h : l.Nodup) (hl : 1 < l.length) :
    l.formPerm (l.nthLe 0 ) = l.nthLe 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]
    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
    @[deprecated List.formPerm_apply_lt_get]
    theorem List.formPerm_apply_lt {α : Type u_1} [DecidableEq α] (xs : List α) (h : xs.Nodup) (n : ) (hn : n + 1 < xs.length) :
    xs.formPerm (xs.nthLe n ) = xs.nthLe (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]
    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,
    @[deprecated List.formPerm_apply_get]
    theorem List.formPerm_apply_nthLe {α : Type u_1} [DecidableEq α] (xs : List α) (h : xs.Nodup) (n : ) (hn : n < xs.length) :
    xs.formPerm (xs.nthLe n hn) = xs.nthLe ((n + 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 : List α} {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]
    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,
    @[deprecated List.formPerm_pow_apply_get]
    theorem List.formPerm_pow_apply_nthLe {α : Type u_1} [DecidableEq α] (l : List α) (h : l.Nodup) (n : ) (k : ) (hk : k < l.length) :
    (l.formPerm ^ n) (l.nthLe k hk) = l.nthLe ((k + 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).get n % (x :: l).length,
    theorem List.formPerm_ext_iff {α : Type u_1} [DecidableEq α] {x : α} {y : α} {x' : α} {y' : α} {l : List α} {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 : xl) :
    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 : List α} {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