Find a left transversal of a finite group which is a right transversal (without combinatorical theorems or assuming that $H$ is normal) The Problem:
We have a finite group G, an arbitrary subgroup $H\leq G$ of index, say $r\in \mathbb{N}^+$, and we want to find $\{g_1,...,g_r\}$ which is a left transversal and a right transversal.
My Question: I am looking for a proof which does not use Hall's Marriage theorem (we did not cover this in my classes, so I would also have to prove that theorem itself in my proof if I used it, even then I probably would not get full credit). I really only have very basic set theory (including AC/Zorn's) and group theory that I am allowed to use here (up to for instance actions, class equation, and Sylow theory).
What I have tried: Obviously we can take some left transversal $\{g_i\mid 1\leq i\leq r\}$, then I know that $\{g_i^{-1}\mid 1\leq i\leq r\}$ is a right transversal, which does not seem to be particularly helpful. I have also tried throwing a combination of: existence of a Sylow p-subgroup P (where p is the smallest prime dividing $\rvert G\rvert$) and induction at this (something like: if $H$ is a proper subgroup of $HP$ (if $P$ is normal), then we can do some sort of induction on the index here I think, not really sure yet, but this need not happen, we could have $H$ strictly contain $P$ for instance, or $H = P$). The idea I was trying to get at was something like a composition series to apply induction to $[G:H]$ on, but even a finite group need not have a composition series which includes $H$, so I am kind of stuck atm.
Notes: Yes I am aware there are other MSE posts about this, but afaik they all either use some combinatorical theorems (namely Marriage theorem) that I can't use, or they assume H is normal (it is fairly trivial in that case anyway).
 A: I'd give an algorithmic construction as follows:
Start with a left transversal $\{l_1,\ldots,l_k\}$ and a right transversal $\{r_1,\ldots,r_k\}$ ($[G:H]=k$ to avoid confusion with $r$ and $r_i$).
For $i=1,\ldots,k$:

If $l_iH\cap Hr_j\ne\emptyset$ for some $j\ge i$ then choose $g_i\in l_iH\cap Hr_j$ and swap $r_j$ with $r_i$ so $g_iH=l_iH$ and $Hr_i=Hg_i$.


Otherwise $l_iH\subseteq \cup_{j<i}Hg_j$. In this case $|\cup_{j<i}Hg_j|<|\cup_{j\le i}l_jH|$, so there is some $s<i$ with $g_sH=l_sH\not\subseteq \cup_{j<i}Hg_j$. Set $i_0=i$, $g_{i_0}=l_i$ (this choice of $g_{i_0}$ is really just a placeholder so that the rest of the loop is well defined).


While $l_{i_0}H\subseteq\cup_{j<i_0}Hg_j$ fix $s<i_0$ with $g_sH=l_sH\not\subseteq \cup_{j<i_0}Hg_j$. Move $l_s$ to $l_{i_0}$, shifting $l_{s+1},\ldots,l_{i_0}$ down by one to make space (also rotate $g_s,\ldots,g_{i_0}$ and $r_s,\ldots,r_{i_0}$ to match). Subtract $1$ from $i_0$.


While $i_0\le i$ we have by construction $l_{i_0}H\cap Hr_j\ne\emptyset$ for some $j\ge i_0$. Fix $g_{i_0}\in l_{i_0}H\cap Hr_j$ and swap $r_{i_0}$ with $r_j$. Set $i_0=j$.

