Mathematische Kombination

11

Schreiben Sie ein Programm, das eine Eingabe wie die folgenden vornimmt:

n,k

was dann berechnet:

Kombination von n und k.  (C (n, k))

und druckt dann das Ergebnis.


Ein numerisches Beispiel:

Eingang:

5,2

Interne Berechnung:

(5!) / (3! X2!)

Gedruckte Ausgabe:

10

Ich würde gerne eine Antwort sehen, die meine Python-Lösung mit 65 Zeichen übertrifft, aber alle Sprachen sind natürlich willkommen.

Hier ist meine Lösung:

n,k=input();f=lambda x:+(x<2)or x*f(x-1);print f(n)/(f(k)*f(n-k))

Bearbeiten:

Ich gebe zu, dass diese Frage aus dem mathematischen Kombinationsrätsel der Codegolf-Website stammt . Ich weiß, dass meine Antwort so aussieht, als ob nicht viel Fortschritt gemacht werden kann, aber die Anführer dieses Puzzles haben es in fast halb so vielen Charakteren gelöst.

Die derzeit niedrigsten Zeichenzahlen nach Sprache sind:

Perl: 35

Ruby: 36

Python: 39

PHP: 62

Backus
quelle
Funktion oder volles Programm? Ihre Beschreibung besagt eine Funktion, die das richtige Ergebnis zurückgibt, aber Ihr Beispiel ist ein vollständiges Programm, das es druckt.
Ventero
@Ventero Du hast recht, ich meinte Programm. Das tut mir leid.
Backus
3
Im Allgemeinen sind grundlegende mathematische Konzepte keine großartigen Golffragen, da sie in J, APL, Maple, Mathematica und vielen anderen integriert sind. Seien Sie auch etwas spezifischer in Bezug auf das Eingabe- und Ausgabeformat und liefern Sie Beispielergebnisse - ich kann nicht Sagen Sie, wenn Sie 5 meinen, wählen Sie 2 oder 2 wählen Sie 5 hier.
Jesse Millikan
@Jesse Ich habe diese Herausforderung von einer anderen Website erhalten, die nur die wichtigsten Skriptsprachen zulässt. Ich werde mich in Zukunft an diese Richtlinie erinnern. Ich habe meine Frage bearbeitet, um die Herausforderungsanforderungen klarer zu gestalten. Lassen Sie mich wissen, ob sie klar genug sind oder nicht.
Backus
Ich bin neu, also sitzen wir im selben Boot. Fassen Sie die Ergebnisse jedoch nicht zusammen. Sie werden einfach veraltet sein. Stimmen Sie einfach ab und akzeptieren Sie (falls zutreffend) Antworten. (Außerdem werden Sie die Leute unglücklich machen, wenn Sie die Antworten von J und GolfScript ohne Grund ignorieren.)
Jesse Millikan

Antworten:

11

APL, 3 Bytes

⎕!⎕

Oder für diejenigen, deren Browser das oben Gesagte in einem ASCII-Rendering nicht rendert:

{Quad}!{Quad}
jpjacobs
quelle
3
Um vollständig mit der n,kEingabe übereinzustimmen, müssten Sie dies tun !/⌽⎕.
marinus
10

R (11 Zeichen)

choose(n,r)
skeevey
quelle
10

C 96

Mit E / A (was ungefähr 34 Zeichen dauert). Einige Zeilenumbrüche wurden hinzugefügt, um die Lesbarkeit zu verbessern.

main(a,b,c,d){scanf("%d,%d",&a,&b);
d=a-b;for(c=1;a>b;){c*=a--;}for(;d;)
{c/=d--;}printf("%d",c);}

Nun, wenn Sie mich entschuldigen, ich habe eine ASCII-Rakete zum Wählen.

    d;main(a
   ,         b
  ,           c
 )  int        a
 ;   {scanf    (
 (   "%d %d"   )
 ,   &a,  &b   )
 ;   d    =a   -
 b   +     b   -
 b   *     1   ;
 a             -
 a  ;for    (  c
 =  1;a>   b   ;
 )  {c=   c    *
 (  (a-- )     )
 ;  }for(      b
 =  b + 1      ;
 d  ;    )     {
 c  =     c    /
 (  d--    )   ;
  }           {
  }           {
   }         (
  printf("%d",c)
 )      ;       }
