tło

Tak zwany „protokół pisuaru”, opisujący kolejność wybierania poszczególnych pisuarów w męskiej łazience, był omawiany w wielu miejscach. Jedna wersja jest podana w tym poście na blogu xkcd . To pytanie dotyczy niewielkiej zmienności:

Rozmieszczenie : n pisuarów w linii.
Protokół : każda nowa osoba wybiera jeden z pisuarów najbardziej odległych od już używanych.

Pamiętaj, że nie nakłada to żadnych ograniczeń na to, który pisuar wybiera pierwsza osoba.

Aktualizacja : Sekwencja liczby różnych sposobów wyboru n pisuarów zaczyna się od 1, 2, 4, 8, 20 ... Zauważ, że to nie to samo co OEIS A095236 , które opisuje nieco bardziej rygorystyczne ograniczenia niż w tym pytanie.

Zadanie

Biorąc pod uwagę liczbę całkowitą n od 0 do 10, wyprowadzaj (w dowolnej kolejności) wszystkie możliwe porządki, w których n ludzi może zajmować n pisuarów. Każde zamówienie powinno być wydrukowane jako ostateczne ustawienie: ciąg cyfr reprezentujących ludzi (1-9 dla pierwszych 9 osób, 0 dla dziesiątej), zaczynając od pisuaru najbardziej na lewo, z opcjonalnymi niealfanumerycznymi separatorami między (ale nie wcześniej lub po) cyfrach. Na przykład następujące dane wyjściowe są poprawne:

>> 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

Możesz napisać program lub funkcję, przyjmując dane wejściowe przez STDIN (lub najbliższą alternatywę), argument wiersza poleceń lub argument funkcji. Wyniki należy wydrukować do STDOUT (lub najbliższej alternatywy).

Punktacja

Najkrótszy kod wygrywa. Obowiązują standardowe warunki.

Pyth, 53 51

MhSm^-dG2HjbmjdmehxkbQusmm+dkfqgTdeSmgbdQUQGUtQm]dQ

To jest podejście iteracyjne. Biorąc pod uwagę możliwe częściowo wypełnione uporządkowane zestawy lokalizacji, znajdujemy wszystkie optymalne dalsze lokalizacje, a następnie generujemy odpowiednią listę lokalizacji i powtarzamy.

Wyniki są generowane w formie [<first person's location>, <second person's location> ...], a następnie przekształcane w pożądany format. MhSm^-dG2Hdefiniuje funkcję pomocnika, która określa minimalne odległości od danego przeciągnięcia do zajętego przeciągnięcia (kwadrat). Zabawne jest, że separator jest bezpłatny.

Przykładowy przebieg.

Wyjaśnienie:

Po pierwsze, funkcja pomocnika g, która znajduje minimalną kwadratową odległość między G i dowolną wartością w H.

MhSm^-dG2H
M             def g(G,H): return
 hS           min(                         )
   m     H        map(lambda d:        , H) 
    ^-dG2                      (d-G)**2

Następnie znajdujemy maksymalne położenie nad pisuarem minimalnej kwadratowej odległości między tym pisuarem a dowolnym zajętym pisuarem:

( Qjest wejściem.)

eSmgbdQ
eS          max(                                   )
  m   Q         map(lambda b:      , range(len(Q)))
   gbd                       g(b,d)

dw tym przypadku jest to lista zajętych pisuarów, podczas gdy biteracja dotyczy lokalizacji pisuarów.

Następnie znajdujemy wszystkie lokalizacje pisuaru, których minimalna kwadratowa odległość od najbliższego zajmowanego pisuaru jest równa maksymalnej wartości podanej powyżej.

fqgTdeSmgbdQUQ
f           UQ    filter(lambda T:                             , range(len(Q)))
 qgTd                             g(T,d) ==
     eSmgbdQ                                <value found above>

Następnie wygenerujemy listy lokalizacji pisuarów utworzone przez dodanie do powyższych pozycji pisuaru d. Zrobimy to dla każdej poprzedniej listy lokalizacji pisuaru, rozszerzając w ten sposób listy z długości Ndo N+1. Gto lista legalnych list zajętych lokalizacji pisuarów o danej długości.

smm+dkfqgTdeSmgbdQUQG
sm                  G    sum(map(lambda d:                               ,G)
  m+dk                                   map(lambda k:d+[k],            )
      fqgTdeSmgbdQUQ                                        <above list>

Następnie zastosujemy powyższe wyrażenie wielokrotnie, aby wygenerować pełną listę list zajętych lokalizacji pisuaru. u, funkcja redukująca, robi to dokładnie tyle razy, ile jest elementów w drugim argumencie.

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]]. 

Konwersja z powyższego przedstawienia, który przechodzi [<1st location>, <2nd location>, ... ]do pożądanej postaci wyjściowej [<person in slot 1>, <person in slot 2>, ... ]. Następnie formularz wyjściowy jest łączony z ciągiem wyjściowym i drukowany. Drukowanie jest niejawne.

