Permutationen mit nicht unterscheidbaren Gegenständen

12

Geben Sie bei einer Liste von Ganzzahlen die Anzahl der Permutationen der Ganzzahlen aus, wobei nicht unterscheidbare Permutationen einmal gezählt werden. Wenn es nganze Zahlen gibt und jede Gruppe nicht unterscheidbarer Zahlen eine Länge hat n_i, ist diesn! / (n_1! * n_2! * ...)

Regeln

  • Die Eingabe erfolgt in Form einer Liste als Argument für eine Funktion oder ein Programm mit 1 bis 12 nicht negativen Ganzzahlen.

  • Die Ausgabe erfolgt wie oben beschrieben durch Drucken oder Zurücksenden der Anzahl der Permutationen.

  • Keine Standardlücken oder eingebauten Funktionen (Erzeugen von Permutationen, Kombinationen usw.). Factorials sind erlaubt.

Testfälle

Eingänge:

1, 3000, 2, 2, 8
1, 1, 1
2, 4, 3, 2, 3, 4, 4, 4, 4, 4, 1, 1

Ausgänge:

60
1
83160
qwr
quelle
Wenn Sie keine Builtins sagen, beinhaltet dies auch das, was ich getan habe, als ich ein Builtin zum Generieren aller Permutationen verwendet habe?
Maltysen
1
Dies entspricht weitgehend der Berechnung des Multinomialkoeffizienten . Unterscheidet sich die Zählung identischer Einträge für die Eingabe ausreichend, um kein Betrug zu sein?
XNOR
@xnoder hier muss man eigentlich die Duplikate zählen, also ist es wohl nicht so einfach. Das andere ist so ziemlich das direkte Einstecken von Werten.
Qwr
@Maltysen leider ja, ich muss die Frage aktualisieren
qwr
1
@ LuisMendo Ja, es ist, obwohl es keinen Unterschied machen sollte, soweit ich es mir vorstellen kann
qwr

Antworten:

6

Python, 48 Bytes

f=lambda l:l==[]or len(l)*f(l[1:])/l.count(l[0])

Eine rekursive Implementierung.

n! / (n_1! * n_2! * ...)Wenn wir in der Formel das erste Element entfernen (sagen wir, es ist 1), beträgt die Anzahl der Permutationen für die verbleibenden n-1Elemente

