Even-Mansour is a theoretical model to prove security results. One would need to sample permutations of $n$ bits, say for $n=128,$ since the resulting space of $N=2^n$ objects would be too large to store or manipulate. This is similar to the fact that no one uses a purely random equidistributed and i.i.d. sequence of bits as a keystream in OTP mode in modern cryptography. It is too slow.
However, the following algorithm gives a random permutation on $\{1,2,\ldots, N\}.$ No claim of optimal efficiency is made here.
CODE FOR RANDOM PERMUTATION OF SMALL LIST
Input: The list $A=[1,2,\ldots, N]$ of $N=2^n$ items.
Task: permute the values in $A$ at random.
Let $S:=\{u: u \in A\}.$ Let $B:=A$
for each $i=1,\ldots,N$ do
$\quad$ Choose a random integer $j \in S$
$\quad$ Change array $B$ via $B[j]:=A[i]$
$\quad$ Remove $j$ from set $S$
end for
This algorithm chooses $N,$ then $N-1$, then $N-2$ etc. objects uniformly and can generate each permutation with equal likelihood, since it makes $N\!$ choices.
Output: The list $A$ is now random.
There are more efficient ways to sample random permutations, see for example Jens Gustedt, "Efficient sampling of random permutations", Journal of Discrete Algorithms, Vol. 6, Issue 1, 2006. Also take a look at Fisher-Yates shuffle and Knuth Shuffle, google is your friend.
The algorithm below doesn't quite get there, thanks to @kelalaka for the correction
Input: The list $A=\{1,2,\ldots, N\}$ of $N=2^n$ items.
Task: permute the values in $A$ at random.
for each $i=0,\ldots,N-1$ do
$\quad$ Choose a random integer $j$ with $i<j<N.$
$\quad$ Swap the entries $A[i]$ and $A[j].$
end for
Output: The list $A$ is now random.
