Das Taubenschlagprinzip besagt das

Wenn N Artikel in M Felder mit N > M gestellt werden , muss mindestens ein Feld mehr als einen Artikel enthalten.

Für viele hat dieses Prinzip einen besonderen Stellenwert im Vergleich zu anderen mathematischen Aussagen. Wie EW Dijkstra schrieb ,

Es ist von Mystik umgeben. Proofs, die es verwenden, werden oft als etwas Besonderes, als etwas besonders Geniales angesehen.

Die Herausforderung

Der Zweck dieser Herausforderung ist die Veranschaulichung des Pigeonhole-Prinzips anhand von ASCII-Darstellungen. Speziell:

1. Nehmen Sie als Eingabe N(Anzahl der Elemente) und M(Anzahl der Felder), mit Nnicht-negativen und Mpositiven. Nkann kleiner sein als M(auch wenn der Grundsatz in diesem Fall nicht gilt).
2. Wählen Sie zufällig eine der möglichen Zuordnungen von Elementen zu Feldern aus. Jede Aufgabe sollte mit einer Wahrscheinlichkeit ungleich Null ausgewählt werden.

3. Erstellen Sie eine ASCII-Grafikdarstellung der Zuweisung wie folgt:

   • Es gibt MLinien, die jeweils einem Kästchen entsprechen.
   • Jede Zeile beginnt mit einem Nicht-Leerzeichen wie z |.
   • Nach diesem Zeichen folgt ein anderes Nicht-Leerzeichen, das z. B. #so oft wiederholt wird, wie sich Elemente in diesem Feld befinden.

Betrachten Sie zum Beispiel N = 8, M = 5. Wenn die ausgewählte Zuordnung von Elementen zu Feldern " 4," 1, " 0ist 3, 0ist die Darstellung"

|####
|#
|
|###
|

Ein anderer Lauf (der zu einer anderen Zuweisung führt) desselben Programms könnte ergeben

|#
|##
|#
|#
|###

Es gibt eine gewisse Flexibilität in Bezug auf die Darstellung; siehe unten.

Spezifische Regeln

Der Code sollte theoretisch für alle Werte von Nund ausgeführt werden M. In der Praxis kann es durch Einschränkungen der Speichergröße oder des Datentyps eingeschränkt sein.

Da das Beobachten der Ausgabe nicht ausreicht, um zu bestimmen, ob alle Zuweisungen eine Wahrscheinlichkeit ungleich Null haben , sollte jede Einreichung erläutern, wie der Code dies erreicht, wenn nicht offensichtlich.

Folgende Darstellungsvarianten sind zulässig:

• Es kann ein beliebiges Paar verschiedener Zeichen ohne Leerzeichen ausgewählt werden. Sie müssen über die Programmausführungen hinweg konsistent sein.
• 90-Grad-Drehungen der Darstellung sind zulässig. Auch hier muss die Auswahl konsistent sein.
• Nachgestellte oder führende Leerzeichen sind zulässig.

Als ein Beispiel mit einem anderen Darstellungsformat, für N = 15, M = 6könnten die Ergebnisse von zwei Ausführungen des Programms sein

VVVVVV
@@@@@@
@@ @@@
 @  @@
    @

oder

VVVVV
@@@ @
@@@ @
@ @ @
@ @ @
@

Ebenso N = 5, M = 7könnte geben, eine andere Variation der Darstellung verwendet wird ,

  *
* * * *
UUUUUUU

oder

 *** **
UUUUUUU

oder

   *
*  *
*  * 
UUUUUUU

Beachten Sie, wie das Prinzip in diesem Fall nicht anwendbar ist, weil N< M.

Allgemeine Regeln

Programme oder Funktionen sind in jeder Programmiersprache zulässig . Standardlücken sind verboten.

Die Eingabe kann auf jede vernünftige Weise erfolgen . und mit jedem Format, z. B. einem Array aus zwei Zahlen oder zwei verschiedenen Zeichenfolgen.