(n-1)! / ((n_1-1)! * n_2! * ...) ==
n! / n / (n_1! / n_1! * n_2! * ...) == 
n/n_1 * (n! / (n_1! * n_2! * ...)`)

Wir erhalten die Antwort, indem wir n/n1den Kehrwert der Elemente, die dem ersten entsprechen, mit dem rekursiven Ergebnis für den Rest der Liste multiplizieren . Die leere Liste gibt den Basisfall von 1 an.

xnor
quelle
Warum setzt du nicht /l.count(l[0])am Ende? Dann brauchen Sie diesen icky Fließkomma nicht.
Feersum
4

MATL , 14, 13 12 Bytes

fpGu"@G=s:p/

Probieren Sie es online!

Erläuterung

Der Ansatz ist dem in @ Adnans Antwort sehr ähnlich .

f       % Take input implicitly. Push array of indices of nonzero entries.
        % This gives [1 2 ... n] where n is input length.
p       % Product (compute factorial)
Gu      % Push input. Array of its unique elements
"       % For each of those unique values
  @     %   Push unique value of current iteration
  G=s   %   Number of times (s) it's present (=) in the input (G)
  :p    %   Range, product (compute factorial)
  /     %   Divide
        % End for each implicitly. Display implicitly
Luis Mendo
quelle
3

05AB1E , 15 14 13 Bytes

Code:

D©g!rÙv®yQO!/

Erläuterung:

               # implicit input
D©             # duplicate and save a copy to register
  g!           # factorial of input length (total nr of permutations without duplicates)
    rÙv        # for each unique number in input
       ®yQO!   # factorial of number of occurances in input
            /  # divide total nr of permutations by this
               # implicit output

Verwendet die CP-1252- Codierung.

Probieren Sie es online! .

Adnan
quelle
2

JavaScript (ES6), 64 61 Bytes

a=>a.sort().map((x,i)=>r=r*++i/(x-y?(y=x,c=1):++c),y=r=-1)|-r

Verwendet die angegebene Formel, außer dass jede Fakultät inkrementell berechnet wird (z. B. die r=r*++ieffektiven Berechnungen n!).

Bearbeiten: Ursprünglich habe ich alle endlichen Zahlen akzeptiert, aber ich habe 3 Bytes gespart, als @ user81655 darauf hinwies, dass ich nur positive Ganzzahlen unterstützen musste (obwohl ich eigentlich nicht negative Ganzzahlen akzeptiere).

Neil
quelle
r*=++i/(x-y?(y=x,c=1):++c),y=r=-1)|-r?
user81655
@ user81655 Ah, ich hatte die Frage nicht gründlich genug gelesen und übersehen, dass ich mich darauf verlassen konnte, dass die Werte positive ganze Zahlen sind. Ich mag das *=aber nicht, da das Rundungsfehler einführt.
Neil
2

Pyth, 11 Bytes

/.!lQ*F/V._

Testsuite

Verwendet die Standardformel n! / (count1! * count2! * ...), außer dass die Fakultäten der Zählungen ermittelt werden, indem gezählt wird, wie oft jedes Element im vorangegangenen Präfix vorkommt, und dann alle diese Zahlen miteinander multipliziert werden.

Erläuterung:

/.!lQ*F/V._
/.!lQ*F/V._QQ    Implicit variable introduction.
                 Q = eval(input())
         ._Q     Form all prefixes of the input.
       /V   Q    Count how many times each element occurs in the prefix
                 ending with that element.
     *F          Fold on multiplication - take the product.
 .!lQ            Take the factorial of the input length
/                Divide.
isaacg
quelle
1

Pyth - 14 12 Bytes

/F.!M+lQ/LQ{

Test Suite .

Maltysen
quelle
1

Ruby, 75 74 Bytes

Irgendwie wünschte Mathich mir, dass Rubys Modul eine Fakultätsfunktion hätte, damit ich keine eigene bauen müsste.

->l{f=->x{x<2?1:x*f[x-1]};l.uniq.map{|e|f[l.count e]}.inject f[l.size],:/}
Wert Tinte
quelle
1

CJam, 17 Bytes

q~_,\$e`0f=+:m!:/

Teste es hier.

Erläuterung

q~   e# Read input and evaluate.
_,   e# Duplicate and get length.
\$   e# Swap with other copy and sort it.
e`   e# Run-length encode. Since the list is sorted, this tallies the numbers.
0f=  e# Select the tally of each number.
+    e# Prepend the length of the input.
:m!  e# Compute the factorial of each number in the list.
:/   e# Fold division over it, which divides each factorial of a tally into
     e# the factorial of the length.
Martin Ender
quelle
1

Gelee, 8 Bytes

W;ĠL€!:/

Probieren Sie es online!

W;ĠL€!:/ example input:             [1, 3000, 2, 2, 8]
W        wrap:                      [[1, 3000, 2, 2, 8]]
  Ġ      group index by appearance: [[1], [3, 4], [5], [2]]
 ;       concatenate:               [[1, 3000, 2, 2, 8], [1], [3, 4], [5], [2]]
   L€    map by length:             [5, 1, 2, 1, 1]
     !   [map by] factorial:        [120, 1, 2, 1, 1]
      :/ reduce by division:        120÷1÷2÷1÷1 = 60
Undichte Nonne
quelle
1

J, 13 Bytes

#(%*/)&:!#/.~

Verwendung

   f =: #(%*/)&:!#/.~
   f 1 3000 2 2 8
60
   f 1 1 1
1
   f 2 4 3 2 3 4 4 4 4 4 1 1
83160

Erläuterung

#(%*/)&:!#/.~  Input: A
         #/.~  Partition A by equal values and get the size of each, these are the tallies
#              Get the size of A
      &:!      Take the factorial of both the size and the tallies
   */          Reduce using multiplication the factorial of the tallies
  %            Divide the factorial of the size by that product and return
Meilen
quelle