Timeline for Bubblesort with a twist: a tricky termination
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 9, 2023 at 17:21 | comment | added | darij grinberg | Your nice proof for Question 2 is now (in a heavily elementarized and detailed form, because for some reason I decided to make this an introductory example on monovariants) the solution to Exercise 6.3.1 (c) on my worksheet 6 in Fall 2023 Math 235. | |
| Oct 24, 2023 at 20:41 | comment | added | Jan Nienhaus | You should rather suppose $i>j$. The idea is that if $a_i$ is a barrier for $a_j$, then $a_j$ will never be able to end up to the right of $a_i$ along any path of $P$-moves. | |
| Oct 24, 2023 at 4:29 | history | edited | user21820 | CC BY-SA 4.0 |
minor improvements
|
| Oct 24, 2023 at 3:38 | comment | added | darij grinberg | For Question 1: In the definition of "$a_i$ is a barrier for $a_j$", do you suppose $i < j$? | |
| Oct 24, 2023 at 2:35 | comment | added | Jan Nienhaus | @darijgrinberg one of the sets has a 'not' in it and the other doesn't | |
| Oct 24, 2023 at 1:04 | comment | added | darij grinberg | ... Now what you argue is essentially that any P-move and any S-move decrease the Lehmer code of $w$ with respect to this lexicographic order, as long as $w$ consists of integers. Thus, the moves cannot continue for more than $n!$ steps. | |
| Oct 24, 2023 at 1:03 | comment | added | darij grinberg | Nice proof for Question 2!! Translated into a language I like a bit more, this is really an induction on the Lehmer code. For any $n$-tuple $w = \left(w_1, w_2, \ldots, w_n\right)$, we define the Lehmer code of $w$ to be the $n$-tuple $\left(\ell_1\left(w\right), \ell_2\left(w\right), \ldots, \ell_n\left(w\right)\right)$, where $\ell_i\left(w\right)$ denotes the number of entries of $w$ to the right of $w_i$ but smaller than $w_i$. This Lehmer code is an element of the $n!$-element set $\prod_{i=1}^n \left\{0,1,\ldots,n-i\right\}$, which is totally ordered by lexicographic order. ... | |
| Oct 24, 2023 at 0:21 | history | answered | Jan Nienhaus | CC BY-SA 4.0 |