/*     *  *   * *\
 * * X   * 8 * * |
|     *      *    \
*/    //       *  */
Walpen
quelle
7

GolfScript, 17 Zeichen

Diese Lösung behandelt Fälle wie k = 0 oder k = 1 korrekt.

~>.,,]{1\{)*}/}//

Der faktorielle Teil basiert auf einer vorherigen Antwort .

Nabb
quelle
6

GolfScript 21

~~)>.,,]{{)}%{*}*}%~/

Nicht besonders kurz, GolfScript hat keine echte Fakultätsfunktion, aber dies muss die bösartigste Datenmanipulation sein, die ich jemals durchgeführt habe. Dies erfordert eine Stapelverfolgung:

"5,2" Daten auf dem Stapel von der Eingabe.
~Beachten Sie, dass der Befehl Eval ein Operator ist, der eine Zahl in ein Array verwandelt.
[0 1 2 3 4] 2
~Binär nicht.
[0 1 2 3 4] -3
)Inkrement.
[0 1 2 3 4] -2
>Nehmen Sie das Ende des Arrays, -2 als Parameter, um die letzten 2 Elemente zu erhalten.
[3 4]
.Element duplizieren.
[3 4] [3 4]
,Array-Länge.
[3 4] 2
,Drehen Sie die Nummer in ein Array.
[3 4] [0 1]
]Array erstellen.
[[3 4] [0 1]]
{{)}%{*}*}Codeblock.
[[3 4] [0 1]] {{)}% {*} *}
%Führen Sie den Block für jedes Element des Arrays einmal aus. Der folgende Teil zeigt nur die erste Schleife.
[3 4]
{)}%Inkrementiere jedes Array-Element.
[4 5]
{*}Block mit einem Multiplikationsbefehl.
[4 5] {*}
*"Falten" Sie das Array mit dem Befehl block, dh machen Sie in diesem Fall das Produkt aller Elemente.
20
Nachdem die große Schleife beendet ist, wird ein Array mit den Ergebnissen zurückgegeben.
[20 2]
~Dekonstruiere das Array.
20 2
/Abteilung.
10

aaaaaaaaaaaa
quelle
6

Ruby 1.9, 52 46 (42) Zeichen

eval"A,B="+gets;i=0;p eval"(A-B+i+=1)/i*"*B+?1

Wenn stderr ignoriert wird:

eval"A,B=I="+gets;p eval"I/(A-I-=1)*"*B+?1

Ruby 1.8, 43 Zeichen, keine zusätzliche Ausgabe an stderr:

eval"a,b=i="+gets;p eval"i/(a-i-=1)*"*b+"1"

Bearbeitungen:

  • (52 -> 48) Es wurde ein kürzerer Weg gefunden, um die Eingabe zu analysieren
  • (48 -> 46) Weniger Looping, mehr Auswertung.
Ventero
quelle
4

Python (56)

f=lambda n,k:k<1and 1or f(n-1,k-1)*n/k;print f(*input())

Ungolfed Code und eine Erklärung einer Abkürzung zur Berechnung des Binomialkoeffizienten. (Hinweis: Es gibt einige Erkenntnisse, die ich einfach nicht herausgefunden habe, um zur 39-Zeichen-Version zu gelangen. Ich glaube nicht, dass dieser Ansatz Sie dorthin bringt.)