Ausgabemittel und Format sind ebenfalls flexibel. Die Ausgabe kann beispielsweise eine Liste von Zeichenfolgen oder eine Zeichenfolge mit Zeilenumbrüchen sein. wird als Funktionsausgabeargument zurückgegeben oder in STDOUT angezeigt. Im letzteren Fall ist es nicht erforderlich, sich um Zeilenumbrüche zu kümmern, die durch eine begrenzte Anzeigebreite verursacht werden.

Kürzester Code in Bytes gewinnt.

Gelee , 9 8 Bytes

=þṗX¥S⁵*

Dies ist eine dyadische Verknüpfung, die M als linkes und N als rechtes Argument verwendet. Die Ausgabe ist ein Array von Ganzzahlen, wobei 0 für Tauben und 1 für Löcher steht.

Probieren Sie es online!

Wie es funktioniert

=þṗX¥S⁵*  Main link. Left argument: m. Right argument: n

    ¥     Combine the two links to the left into a dyadic chain and call it
          with arguments m and n.
  ṗ        Compute the n-th Cartesian power of [1, ..., m], i.e., generate all
           vectors of length n that consist of elements of [1, ..., m].
   X       Pseudo-randomly choose one of those vectors with a uniform distribution.
=þ        Equal table; for each k in [1, ..., m] and each vector to the right,
          compare the elements of the vector with k. Group the results by the
          vectors, yielding a 2D Boolean matrix.
     R    Range; map 1 to [1], 0 to [].
      S   Take the sum of all columns.
       ⁵* Raise 10 to the resulting powers.

Mathematica, 68 Bytes

