[Question]
  [
## Background
The so-called "Urinal Protocol", describing the order in which individual urinals are picked in a men's bathroom, has been discussed in multiple places. One version is given in [this xkcd blog post](http://blog.xkcd.com/2009/09/02/urinal-protocol-vulnerability/). This question concerns a slight variation:
> 
> **Arrangement**: n urinals in a line.  
> 
> **Protocol**: each new person selects one of the urinals most distant from those already in use.
> 
> 
> 
Note that this places *no* restrictions on which urinal is picked by the first person.
**Update**: The sequence of the number of different ways in which n people can select n urinals starts with 1, 2, 4, 8, 20... Note that this *not* the same as [OEIS](http://oeis.org/) [A095236](http://oeis.org/A095236), which describes slightly stricter restrictions than in this question.
## Task
Given an integer n between 0 and 10, output (in any order) all the possible orderings in which n people can occupy n urinals. Each ordering should be printed as the final arrangement: a sequence of digits representing the people (1-9 for the first 9 people, 0 for the tenth), starting from the leftmost urinal, with *optional* non-alphanumeric separators between (but not before or after) the digits. For example, the following outputs are both valid:
```
>> 3
132
213
312
231
>> 4
1|3|4|2
1|4|3|2
3|1|4|2
4|1|3|2
2|3|1|4
2|4|1|3
2|3|4|1
2|4|3|1
```
You may write a program or function, taking input via STDIN (or closest alternative), command-line argument or function argument. Results should be printed to STDOUT (or closest alternative).
## Scoring
Shortest code wins. Standard terms & conditions apply.
  
[Answer]
# Pyth, ~~53~~ 51
```
MhSm^-dG2HjbmjdmehxkbQusmm+dkfqgTdeSmgbdQUQGUtQm]dQ
```
This is an iterative approach. Given a possible partially filled in ordered sets of locations, we find all the optimal further locations, then generate the corresponding location list, and repeat.
Results are generated in the form `[<first person's location>, <second person's location> ...]`, then this is transformed into the desired format. `MhSm^-dG2H` defines a helper function which finds the minimum distances from a given stall to an occupied stall (squared). Amusingly, the separator is free.
[Example run.](https://pyth.herokuapp.com/?code=MhSm%5E-dG2HjbmjdmehxkbQusmm%2BdkfqgTdeSmgbdQUQGUtQm%5DdQ&input=4)
Explanation:
First, the helper function `g`, which finds the minimum squared distance between G and any value in H.
```
MhSm^-dG2H
M             def g(G,H): return
 hS           min(                         )
   m     H        map(lambda d:        , H) 
    ^-dG2                      (d-G)**2
```
Next, we find the maximum over urinal locations of the minimum squared distance between that urinal and any occupied urinal:
(`Q` is the input.)
```
eSmgbdQ
eS          max(                                   )
  m   Q         map(lambda b:      , range(len(Q)))
   gbd                       g(b,d)
```
`d` in this case is the list of occupied urinals, while `b` iterates over urinal locations.
Next, we find all urinal locations whose minimum squared distance from the nearest occupied urinal is equal to the maximum value found above.
```
fqgTdeSmgbdQUQ
f           UQ    filter(lambda T:                             , range(len(Q)))
 qgTd                             g(T,d) ==
     eSmgbdQ                                <value found above>
```
Next, we will generate the urinal location lists created by adding the urinal locations found above to `d`. We will do this for each previous list of urinal locations, thus extending the lists from length `N` to `N+1`. `G` is the list of legal lists of occupied urinal locations of a given length.
```
smm+dkfqgTdeSmgbdQUQG
sm                  G    sum(map(lambda d:                               ,G)
  m+dk                                   map(lambda k:d+[k],            )
      fqgTdeSmgbdQUQ                                        <above list>
```
Next, we will apply the above expression repeatedly, to generate the complete list of lists of occupied urinal locations. `u`, the reduce function, does exactly this, as many times as there are elements in its second argument.
```
usmm+dkfqgTdeSmgbdQUQGUtQm]dQ
usmm+dkfqgTdeSmgbdQUQG           reduce(lambda G,H: <the above expression)
                      UtQ        repeat Q-1 times
                         m]dQ    starting with [[0], [1], ... [Q-1]]. 
```
Convert from the above representation, which goes `[<1st location>, <2nd location>, ... ]`, to the desired output form, `[<person in slot 1>, <person in slot 2>, ... ]`. Then, the output form is joined into the output string and printed. Printing is implicit.
```
jbmjdmehxkbQ
jbm             '\n'.join(map(λ k:                                    ,<above>)
   jdm     Q                      ' '.join(map(λ b:                ,Q)
        xkb                                        b.index(k)
      eh                                                     +1 %10
     
```
[Answer]
# Pyth, 75 71 67
```
DcGHFk_UQJf!s:GeS,0-TkhS,h+TklGUQIJRsmcX>G0dhHhHJ)R]Gjbmjdmebkcm0Q0
```
Recursive combinatorial solution.
It's a fairly direct translation from this Python solution:
```
N = int(input())
def gen(l, p):
    for d in reversed(range(N)):
        s = []
        for i in range(N):
            if not sum(l[max(0,i-d):min(i+d+1, len(l))]):
                s.append(i)
        if s:
            r = []
            for possib in s:
                j = l[:]
                j[possib] = p+1
                r += gen(j, p+1)
            return r
    
    return [l]
print("\n".join(" ".join(str(x % 10) for x in sol) for sol in gen([0] * N, 0)))
```
[Answer]
# C, ~~929~~ 878 bytes
This one's a monster, guys. Sorry.
```
typedef unsigned long U;typedef unsigned char C;U f(int*u,n){C c[8],a[8];*(U*)(&c)=-1;int i,b=0,l=-9,s=-2,f=0,d;for (i=0; i<n; i++) {if (!u[i]&&s<0)s=i,l=0;if(!u[i])l++;if(u[i]&&s>=0){if(!s)l=2*l-1;d=(l-1)/2;if(b<d)*(U*)(a)=0,*(U*)(c)=-1,*c=s,*a=l,f=1,b=d;else if(b==d)c[f]=s,a[f++]=l;s=-1;}}if(s>=0&&l){l=2*l-1;d=(l-1)/2;if(b<d)*(U*)(c)=-1,*c=s,*a=l,f=1,b=d;else if(b==d)c[f]=s,a[f++]=l;}d=f;for(i=0;i<d;i++){if((c[i]+1)&&c[i]){if(c[i]+a[i]==n)c[i]=n-1;else{if(!(a[i]%2))c[f++]=b+c[i]+1;c[i]+=b;}}}return*(U*)c;}void P(int*u,n,i,c,m){for(i=0;i<n;i++){if(!u[i])c++;if(u[i]>m)m=u[i];}if(!c){for(i=0;i<n;i++)printf("%d",u[i]==10?0:u[i]);printf("\n");}else{int s[8][n];for(i=0;i<8;i++)for(c=0;c<n;c++)s[i][c]=u[c];U t=f(u,n);C*H=&t;for(i=0;i<8;i++)if((C)(H[i]+1))s[i][H[i]]=m+1,P(s[i],n,0,0,0);}}void L(n){int u[n],i,j;for(i=0;i<n;i++){for(j=0;j<n;j++)u[j]=j==i?1:0;P(u,n,0,0,0);}}
```
Defines 3 functions, `f(int*,int)`,`P(int*,int,int,int,int)`, and `L(int)`. Call `L(n)`, and it outputs to STDOUT.
Output for `n=5`:
```
14352
15342
31452
31542
41352
51342
41532
51432
24153
25143
34152
35142
23415
23514
24513
25413
24315
25314
24351
25341
```
**Update:** I removed separators and fixed up the code. The old code not only failed for n=7+, but failed to output anything at all for n=10 (oops!). I've more thoroughly tested this bunch. It now supports input of up to n=13 (though the `"%d"` should be changed to `"%x"`so it prints in hexadecimal). The size of input depends on `sizeof(long)` and it is assumed to be `8` in practice.
Here's some explanation of how it works, and why such an odd restriction exists:
These were used a lot, so we define them to save a couple bytes:
`typedef unsigned long U; typedef unsigned char C;`
Here is `f`:
```
U f(int*u,n){
    C c[8],a[8];
    *(U*)(&c)=-1;
    int i,b=0,l=-9,s=-2,f=0,d;
    for (i=0; i<n; i++) {
        if (!u[i]&&s<0)
            s=i,l=0;
        if(!u[i])
            l++;
        if(u[i]&&s>=0){
            if(!s)
                l=2*l-1;
            d=(l-1)/2;
            if(b<d)
                *(U*)(a)=0,
                *(U*)(c)=-1,
                *c=s,
                *a=l,
                f=1,
                b=d;
            else if(b==d)
                c[f]=s,a[f++]=l;
            s=-1;
        }
    }
    if(s>=0&&l){
        l=2*l-1;
        d=(l-1)/2;
        if(b<d)
            *(U*)(c)=-1,
            *c=s,
            *a=l,
            f=1,
            b=d;
        else if(b==d)
            c[f]=s,a[f++]=l;
    }
    d=f;
    for(i=0;i<d;i++){
        if((c[i]+1)&&c[i]){
            if(c[i]+a[i]==n)
                c[i]=n-1;
            else{
                if(!(a[i]%2))
                    c[f++]=b+c[i]+1;
                c[i]+=b;
            }
        }
    }
    return*(U*)c;
}
```
`f` takes an array of integers of size `n`, and `n` itself. The only clever bit here is that it returns an `unsigned long`, which is converted into a `char[8]` by the calling function. Each character in the array is thus set either to `0xFF` or to an index pointing to a valid urinal for the next person. For `n<10`, we never need more than 5 bytes to hold every valid urinal the next person can use.
Here is `P`:
```
void P(int*u,n,i,c,m){
    for(i=0;i<n;i++){
        if(!u[i])c++;
        if(u[i]>m)m=u[i];
    }
    if(!c){
        for(i=0;i<n;i++)
            printf("%d",u[i]==10?0:u[i]);
        printf("\n");
    }
    else{
        int s[8][n];
        for(i=0;i<8;i++)
            for(c=0;c<n;c++)
                s[i][c]=u[c];
        U t=f(u,n);
        C*H=&t;
        for(i=0;i<8;i++)
            if((C)(H[i]+1))
                s[i][H[i]]=m+1,P(s[i],n,0,0,0);
    }
}
```
`P` takes an array `u` of size `n` wherein exactly one element is set to `1`, and the rest are `0`. It then finds and prints every permutation possible recursively.
Here is `L`:
```
void L(n){
    int u[n],i,j;
    for(i=0;i<n;i++){
        for(j=0;j<n;j++)
            u[j]=j==i?1:0;
        P(u,n,0,0,0);
    }
}
```
`L` simply calls `P` `n` times with different starting positions each time.
For the interested, this (less golfed) `f` will generate the sequence in [A095236](http://oeis.org/A095236 "OEIS A095236").
```
U f(int*u,n) {
    C c[8];
    *(U*)(&c) = -1;
    int i,b=0,l=-10,s=-2,f=0,d;
    for (i=0; i<n; i++) {
        if (!u[i]&&s<0) {
            s=i,l=0;
        }
        if(!u[i]){
            l++;
        }
        if (u[i]&&s>=0) {
            if (!s) {
                l=2*l-1;
            }
            if (b<l) {
                *(U*)(&c)=-1;
                c[0]=s;
                f=1;
                b=l;
            }
            else if (b==l)
                c[f++]=s;
            s=-1;
        }
    }
    if (s>=0&&l) {
        l=2*l-1;
        if (b<l) {
            *(U*)(&c)=-1;
            c[0]=s;
            f=1;
            b=l;
        }
        else if (b==l)
            c[f++]=s;
    }
    d=f;
    for (i=0; i<d; i++) {
        if ((c[i]+1)&&c[i]) {
            if (c[i]+b==n) {
                c[i]=n-1;
            }
            else{
                if (!(b%2)) {
                    c[f++]=(b-1)/2+c[i]+1;
                }
                c[i]+=(b-1)/2;
            }
        }
    }
    return *(U*)c;
}
```
[Answer]
# Python 2, 208
```
n=input()
r=range(n)
l=[0]*n
def f(a,d=-1):
 if a>n:print''.join(l);return
 for i in r:
  t=min([n]+[abs(i-j)for j in r if l[j]])
  if t==d:p+=[i]
  if t>d:p=[i];d=t
 for i in p:l[i]=`a%10`;f(a+1);l[i]=0
f(1)
```
Recursive approach. 
[Answer]
# JavaScript (ES6) 153 ~~160 169~~
**Edit** Using Math.min to find (of course) the max distance: streamlined code and 16 bytes saved.
Recursive search, can work with n > 10, just remove % 10 (and be prepared to wait while the console unrolls all its output).
I use a single array to store the slot in use (positive numbers) or the current distance from the nearest slot (negative numbers so `<` and `>` are swapped in code).
```
F=n=>{(R=(m,d,t,x=Math.min(...d=m?
  d.map((v,i)=>(c=i<t?i-t:t-i)?v<c?c:v:m%10)
  :Array(n).fill(-n)))=>
x<0?d.map((v,i)=>v>x||R(-~m,d,i)):console.log(d+[]))()}
```
**Ungolfed**
```
F=n=>{
  var R=(m, // current 'man', undefined at first step
   d, // slot array
   t // current position to fill
  ) =>
  {
    if (m) // if not at first step
    {
      d[t] = m % 10; // mark slot in use, (10 stored as 0 )
      d = d.map((v,i) => { // update distances in d[] 
        var c = i<t ? i-t : t-i; // distance from the current position (negated)
        return v < c ? c : v; // change if less than current distance
      });
    }
    else
    {
      d = Array(n).fill(-n) // fill distance array with max at first step
      // negative means slot free, value is the distance from nearest used slot
      // >= 0 means slot in use by man number 1..n 
    }
    var x = Math.min(...d);
    if ( x < 0 ) // if there is still any free slot
    {
      d.forEach((v,i) => { // check distance for each slot 
        if (v <= x) // if slot is at max distance, call recursive search
          R(-~m, [...d], i) // ~- is like '+1', but works on undefined too
      });
    }
    else
    {
      console.log(d+[]); // no free slot, output current solution
    }
  }
  
  R() // first step call
}
```
**Test** In Firefox/FireBug console
```
F(5)
```
> 
> 1,4,3,5,2  
> 
> 1,5,3,4,2  
> 
> 
> 
> 
[Answer]
# Mathematica, ~~123~~ 104
```
f[n_,s_:{}]:=If[Length@s<n,f[n,s~Join~{#}]&/@MaximalBy[Range@n,Min@Abs[#-s]&];,Print@@Ordering@s~Mod~10]
```
[Answer]
## MATLAB, 164
```
function o=t(n),o=mod(r(zeros(1,n)),10);function o=r(s),o=[];d=bwdist(s);m=max(d);J=find(d==m);if~d,o=s;J=[];end,n=max(s)+1;for j=J,o=[o;r(s+n*(1:numel(s)==j))];end
```
[Answer]
# Perl, 174
Not very short, but fun. I'm not counting `use feature 'say';` towards the byte total.
```
$n=pop;@u="_"x$n." "x$n."_"x$n;for$p(1..$n){@u=map{my@r;for$x(reverse 0..$n){
s/(?<=\D{$x}) (?=\D{$x})/push@r,$_;substr $r[-1],pos,1,$p%10/eg and last;
}@r}@u}y/_//d&&say for@u
```
De-golfed:
```
$n = pop; # Get number of urinals from commandline
@state = ( "_" x $n . " " x $n . "_" x $n );
for my $person (1 .. $n) {
  # Replace each state with its list of possible next states.
  @state = map {
    my @results;
    for my $distance (reverse 0 .. $n) {
      # If there are any spots with at least $distance empty on
      # both sides, then add an entry to @results with the current
      # $person number in that spot, for each spot. Note that this
      # is only used for its side-effect on @results; the modified $_
      # is never used.
      s{
        (?<=\D{$distance})
        [ ]
        (?=\D{$distance})
      }{
        push @results, $_;
        substr $results[-1], pos(), 1, $person % 10;
      }xeg
      # If we found any spots, move on, otherwise try
      # with $distance one lower.
      and last;
    }
    # New state is the array we built up.
    @results;
  } @state;
}
# After adding all the people, remove underscores and print the results
for my $result (@state) {
  $result =~ tr/_//d;
  say $result;
}
```
[Answer]
# C, 248 bytes
This code uses a recursive algoritm to generate the desired outcome.
```
void q(char*f,int l,int d,char*o){char*c=f;while(f<c+l){if(!*f){sprintf(o+4*d,"%03i,",f-c);*f=1;q(c,l,d+1,o);*f=0;}f++;}if(d+1==l){o[4*d+3]=0;printf("%s\n",o);}}int main(int i,char**v){int k=atoi(v[1]);char*c=calloc(k,5),*o=c+k;q(c,k,0,o);free(c);}
```
---
*Expanded:*
```
void printperms(char* memory,int length,int offset,char*output)
{
    char*temp_char=memory;
    while(memory<temp_char+length)
    {
        if(!*memory)
        {
            sprintf(output+4*offset,"%03i,",memory-temp_char);
            *memory=1;
            printperms(temp_char,length,offset+1,output);
            *memory=0;
        }
        memory++;
    }
    if(offset+1==length)
    {
        output[4*offset+3]=0;
        printf("%s\n",output);
    }
}
int main(int i,char**v)
{
    int argument=atoi(v[1]);
    char*t=calloc(argument,5),*output=t+argument;
    printperms(t,argument,0,output);
    free(t);
}
```
[Answer]
# Bash, 744 674 bytes
This is still way too long :). I use a string to represent the row of urinals and a flooding algorithm to find the most distant urinals in each phase of recursion. The ungolfed code is almost self-explanatory. The number of urinals is read from keyboard.
Code (golfed):
```
read l;u=----------;u=-${u::$l}-
s(){ u=${u:0:$1}$2${u:$((1+$1))};}
m(){ local u=$1;a=();while :;do [ 0 -ne `expr index - ${u:1:$l}` ]||break;t=$u;y=$u;for i in `seq $l`;do [ ${y:$i:1} = - ]||{ s $(($i-1)) X;s $(($i+1)) X;};done;done;while :;do k=`expr index $t -`;[ 0 != $k ]||break;t=${t:0:$(($k-1))}X${t:$k};if [ 1 -ne $k ]&&[ $(($l+2)) -ne $k ];then a+=($(($k-1)));fi;done;}
e(){ local u f b v;u=$1;f=$2;if [ 1 -eq $l ];then echo 1;return;fi;if [ 1 = $f ];then for i in `seq $l`;do v=$u;s $i 1;e $u 2;u=$v;done;else m $u;b=(${a[@]});if [ 0 -eq ${#b} ];then echo ${u:1:$l};else for i in ${b[@]};do v=$u;s $i $(($f%10));e $u $(($f+1));u=$v;a=(${b[@]});done;fi;fi;}
e $u 1
```
Use:
```
$ source ./script.sh
input number of urinals from keyboard
```
And ungolfed it goes:
```
read l  # read number of urinals
u=----------
u=-${u:0:$l}- #row is two positions longer (it will be helpful when finding the most distant urinals)
# So, for the end, with 6 men, u might look like this:
# -143652-
# subu no fellow_no => set urinal [number] occupied by [fellow_no]
# this is just convenience for resetting a character inside a string
subu(){ u=${u:0:$1}$2${u:$((1+$1))};}
# this will be iterated in longest to find the remotest places:
# -1---3---2- => spreadstep => X1X-X3X-X2X => spreadstep => X1XXX3XXX2X
# see longest() to get more explanation.
spreadstep()
{
    y=$u
    for i in `seq 1 $l`
    do
    if [ "${y:$i:1}" != "-" ]
    then
        subu $(($i-1)) X
        subu $(($i+1)) X
    fi
    done
}
# Find the urinals with the longest distance. It uses spreadstep() - see above.
# -1---3---2- => spreadstep => X1X-X3X-X2X => spreadstep => X1XXX3XXX2X
# ---> last state with free ones was X1X-X3X-X2X ,
#                                     123456789
# free urinals are no. 3 and no. 7 => save them to arr
longest()
{
    local u=$1
    arr=()
    while true
    do
        if [ 0 -eq `expr index - ${u:1:$l}` ]
        then
            break
        fi
        save=$u
        spreadstep
    done
    while true
    do
        index=`expr index $save -`
        if [ 0 == $index ]
        then
            break
        fi
        save=${save:0:$(($index-1))}X${save:$index}
        if [ 1 -ne $index ] && [ $(($l+2)) -ne $index ]
        then
            arr+=($(($index-1)))
        fi
    done
}
# main function, recursively called
# the first fellow may take any of the urinals.
# the next fellows - only those with the longest distance.
placements_with_start()
{
    local u=$1
    local fellow=$2
    if [ 1 -eq $l ] # special case - there is no 2nd fellow, so below code would work incorrect 
    then
        echo "1"
        return
    fi
    if [ 1 == $fellow ]       # may take any of urinals
    then
        for i in `seq 1 $l`
        do
            local _u=$u
            subu $i 1                     # take the urinal
            placements_with_start $u 2    # let the 2nd fellow choose :)
            u=$_u
        done
    else
        longest $u   # find the ones he can take
        local _arr=(${arr[@]})
        if [ 0 -eq ${#_arr} ]
        then
            echo ${u:1:$l}    # no more free urinals - everyone took one - print the result
        else
            for i in ${_arr[@]}
            do
                local _u=$u
                subu $i $(($fellow % 10))                # take urinal
                placements_with_start $u $(($fellow+1))  # find locations for for next fellow
                u=$_u
                arr=(${_arr[@]})
            done
        fi
    fi
}
placements_with_start $u 1
```
]