# Since choose(n,k) =
#
#     n!/((n-k)!k!)
#
#          [n(n-1)...(n-k+1)][(n-k)...(1)]
#        = -------------------------------
#            [(n-k)...(1)][k(k-1)...(1)]
#
# We can cancel the terms:
#
#     [(n-k)...(1)]
#
# as they appear both on top and bottom, leaving:
#
#    n (n-1)     (n-k+1)
#    - ----- ... -------
#    k (k-1)       (1)
#
# which we might write as:
#
#      choose(n,k) = 1,                      if k = 0
#                  = (n/k)*choose(n-1, k-1), otherwise
#
def choose(n,k):
    if k < 1:
        return 1
    else:
        return choose(n-1, k-1) * n/k

# input() evaluates the string it reads from stdin, so "5,2" becomes
# (5,2) with no further action required on our part.
#
# In the golfed version, we make use of the `*` unpacking operator, 
# to unpack the tuple returned by input() directly into the arguments
# of f(), without the need for intermediate variables n, k at all.
#
n, k = input()

# This line is left as an exercise to the reader.
print choose(n, k)

quelle
Könnten Sie ein Beispiel für Ihr Drehbuch geben?
Backus
Können wir *Eingaben des Formulars analysieren 4545 78?
Quixotic
Leider nein, aber das ist nicht *das Problem. 4545 78ist kein gültiger Python-Ausdruck, daher input()wird a ausgelöst SyntaxError. Dieser Trick hängt ganz von dem Problem ab, nach dem gefragt wird x,y. Wenn Sie eine Funktion hatten, die x yein Tupel las und zurückgab, konnten Sie es problemlos verwenden *.
4

RPL (4)

(mit eingebauter Funktion)

COMB
oliver
quelle
3

Windows PowerShell, 57

$a,$b=iex $input
$p=1
for($a-=$b;$a-ge1){$p*=1+$b/$a--}$p
Joey
quelle
3

J, 33 36

(":!~/".;._1}:toJ',',1!:1(3))1!:2(4)

35 Zeichen werden eingegeben, analysiert und ausgegeben. Das andere Zeichen !ist n wähle k.

Ich habe momentan kein Windows zum Testen, aber ich glaube, es sollte dort funktionieren.

Jesse Millikan
quelle
3

Q, 32 Zeichen

{f:{1*/1.+(!)x};f[x]%f[y]*f x-y}
tmartin
quelle
2

Perl 6 (55)

my ($a,$b)=lines;$_=1;for 1..$a-$b {$_+=$_*$b/$^a};.say
Ming-Tang
quelle
2

RPL (22)

(ohne integrierte COMB-Funktion)

→ n k 'n!/(k!*(n-k)!)'
oliver
quelle
2

Q ( 50 45)

 f:{(prd 1.+til x)%((prd 1.+til y)*prd 1.+til x-y)}

Sie können einige der oben genannten Zeichen entfernen, indem Sie redundante Klammern entfernen und 1 * / anstelle von prd verwenden.

f:{(1*/1.+til x)%(1*/1.+til y)*1*/1.+til x-y}
sinedcm
quelle
2

Mathematica 12

Einfache, eingebaute Funktion.

n~Binomial~k
DavidC
quelle
2

Perl 6 , 25 16 Bytes

-9 Bytes dank nwellnhof

+*o&combinations

Probieren Sie es online aus!

Anonyme Funktion, die zwei Zahlen akzeptiert und ein int zurückgibt. Dies verwendet die integrierte combinationsund konvertiert die zurückgegebene Liste in eine int.

Scherzen
quelle
16 Bytes
Nwellnhof
@wellnhof Ah, ich wusste nicht, dass ich combinationseine Nummer anstelle einer Liste nehmen könnte
Jo King
1

PHP (71 79 )

<?$a=fgetcsv(STDIN);$x=1;while($a[1]-$i)$x=$x*($a[0]-++$i+1)/$i;echo$x;

<?php $a=fgetcsv(STDIN);$x=1;while(++$i<=$a[1])$x=$x*($a[0]-$i+1)/$i;echo $x?>

mellamokb
quelle
1

Python (54)

f=lambda n,k:k<1or f(n-1,k-1)*n/k;print 1*f(*input())

Im Wesentlichen das gleiche wie das Python oben, aber ich rasiere vier Bytes durch Löschen des

