Muszę obliczyć combinatorials (NCR) w Pythonie, ale nie może znaleźć funkcji do zrobienia, że math
, numpy
czy stat
bibliotek. Coś w rodzaju funkcji typu:
comb = calculate_combinations(n, r)
Potrzebuję liczby możliwych kombinacji, a nie rzeczywistych kombinacji, więc itertools.combinations
mnie to nie interesuje.
Na koniec chcę uniknąć silni, ponieważ liczby, dla których będę obliczać kombinacje, mogą być zbyt duże, a silnie będą potworne.
Wydaje się, że odpowiedź na to pytanie jest NAPRAWDĘ łatwa, jednak tonę w pytaniach o generowanie wszystkich rzeczywistych kombinacji, czego nie chcę.
źródło
scipy.misc.comb
jest przestarzałe na korzyśćscipy.special.comb
od wersji0.10.0
.Dlaczego nie napisać tego samemu? To jeden wiersz lub coś takiego:
Test - drukowanie trójkąta Pascala:
PS. edytowane w celu zastąpienia
int(round(reduce(mul, (float(n-i)/(i+1) for i in range(k)), 1)))
przez,int(reduce(mul, (Fraction(n-i, i+1) for i in range(k)), 1))
więc nie będzie błądzić dla dużych N / Kźródło
from functools import reduce
.Szybkie wyszukiwanie w kodzie google daje (wykorzystuje formułę z odpowiedzi @Mark Byers ):
choose()
jest 10 razy szybszy (testowany na wszystkich parach 0 <= (n, k) <1e3), niżscipy.misc.comb()
gdybyś potrzebował dokładnej odpowiedzi.źródło
choose
funkcja powinna mieć znacznie więcej pozytywnych głosów! Python 3.8 ma math.comb, ale musiałem użyć Pythona 3.6 do wyzwania i żadna implementacja nie dała dokładnych wyników dla bardzo dużych liczb całkowitych. Ten robi i robi to szybko!Jeśli chcesz uzyskać dokładne wyniki i szybkość, wypróbuj gmpy -
gmpy.comb
powinien robić dokładnie to, o co prosisz, i jest dość szybki (oczywiście jakogmpy
autor jestem stronniczy ;-).źródło
gmpy2.comb()
jest 10 razy szybszy niżchoose()
z mojej odpowiedzi dla kodu:for k, n in itertools.combinations(range(1000), 2): f(n,k)
gdzief()
jest albogmpy2.comb()
albochoose()
na Pythonie 3.Jeśli chcesz uzyskać dokładny wynik, użyj
sympy.binomial
. Wydaje się, że jest to najszybsza metoda.źródło
Dosłowne tłumaczenie definicji matematycznej jest wystarczające w wielu przypadkach (pamiętając, że Python automatycznie użyje arytmetyki dużych liczb):
Dla niektórych testowanych przeze mnie danych wejściowych (np. N = 1000 r = 500) było to ponad 10 razy szybsze niż jedna linijka
reduce
sugerowana w innej odpowiedzi (aktualnie najwyżej głosowanej). Z drugiej strony wyprzedza go fragment dostarczony przez @JF Sebastian.źródło
Zaczynając
Python 3.8
, biblioteka standardowa zawiera terazmath.comb
funkcję obliczania współczynnika dwumianu:czyli liczba sposobów wyboru k elementów z n elementów bez powtórzeń
n! / (k! (n - k)!)
:źródło
Oto inna alternatywa. Ten został pierwotnie napisany w C ++, więc można go przenieść do C ++ w celu uzyskania liczby całkowitej o skończonej precyzji (np. __Int64). Zaletą jest to, że (1) obejmuje tylko operacje na liczbach całkowitych, a (2) pozwala uniknąć powiększania wartości całkowitej poprzez wykonywanie kolejnych par mnożenia i dzielenia. Przetestowałem wynik za pomocą trójkąta Pascala Nas Banova, otrzymuje poprawną odpowiedź:
Uzasadnienie: aby zminimalizować liczbę mnożeń i dzieleń, przepisujemy wyrażenie jako
Aby uniknąć przepełnienia mnożenia w jak największym stopniu, będziemy oceniać w następującej kolejności STRICT, od lewej do prawej:
Możemy pokazać, że arytmatyka liczb całkowitych wykonywana w tej kolejności jest dokładna (tj. Nie ma błędu zaokrąglenia).
źródło
Używając programowania dynamicznego, złożoność czasowa wynosi Θ (n * m), a złożoność przestrzeni Θ (m):
źródło
Jeśli twój program ma górną granicę
n
(powiedzmyn <= N
) i musi wielokrotnie obliczać nCr (najlepiej >>N
razy), użycie lru_cache może dać ogromny wzrost wydajności:Konstruowanie pamięci podręcznej (co jest wykonywane niejawnie) zajmuje trochę
O(N^2)
czasu. Wszelkie kolejne połączenia z numeremnCr
powrócą zaO(1)
.źródło
Możesz napisać 2 proste funkcje, które w rzeczywistości okazują się być około 5-8 razy szybsze niż przy użyciu scipy.special.comb . W rzeczywistości nie musisz importować żadnych dodatkowych pakietów, a funkcja jest dość łatwa do odczytania. Sztuczka polega na tym, aby użyć zapamiętywania do przechowywania wcześniej obliczonych wartości i użyć definicji nCr
Jeśli porównamy czasy
źródło
Z Sympy jest to całkiem proste.
źródło
Używając tylko standardowej biblioteki dystrybuowanej z Pythonem :
źródło
Formuła bezpośrednia daje duże liczby całkowite, gdy n jest większe niż 20.
A więc kolejna odpowiedź:
krótkie, dokładne i wydajne, ponieważ pozwala to uniknąć dużych liczb całkowitych w Pythonie poprzez trzymanie się długich liczb.
Jest dokładniejszy i szybszy w porównaniu do scipy.special.comb:
źródło
range(n-r+1, n+1)
zamiastrange(n-r,n+1)
.To jest kod @ killerT2333 wykorzystujący wbudowany dekorator zapamiętywania.
źródło
Oto skuteczny algorytm dla Ciebie
Na przykład nCr (30,7) = fakt (30) / (fakt (7) * fakt (23)) = (30 * 29 * 28 * 27 * 26 * 25 * 24) / (1 * 2 * 3 * 4 * 5 * 6 * 7)
Więc wystarczy uruchomić pętlę od 1 do r, aby uzyskać wynik.
źródło
To prawdopodobnie tak szybko, jak możesz to zrobić w czystym Pythonie dla dość dużych danych wejściowych:
źródło
Ta funkcja jest bardzo zoptymalizowana.
źródło