Print/@(10^RandomSample@RandomChoice[IntegerPartitions[+##,{#}]-1])&

Eine unbenannte Funktion, die zwei ganzzahlige Argumente akzeptiert, die Anzahl der Felder, gefolgt von der Anzahl der Elemente.

Es berechnet zunächst alle möglichen Partitionen von N+Min genau Mpositive Teile und subtrahiert anschließend 1von jeder Partition. Dies gibt uns alle möglichen Partitionen Nin Mnicht negative Teile (die IntegerPartitionssonst nicht erzeugt würden). Wähle dann eine zufällige Partition und mische sie. Dies garantiert, dass alle möglichen geordneten Partitionen mit Nullen zulässig sind. Schließlich wird jedes Fach der mit einer Ausgangsleitung Partition konvertieren , indem 10 auf die entsprechende Potenzierung (so dass jede Zeile wird 1000...mit kNullen). Eine Beispielausgabe könnte folgendermaßen aussehen:

100
10000
1
10
10

Python 2, 77 86 Bytes

from random import*
n,m=input()
exec'c=randint(0,n);n-=c;print 10**c;'*~-m
print 10**n

Erzeugt eine Zahl in [0, n], druckt so viele Elemente und subtrahiert sie von n. Das macht es m-mal.

Dies macht es sehr unwahrscheinlich, dass irgendetwas es bis zur letzten Box schafft, aber die Frage stellte nur, dass jede Ausgabe möglich und nicht gleich wahrscheinlich ist .

Batch, 164 Bytes

@for /l %%i in (1,1,%1)do @set h%%i=1
@for /l %%j in (1,1,%2)do @call set/ab=%%random%%%%%%%1+1&call set/ah%%b%%*=10
@for /l %%i in (1,1,%1)do @call echo %%h%%i%%

Ich denke, 7 aufeinanderfolgende %Zeichen könnten eine neue persönliche Bestleistung sein! Hinweis: Dies führt zu einer ungeraden Ausgabe, sollte der gleichen Box jemals mehr als 9 Elemente zugewiesen werden. Wenn das ein Problem ist, dann für 180 Bytes:

@for /l %%i in (1,1,%1)do @set h%%i=1
@for /l %%j in (1,1,%2)do @call set/ab=%%random%%%%%%%1+1&call call set h%%b%%=%%%%h%%b%%%%%%0
@for /l %%i in (1,1,%1)do @call echo %%h%%i%%

Ja, das sind insgesamt 28 %Sekunden in der zweiten Zeile.

C 102 Bytes

n,m;main(x){srand(time(0));for(scanf("%d %d",&n,&m);m--;n-=x)printf("|%0*s\n",x=m?rand()%(n+1):n,"");}

Übernimmt Eingaben über stdin, zB:

echo "5 4" | ./pigeonhole

Erzeugt nicht jede Ausgabe mit gleicher Wahrscheinlichkeit, kann aber alle möglichen Kombinationen erzeugen.

Nervenzusammenbruch:

n,m;
main(x){
    srand(time(0));             // Seed random number generator
    for(scanf("%d %d",&n,&m);   // Parse input values into n and m
        m--;                    // Loop through each bucket (count down)
        n-=x)                   // Subtract number assigned to bucket from total
        printf(                 // Output a formatted string using padding
            "|%0*s\n",          // (turns out %0s will actually zero-pad a string!)
            x=m?rand()%(n+1):n, // Calculate a number of items for this bucket
            "");
}

Beruht auf GCCs Handhabung des undefinierten Verhaltens von %0s- Füllt normalerweise %0eine Ganzzahl oder einen Gleitkommawert mit Null auf, kann jedoch nur aufgefüllt (nie abgeschnitten) werden, sodass kein Leerzeichen gedruckt werden kann. Das Verhalten für Zeichenfolgen ist jedoch nicht definiert, und GCC hat beschlossen, das Auffüllen mit Nullen auf die gleiche Weise vorzunehmen. Daher füllt dieses Auffüllen eine leere Zeichenfolge mit Nullen auf, um in der Lage zu sein, null oder mehr zu schreiben0 .

Python 2, 102 99 97 90 Bytes

m-1wähle mal einen zufälligen Betrag xzwischen 0und n, inklusive und subtrahiere ihn von n. Dann drucken Sie ein 1und '0'*x.

Schließlich drucken 1und der Rest von 0s. Nicht bei allen gleichen Chancen, aber alle Konfigurationen sind möglich.

from random import*
n,m=input()
exec'x=randrange(n+1);n-=x;print 10**x;'*(m-1)
print 10**n

(Wiederverwendeter Code aus der kaputten Python-Antwort.)

Haskell, 114 94 Bytes

import System.Random
n#m=map(10^).take m.until((==n).sum.take m)tail.randomRs(0,m)<$>newStdGen

Ein bisschen wie ein Brute-Force-Ansatz: Erzeugt eine unendliche Liste von Zufallszahlen, nimmt n Zahlen vom Anfang der Liste, summiert sie und prüft, ob sie gleich m sind. Wenn nicht, nimm das erste Element von der Liste und wiederhole es.

Probieren Sie es online!

Hinweis: 73 Bytes ohne den Import

BEARBEITEN: Einige Bytes mit dem 10 ^ Trick gespeichert ( Neue Version online testen! )

REXX, 74 Bytes

arg n m
m=m-1
o.=@
do n
  a=random(m)
  o.a=o.a||#
  end
do a=0 to m
  say o.a
  end

Ausgabe (8 5):

@#
@###
@
@#
@###

Ausgabe (8 5):

@#
@#
@
@####
@##

C 175 138 Bytes

Vielen Dank an @ Dave für das Speichern von 37 Bytes!

i;f(n,m){char**l=calloc(m,8);for(i=0;i<m;)l[i]=calloc(n+1,1),*l[i++]=124;for(i=n+1;--i;)*strchr(l[rand()%m],0)=35;for(;i<m;)puts(l[i++]);}

Probieren Sie es online!

AHK, 66 Bytes

2-=1
Loop,%2%{
Random,r,0,%1%
Send,|{# %r%}`n
1-=r
}
Send,|{# %1%}

Ich folgte demselben Prinzip wie orlp, indem ich Zufallszahlen von 0 bis N verwendete und diese dann von N subtrahierte. Leider konnte ich keine Bytes mit 10 ^ r speichern, da die Sendefunktion so funktioniert. Ach und ach. Hier sind einige Ausgaben für n = 8, m = 5:

|##     |#####    |##       |##     |#      |##   
|##     |#        |#####    |       |###    |#    
|#      |##       |         |###    |###    |     
|###    |         |         |       |#      |     
|       |         |#        |###    |       |#####

CJam, 30 31 21 Bytes

:B1a*:C\{CBmrAt.*}*N*

Eingabe sind zwei Zahlen n mauf dem Stapel. Verwendet 1für das Spaltenzeichen und 0für das wiederholte Zeichen.

Erläuterung:

:B          e# Store m in B (without deleting it from the stack)
1a          e# Push 1 and wrap it in an array: [1]
*           e# Repeat the array m times
:C          e# Store this array in C (without deleting)
\{          e# Do n times:
  CBmrAt    e#   Create an array of 1s with a random element replaced with 10.
  .*        e#   Vectorized multiplication: multiply the respective elements in the arrays.
            e#   Effectively, we multiply a random value in the array by 10 (and add a 0 to the end).
}*          e# End loop.
N*          e# Join with newlines.

Röda , 79 Bytes

f n,m{a=[0]*m
i=0{{n--
a[i%m]++}if randomBoolean
i++}while[n>0]
a|[`|`.."#"*_]}

Probieren Sie es online!

Dadurch wird ein Array von Nullen erstellt und an zufälligen Stellen inkrementiert.

PHP, 100 Bytes

list($z,$m,$n)=$argv;$a=array_fill(0,$n,z);while($m>0){$a[rand(0,$n-1)].=a;$m--;}echo join("\n",$a);

Nervenzusammenbruch :

list($z,$m,$n)=$argv;     // assigns the input vars to $m and $n
$a=array_fill(0,$n,z);    // creates an array $a of $n elements containing 'z'
while($m>0){              // randomly populate array $a
    $a[rand(0,$n-1)].=a;  //
    $m--;                 //
}                         //
echo join("\n",$a);       // output $a contents separated by a new line

Ausgänge für m=7und n=5:

Erste Ausführung:

za
zaa
za
za
zaa

Zweite Ausführung:

za
zaa
zaaa
z
za

Probieren Sie es online!

JavaScript, 105 Bytes

x=>y=>{s=[];for(;x>1;y-=t)s[--x]="|"+"#".repeat(t=Math.random()*(y+1)|0);s[0]="|"+"#".repeat(y);return s}

Probieren Sie es online!

Aufgrund der Methode zum Zuweisen der Zeilen wird dies tendenziell eher nach unten verlegt, obwohl die Wahrscheinlichkeit gering ist, dass die Oberseite etwas davon erhält.

Ruby, 52 Bytes

->(n,m){r=Array.new(m){?|};n.times{r[rand m]+=?#};r}

Erstellt eine anonyme Funktion, die zwei Ganzzahlen als Argumente verwendet und ein Array von Strings zurückgibt:

>> puts ->(n,m){r=Array.new(m){?|};n.times{r[rand m]+=?#};r}.call 7,5
|#
|#
|##
|##
|#

Python 2, 81 Bytes

from random import*
def f(n,m):l=['#']*m;exec('l[randrange(m)]+="o";'*n);return l

Gibt eine Liste von Zeichenfolgen zurück.

Javascript (ES7), 75 Byte

(N,M)=>{for(r='';M;M--,N-=x=~~(Math.random()*(N+1)),r+=10**x+`
`);return r}

Ich dachte, ich wäre schlau genug, um auf die Idee der Potenz 10 zu kommen, nur um zu erkennen, dass die meisten Antworten dies bereits benutzten.

AWK, 78 Bytes

{srand();for(;n++;)c[k]=c[k=int($2*rand())]"#"}END{for(;j<$2;)print"|"c[j++]}

Nimmt 2 Argumente auf, zuerst die Anzahl der Elemente, dann die Anzahl der Felder. Beginnt mit dem Setzen des Zufallszahlengenerators, sodass jeder Lauf anders ist. Dann baut man einfach Strings in einem Array auf.

awk '{srand();for(;n++;)c[k]=c[k=int($2*rand())]"#"}END{for(;j<$2;)print"|"c[j++]}' <<< "12 5"

Example output:
|##
|###
|##
|##
|###

MATLAB, 103 94 Bytes

function a(m,n)
d=@(p)disp(char([1,~(1:p)]+48));for i=1:m-1;p=randi([0,n]);d(p);n=n-p;end;d(n)

Mit der Formatierung

function a(m,n)
for i=1:m-1 
    d=@(p)disp(char([1,~(1:p)]+48));  % inline function for displaying
    p=randi([0,n]);              % picking a random number b/w 0 and n
    d(p);                        % '1' represents the box/pigeonhole, with '0's denoting entries
    n=n-p;
end
d(n);                            % writing the remaining entries/zeros

Beispielausgabe

>> a(4,7)
10
10000
10
10

Es gibt nachgestellte Leerzeichen, da jeder Array-Eintrag mit einem Tabulator dazwischen angezeigt wird. Dies sollte jedoch gemäß den Spezifikationen akzeptabel sein.

Dies scheint mir eine sehr vereinfachte Implementierung zu sein, daher bin ich mir sicher, dass dies verbessert werden könnte.

Danke an @Luis Mendo für die Vorschläge.

Oktave , 62 54 Bytes

@(n,m)strcat(62,(sum(randi(m,1,n)==(1:m)',2)>=1:n)*42)

Anonyme Funktion, die zwei Zahlen annimmt und ein 2D-Array von Zeichen mit ausgibt > für Boxen und *für Objekte . Alle Ergebnisse sind gleich wahrscheinlich.

Probieren Sie es online!

TI-Basic, 63 62 Bytes

Prompt N,M
For(A,1,M
N→B
If M-A
randInt(0,N→B
":→Str0
For(C,1,B
Ans+"X→Str0
End
Disp Ans
N-B→N
End

Jede Aufgabe sollte mit einer Wahrscheinlichkeit ungleich Null ausgewählt werden.

Dieses Kriterium erleichterte das Schreiben des Programms erheblich.

Beispiel I / O:

prgmPIDGEON
N=?5
M=?2
:XXXX
:X

Erläuterung:

Prompt N,M     # 5 bytes, input number of items, number of boxes
For(A,1,M      # 7 bytes, for each box
N→B            # 4 bytes, on last box, make sure the sum is met by adding N items
If M-A         # 5 bytes, if not last box
randInt(0,N→B  # 8 bytes, add random number of items from 0 to N to box A
":→Str0        # 6 bytes, first character
For(C,1,B      # 7 bytes, add B items to the box
Ans+"X→Str0    # 8 bytes
End            # 2 bytes
Disp Ans       # 3 bytes, print this box
N-B→N          # 6 bytes, subtract the items used in this box
End            # 1 byte, move on to next box

MATLAB, 73 64 58 Bytes

Update Nr. 3

Ich brauche die Sortierung anscheinend, da ich sonst negative ganze Zahlen bekomme. Ich habe ersetzen disp(sprintf(...))mit fprintf(...)jetzt, obwohl, so dass die Antwort 58 Bytes bleibt.

@(m,n)fprintf('%i\n',10.^diff([0;sort(randi(n,m-1,1));n]))

Update Nr. 2:

Mir wurde klar, dass ich das Array nicht sortieren musste, und tatsächlich würde das Sortieren den Durchschnitt der Zahlen im Array reduzieren. Also habe ich das sort(...)Teil gelöscht . Beachten Sie, dass die Ausgabe dieselbe bleibt, sodass ich die "Beispielausgabe" nicht aktualisiere.

@(m,n)disp(sprintf('%i\n',10.^diff([0;randi(n,m-1,1);n])))

Endlich die Oktavantwort von Luis! : D

Update Nr. 1:

@(m,n)disp(sprintf('%i\n',10.^diff([0;sort(randi(n,m-1,1));n])))

Anstatt in einen String zu konvertieren, zeige ich nur Zahlen direkt an. Ich könnte auf 58 Bytes reduzieren, indem disp(...)ich das entferne , aber dann bekomme ich das Extraans = mit nur sprintf und weiß nicht, ob das akzeptabel ist.

Anfangscode:

@(m,n)disp(strjust(num2str(10.^diff([0;sort(randi(n,m-1,1));n])),'left'))

Dank einiger Vorschläge von Luis habe ich die Schleife in meiner vorherigen Antwort losgeworden . Jetzt erstelle ich ein vertikales Array von mZufallszahlen, die zusammen n(diff([0;sort(randi(n,m-1,1));n]) ) , verwende sie dann als Exponenten von 10, konvertiere sie in eine Zeichenfolge, bündige sie linksbündig und zeige sie an.

Ich könnte das disp (...) technisch loswerden, um weitere 6 Bytes zu sparen, aber dann wird ein "ans" gedruckt, das möglicherweise gegen die Spezifikationen verstößt. Es kann auch eine Möglichkeit geben, sie in Zeichenfolge und linksbündig zu ändern, um das gewünschte Endformat zu erhalten. Daher bin ich offen für Vorschläge.

Beispielausgabe:

>> a=@(m,n)disp(strjust(num2str(10.^diff([0;sort(randi(n,m-1,1));n])),'left'));
>> a(4,6)
1000
10  
100 
1   

Hinweis : Aufgrund von Vorschlägen habe ich hier meine Funktion in eine anonyme Funktion geändert. In der Beispielausgabe habe ich das zugewiesen,aum zu demonstrieren. Ich hoffe, dies verstößt nicht gegen die Spezifikationen, aber wenn doch, lassen Sie es mich bitte wissen und ich werde es ändern.

Gestapelt , 29 Bytes

('|')\rep\[:randin'#'push@.]*

Probieren Sie es online!

Verhält sich, indem ein Array von MSingletons erstellt wird, die Folgendes enthalten '|', und dann '#'zu zufällig ausgewählten Array- NZeiten hinzugefügt wird .

Python 2 , 80 95 89 88 Bytes

from random import*
n,m=input()
while m:x=randint(0,n);print'1'+'0'*[n,x][m>1];m-=1;n-=x

Probieren Sie es online!

• Hinzugefügt 15 Bytes: Vorherige Bearbeitung war ein bisschen fehlerhaft, einige Piegons wurden ausgelassen.
• Gespeichert 6 Bytes: ersetzt, wenn sonst durch [n, x] [m> 1]
• 1 Byte gespeichert: importieren *

Holzkohle , 19 Bytes

≔ＥＮ⟦⟧θＦＮ⊞‽θ#Ｅθ⁺|⪫ιω

Probieren Sie es online! Link ist eine ausführliche Version des Codes. Erläuterung:

  Ｎ                 Input `M`
 Ｅ                  Map over implicit range
   ⟦⟧               Empty array
≔    θ              Assign resulting nested array to `q`

       Ｎ            Input `N`
      Ｆ             Loop over implicit range
          θ         Nested array `q`
         ‽          Random element
           #        Literal string
        ⊞           Append to array

             θ      Nested array `q`
            Ｅ       Map over array
                 ι  Current element
                  ω Empty string
                ⪫   Join
               |    Literal string
              ⁺     Concatenate
                    Implicitly print on separate lines