and 1

aus der Funktionsdefinition. Dies führt jedoch dazu, dass die Funktion True anstelle von 1 zurückgibt, wenn k = 0 ist. Dies kann jedoch durch Multiplizieren mit 1 vor dem Drucken behoben werden, da 1 * True = 1 ist, wodurch zwei Bytes addiert werden.

Tor
quelle
1

J, 11 Zeichen

!~/".1!:1[1

Übernimmt Eingaben über die Tastatur.

    !~/".1!:1[1
5,2
10
Gareth
quelle
0

Haskell (80)

f(_,0)=1
f(n,k)=n/k*f(n-1,k-1)
main=getLine>>=putStr.show.f.read.(++")").('(':)

Wenn jedoch die Eingabe im Format x yanstelle des Formats zulässig ist x,y, sind es 74 Zeichen:

f[_,0]=1
f[n,k]=n/k*f[n-1,k-1]
main=interact$show.f.map read.take 2.words
Marinus
quelle
0

Scala 54

val n,k=readInt
((k+1)to n product)/(1 to(n-k)product)
Benutzer unbekannt
quelle
0

Python (52)

 f=lambda n,k:k<1or f(n-1,k-1)*n/k;print+f(*input())

Verbessert von den beiden anderen, indem print+das Ergebnis von fvon booleanin intfür den Fall konvertiert wird k==0.

Ich habe immer noch keine Ahnung, wie ich es auf 39 verkleinern soll. Ich frage mich, ob sie überhaupt Lambda verwenden.

Andrea Ambu
quelle
0

(Das OP hat die Eingabe- und Ausgabemethode / das Eingabeformat nur lose angegeben, sodass Folgendes akzeptabel erscheint.)

Salbei Notizbuch ( 39 41 40)

In der aktuellen Zelle

f=lambda n,k:k<1or f(n-1,k-1)*n/k;+f(*_)

Hier wird die Eingabe im Formular n,kin der vorhergehenden Zelle eingegeben und ausgewertet. Dies simuliert die "Befehlszeileneingabe", indem sie zugewiesen wird _(ähnlich wie bei Befehlszeilenargumenten).

Salbei Notizbuch ( 42 44 43)

Alternativ können Sie "In-Source-Eingabe" verwenden (wobei nur die x=Zeichen und Zeilenumbrüche zur Partitur hinzugefügt werden), z.

x=5,2
f=lambda n,k:k<1or f(n-1,k-1)*n/k;+f(*x)

Beide Ansätze sind offensichtlich Ableger früherer Antworten anderer.

res
quelle
0

Javascript, 27 Bytes

Zuerst meine eigenen 35-Byte-Lösungen:

f=(n,k)=>n-k&&k?f(--n,k)+f(n,k-1):1

Oder alternativ,

f=(n,k,i=k)=>i?f(n-1,k-1,i-1)*n/k:1

Der erste arbeitet rekursiv mit der einfachen (n,k) = (n-1,k) + (n-1,k-1)Regel. Der zweite benutzt das (n,k) = (n-1,k-1) * n/k.

BEARBEITEN

Ich habe gerade die Lösung von Arnould in einem Duplikat davon bemerkt:

f=(n,k)=>k?n*f(n-1,k-1)/k:1

Das sind satte 8 Bytes weniger (27 Bytes)

vrugtehagel
quelle
0

TI-BASIC, 16 Zeichen (8 Bytes)

Ans(1) nCr Ans(2

Die Eingabe ist eine Liste mit einer Länge von 2 Zoll Ans.
Die Ausgabe ist das Ergebnis der hier definierten Formel .

Wenn die obige Lösung nicht ausreicht, funktioniert auch die folgende Lösung mit 35 Zeichen (24 Byte) :

Ans(2)!⁻¹(Ans(1)-Ans(2))!⁻¹Ans(1)!

Hinweis: TI-BASIC ist eine Token-Sprache. Die Anzahl der Zeichen entspricht nicht der Anzahl der Bytes.

Tau
quelle