jbmjdmehxkbQ
jbm             '\n'.join(map(λ k:                                    ,<above>)
   jdm     Q                      ' '.join(map(λ b:                ,Q)
        xkb                                        b.index(k)
      eh                                                     +1 %10

Pyth, 75 71 67

DcGHFk_UQJf!s:GeS,0-TkhS,h+TklGUQIJRsmcX>G0dhHhHJ)R]Gjbmjdmebkcm0Q0

Rekurencyjne rozwiązanie kombinatoryczne.

Jest to dość bezpośrednie tłumaczenie z tego rozwiązania Python:

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)))

C, 929 878 bajtów

To jest potwór, chłopaki. Przepraszam.

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);}}

Definiuje 3 funkcje, f(int*,int), P(int*,int,int,int,int), i L(int). Wywołaj L(n)i wyśle ​​do STDOUT.

Dane wyjściowe dla n=5:

14352
15342
31452
31542
41352
51342
41532
51432
24153
25143
34152
35142
23415
23514
24513
25413
24315
25314
24351
25341

Aktualizacja: usunąłem separatory i poprawiłem kod. Stary kod nie tylko nie powiódł się dla n = 7 +, ale w ogóle nie wypisał niczego dla n = 10 (ups!). Dokładniej przetestowałem tę grupę. Obsługuje teraz wejście do n = 13 (chociaż "%d"należy zmienić na, "%x"aby drukowało w systemie szesnastkowym). Wielkość wkładu zależy od sizeof(long)i zakłada się, że jest to 8w praktyce.

Oto wyjaśnienie, jak to działa i dlaczego istnieje takie dziwne ograniczenie:

Były one często używane, więc definiujemy je, aby zaoszczędzić kilka bajtów:

typedef unsigned long U; typedef unsigned char C;

Oto 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;
}

fprzyjmuje tablicę liczb całkowitych wielkości ni nsiebie. Jedynym sprytnym bitem jest to, że zwraca an unsigned long, który jest konwertowany na char[8]funkcję wywołującą. Każdy znak w tablicy jest zatem ustawiony 0xFFna indeks lub na indeks wskazujący na prawidłowy pisuar dla następnej osoby. Ponieważ n<10nigdy nie potrzebujemy więcej niż 5 bajtów do przechowywania każdego ważnego pisuaru, którego może użyć następna osoba.

Oto 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);
    }
}

Pprzyjmuje tablicę urozmiarów, w nktórej ustawiony jest dokładnie jeden element 1, a pozostałe są 0. Następnie wyszukuje i drukuje każdą możliwą kombinację rekurencyjnie.

Oto 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);
    }
}

Lpo prostu wywołuje P nczasy z różnymi pozycjami początkowymi za każdym razem.

Dla zainteresowanych ta (mniej golfa) fwygeneruje sekwencję w 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;
}

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)

Podejście rekurencyjne.

JavaScript (ES6) 153 160 169

Edytuj za pomocą Math.min, aby znaleźć (oczywiście) maksymalną odległość: usprawniony kod i 16 zapisanych bajtów.

Wyszukiwanie rekurencyjne, może pracować z n> 10, wystarczy usunąć% 10 (i być przygotowanym na czekanie, aż konsola rozwija wszystkie dane wyjściowe).

Używam pojedynczej tablicy do przechowywania używanego gniazda (liczby dodatnie) lub bieżącej odległości od najbliższego gniazda (liczby ujemne tak <i >zamieniane są w kodzie).

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+[]))()}

Bez golfa

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
}

Przetestuj w konsoli Firefox / FireBug

F(5)

1,4,3,5,2
1,5,3,4,2
3,1,4,5,2
3,1,5,4,2
4,1,3,5,2
5,1,3 , 4,2
4,1,5,3,2
5,1,4,3,2
2,4,1,5,3
2,5,1,4,3
3,4,1,5,2
3 , 5,1,4,2
2,3,4,1,5
2,3,5,1,4
2,4,3,1,5
2,5,3,1,4
2,4,5, 1,3
2,5,4,1,3
2,4,3,5,1
2,5,3,4,1

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]

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

Perl, 174

Niezbyt krótki, ale zabawny. Nie liczę use feature 'say';do całkowitej bajtu.

$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

Gra w golfa:

$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;
}

C, 248 bajtów

Ten kod używa algorytmu rekurencyjnego do generowania pożądanego wyniku.

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);}

Rozszerzony:

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);
}

Bash, 744 674 bajty

To wciąż za długo :). Używam ciągu znaków do reprezentowania rzędu pisuarów i algorytmu zalewania, aby znaleźć najbardziej odległe pisuary w każdej fazie rekurencji. Nieskluczony kod jest prawie oczywisty. Liczba pisuarów jest odczytywana z klawiatury.

Kod (golfowy):

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

Posługiwać się:

$ source ./script.sh
input number of urinals from keyboard

I bez golfa idzie:

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