Permutations of a list

In this file we prove properties about List.Permutations, a list of all permutations of a list. It is defined in Data.List.Defs.

Order of the permutations

Designed for performance, the order in which the permutations appear in List.Permutations is rather intricate and not very amenable to induction. That's why we also provide List.Permutations' as a less efficient but more straightforward way of listing permutations.

List.Permutations

TODO. In the meantime, you can try decrypting the docstrings.

List.Permutations'

The list of partitions is built by recursion. The permutations of [] are [[]]. Then, the permutations of a :: l are obtained by taking all permutations of l in order and adding a in all positions. Hence, to build [0, 1, 2, 3].permutations', it does

• [[]]
• [[3]]
• [[2, 3], [3, 2]]]
• [[1, 2, 3], [2, 1, 3], [2, 3, 1], [1, 3, 2], [3, 1, 2], [3, 2, 1]]
• [[0, 1, 2, 3], [1, 0, 2, 3], [1, 2, 0, 3], [1, 2, 3, 0], [0, 2, 1, 3], [2, 0, 1, 3], [2, 1, 0, 3], [2, 1, 3, 0], [0, 2, 3, 1], [2, 0, 3, 1], [2, 3, 0, 1], [2, 3, 1, 0], [0, 1, 3, 2], [1, 0, 3, 2], [1, 3, 0, 2], [1, 3, 2, 0], [0, 3, 1, 2], [3, 0, 1, 2], [3, 1, 0, 2], [3, 1, 2, 0], [0, 3, 2, 1], [3, 0, 2, 1], [3, 2, 0, 1], [3, 2, 1, 0]]

TODO

Show that l.Nodup → l.permutations.Nodup. See Data.Fintype.List.

theorem List.permutationsAux2_fst {α : Type u_1} {β : Type u_2} (t : α) (ts : List α) (r : List β) (ys : List α) (f : List α → β) : (List.permutationsAux2 t ts r ys f).fst = ys ++ ts

@[simp]

theorem List.permutationsAux2_snd_nil {α : Type u_1} {β : Type u_2} (t : α) (ts : List α) (r : List β) (f : List α → β) : (List.permutationsAux2 t ts r [] f).snd = r

@[simp]

theorem List.permutationsAux2_snd_cons {α : Type u_1} {β : Type u_2} (t : α) (ts : List α) (r : List β) (y : α) (ys : List α) (f : List α → β) : (List.permutationsAux2 t ts r (y :: ys) f).snd = f (t :: y :: ys ++ ts) :: (List.permutationsAux2 t ts r ys fun x => f (y :: x)).snd

theorem List.permutationsAux2_append {α : Type u_1} {β : Type u_2} (t : α) (ts : List α) (r : List β) (ys : List α) (f : List α → β) : (List.permutationsAux2 t ts [] ys f).snd ++ r = (List.permutationsAux2 t ts r ys f).snd

The r argument to permutationsAux2 is the same as appending.

theorem List.permutationsAux2_comp_append {α : Type u_1} {β : Type u_2} {t : α} {ts : List α} {ys : List α} {r : List β} (f : List α → β) : (List.permutationsAux2 t [] r ys fun x => f (x ++ ts)).snd = (List.permutationsAux2 t ts r ys f).snd

The ts argument to permutationsAux2 can be folded into the f argument.

