Permutacje z nierozróżnialnymi przedmiotami


12

Biorąc pod uwagę listę liczb całkowitych, wypisz liczbę permutacji liczb całkowitych, z nierozróżnialnymi permutacjami liczonymi raz. Jeśli istnieją nliczby całkowite i każda grupa liczb nie do odróżnienia ma długość n_i, to znaczyn! / (n_1! * n_2! * ...)

Zasady

  • Dane wejściowe będą rodzajem listy jako argumenty funkcji lub programu z 1 do 12 liczbami całkowitymi nieujemnymi.

  • Wyjście będzie drukować lub zwracać liczbę permutacji, jak opisano powyżej.

  • Brak standardowych luk i wbudowanych funkcji (generowanie permutacji, kombinacji itp.). Czynniki są dozwolone.

Przypadki testowe

Wejścia:

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

Wyjścia:

60
1
83160

kiedy mówisz, że nie ma wbudowanych, czy obejmuje to to, co zrobiłem, gdy użyłem wbudowanego do wygenerowania wszystkich permutacji?
Maltysen 24.04.16

1
Wygląda to w dużej mierze tak samo jak Oblicz współczynnik wielomianowy . Czy liczenie identycznych wpisów dla danych wejściowych sprawia, że ​​wystarczająco różni się, aby nie być duplikatem?
xnor 24.04.16

@ xnor dobrze tutaj musisz liczyć duplikaty, więc nie jest to takie proste. Drugi to w zasadzie proste podłączanie wartości.
qwr 24.04.16

@Maltysen niestety tak, będę musiał zaktualizować pytanie
qwr 24.04.16

1
@LuisMendo Tak, ale nie powinno to robić różnicy, o ile mogę sobie wyobrazić
qwr 24.04.16

Odpowiedzi:


6

Python, 48 bajtów

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

Implementacja rekurencyjna.

W formule, n! / (n_1! * n_2! * ...)jeśli usuniemy pierwszy element (powiedzmy, że 1), liczba permutacji dla pozostałych n-1elementów wynosi

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

Tak więc otrzymujemy odpowiedź przez pomnożenie przez n/n1ułamek odwrotny elementów, które są równe pierwszemu, przez wynik rekurencyjny dla reszty listy. Pusta lista podaje podstawowy przypadek 1.


Dlaczego nie umieścisz /l.count(l[0])na końcu? Więc nie potrzebujesz tego obrzydliwego zmiennoprzecinkowego.
feersum

4

MATL , 14 13 12 bajtów

fpGu"@G=s:p/

Wypróbuj online!

Wyjaśnienie

Podejście jest bardzo podobne do tego w odpowiedzi @ Adnan .

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

3

05AB1E , 15 14 13 bajtów

Kod:

D©g!rÙv®yQO!/

Wyjaśnienie:

               # 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

Wykorzystuje kodowanie CP-1252 .

Wypróbuj online! .


2

JavaScript (ES6), 64 61 bajtów

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

Korzysta z podanego wzoru, z wyjątkiem obliczania każdego silnia przyrostowo (więc na przykład r=r*++iefektywnie się oblicza n!).

Edycja: Początkowo akceptowałem dowolne liczby skończone, ale zapisałem 3 bajty, gdy @ user81655 wskazał, że muszę obsługiwać tylko liczby całkowite dodatnie (chociaż akceptuję liczby całkowite nieujemne).


r*=++i/(x-y?(y=x,c=1):++c),y=r=-1)|-r?
user81655,

@ user81655 Ach, nie przeczytałem pytania wystarczająco dokładnie i przeoczyłem, że mogę polegać na wartościach całkowitych dodatnich. Nie podoba mi się to, *=ponieważ wprowadza błędy zaokrąglania.
Neil,

2

Pyth, 11 bajtów

/.!lQ*F/V._

Zestaw testowy

Używa standardowej formuły, n! / (count1! * count2! * ...)z tym wyjątkiem, że silnia zliczeń jest obliczana przez zliczenie, ile razy każdy element występuje w prefiksie prowadzącym do tego, a następnie pomnożenie wszystkich takich liczb razem.

Wyjaśnienie:

/.!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.


1

Rubinowy, 75 74 bajtów

Trochę żałuję, że Mathmoduł Ruby nie miał funkcji silni, więc nie musiałem budować własnej.

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

1

CJam, 17 bajtów

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

Sprawdź to tutaj.

Wyjaśnienie

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.

1

Galaretka, 8 bajtów

W;ĠL€!:/

Wypróbuj 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

1

J, 13 bajtów

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

Stosowanie

   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

Wyjaśnienie

#(%*/)&:!#/.~  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
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.