theorem List.map_permutationsAux2' {α : Type u_3} {β : Type u_4} {α' : Type u_5} {β' : Type u_6} (g : α → α') (g' : β → β') (t : α) (ts : List α) (ys : List α) (r : List β) (f : List α → β) (f' : List α' → β') (H : ∀ (a : List α), g' (f a) = f' (List.map g a)) : List.map g' (List.permutationsAux2 t ts r ys f).snd = (List.permutationsAux2 (g t) (List.map g ts) (List.map g' r) (List.map g ys) f').snd

theorem List.map_permutationsAux2 {α : Type u_1} {β : Type u_2} (t : α) (ts : List α) (ys : List α) (f : List α → β) : List.map f (List.permutationsAux2 t ts [] ys id).snd = (List.permutationsAux2 t ts [] ys f).snd

The f argument to permutationsAux2 when r = [] can be eliminated.

theorem List.permutationsAux2_snd_eq {α : Type u_1} {β : Type u_2} (t : α) (ts : List α) (r : List β) (ys : List α) (f : List α → β) : (List.permutationsAux2 t ts r ys f).snd = List.map (fun x => f (x ++ ts)) (List.permutationsAux2 t [] [] ys id).snd ++ r

An expository lemma to show how all of ts, r, and f can be eliminated from permutationsAux2.

(permutationsAux2 t [] [] ys id).2, which appears on the RHS, is a list whose elements are produced by inserting t into every non-terminal position of ys in order. As an example:

#eval permutationsAux2 1 [] [] [2, 3, 4] id
-- [[1, 2, 3, 4], [2, 1, 3, 4], [2, 3, 1, 4]]

theorem List.map_map_permutationsAux2 {α : Type u_3} {α' : Type u_4} (g : α → α') (t : α) (ts : List α) (ys : List α) : List.map (List.map g) (List.permutationsAux2 t ts [] ys id).snd = (List.permutationsAux2 (g t) (List.map g ts) [] (List.map g ys) id).snd

theorem List.map_map_permutations'Aux {α : Type u_1} {β : Type u_2} (f : α → β) (t : α) (ts : List α) : List.map (List.map f) (List.permutations'Aux t ts) = List.permutations'Aux (f t) (List.map f ts)

theorem List.permutations'Aux_eq_permutationsAux2 {α : Type u_1} (t : α) (ts : List α) : List.permutations'Aux t ts = (List.permutationsAux2 t [] [ts ++ [t]] ts id).snd

theorem List.mem_permutationsAux2 {α : Type u_1} {t : α} {ts : List α} {ys : List α} {l : List α} {l' : List α} : l' ∈ (List.permutationsAux2 t ts [] ys fun x => l ++ x).snd ↔ ∃ l₁ l₂, l₂ ≠ [] ∧ ys = l₁ ++ l₂ ∧ l' = l ++ l₁ ++ t :: l₂ ++ ts

theorem List.mem_permutationsAux2' {α : Type u_1} {t : α} {ts : List α} {ys : List α} {l : List α} : l ∈ (List.permutationsAux2 t ts [] ys id).snd ↔ ∃ l₁ l₂, l₂ ≠ [] ∧ ys = l₁ ++ l₂ ∧ l = l₁ ++ t :: l₂ ++ ts

theorem List.length_permutationsAux2 {α : Type u_1} {β : Type u_2} (t : α) (ts : List α) (ys : List α) (f : List α → β) : List.length (List.permutationsAux2 t ts [] ys f).snd = List.length ys

theorem List.foldr_permutationsAux2 {α : Type u_1} (t : α) (ts : List α) (r : List (List α)) (L : List (List α)) : List.foldr (fun y r => (List.permutationsAux2 t ts r y id).snd) r L = (List.bind L fun y => (List.permutationsAux2 t ts [] y id).snd) ++ r

theorem List.mem_foldr_permutationsAux2 {α : Type u_1} {t : α} {ts : List α} {r : List (List α)} {L : List (List α)} {l' : List α} : l' ∈ List.foldr (fun y r => (List.permutationsAux2 t ts r y id).snd) r L ↔ l' ∈ r ∨ ∃ l₁ l₂, l₁ ++ l₂ ∈ L ∧ l₂ ≠ [] ∧ l' = l₁ ++ t :: l₂ ++ ts

theorem List.length_foldr_permutationsAux2 {α : Type u_1} (t : α) (ts : List α) (r : List (List α)) (L : List (List α)) : List.length (List.foldr (fun y r => (List.permutationsAux2 t ts r y id).snd) r L) = List.sum (List.map List.length L) + List.length r

theorem List.length_foldr_permutationsAux2' {α : Type u_1} (t : α) (ts : List α) (r : List (List α)) (L : List (List α)) (n : ℕ) (H : ∀ (l : List α), l ∈ L → List.length l = n) : List.length (List.foldr (fun y r => (List.permutationsAux2 t ts r y id).snd) r L) = n * List.length L + List.length r

@[simp]

theorem List.permutationsAux_nil {α : Type u_1} (is : List α) : List.permutationsAux [] is = []

@[simp]

theorem List.permutationsAux_cons {α : Type u_1} (t : α) (ts : List α) (is : List α) : List.permutationsAux (t :: ts) is = List.foldr (fun y r => (List.permutationsAux2 t ts r y id).snd) (List.permutationsAux ts (t :: is)) (List.permutations is)

@[simp]

theorem List.permutations_nil {α : Type u_1} : List.permutations [] = [[]]

theorem List.map_permutationsAux {α : Type u_1} {β : Type u_2} (f : α → β) (ts : List α) (is : List α) : List.map (List.map f) (List.permutationsAux ts is) = List.permutationsAux (List.map f ts) (List.map f is)

theorem List.map_permutations {α : Type u_1} {β : Type u_2} (f : α → β) (ts : List α) : List.map (List.map f) (List.permutations ts) = List.permutations (List.map f ts)

theorem List.map_permutations' {α : Type u_1} {β : Type u_2} (f : α → β) (ts : List α) : List.map (List.map f) (List.permutations' ts) = List.permutations' (List.map f ts)

theorem List.permutationsAux_append {α : Type u_1} (is : List α) (is' : List α) (ts : List α) : List.permutationsAux (is ++ ts) is' = List.map (fun x => x ++ ts) (List.permutationsAux is is') ++ List.permutationsAux ts (List.reverse is ++ is')

theorem List.permutations_append {α : Type u_1} (is : List α) (ts : List α) : List.permutations (is ++ ts) = List.map (fun x => x ++ ts) (List.permutations is) ++ List.permutationsAux ts (List.reverse is)