Permutacja a kombinacja: różnica między permutacją a kombinacją

Kombinatoryka – dziedzina matematyki zajmująca się liczeniem, układami, permutacjami i kombinacjami – jest często jedną z najbardziej zagmatwanych dziedzin. Stanowi jednak podstawę całej dziedziny prawdopodobieństwa i ostatecznie odgrywa kluczową rolę w uczeniu maszynowym i sztucznej inteligencji. Z tych powodów permutacje i kombinacje to temat, który należy opanować przed kontynuowaniem.

Jednym z głównych nieporozumień, które działają jak blokada, jest różnica między permutacjami a kombinacjami. Z tego powodu przyjrzymy się dogłębnie kluczowym definicjom i cechom permutacji i kombinacji. To wyjaśni, czym różnią się oba te terminy i który z nich należy zastosować w którym scenariuszu.

Zaczynajmy!

Czym są permutacje i kombinacje – różnice między nimi

Spróbujmy zrozumieć te kluczowe terminy na kilku przykładach. Załóżmy, że chcesz zamówić sałatkę na lunch. Twoja ulubiona sałatka może być mieszanką pomidorów, marchwi, rzodkiewki i buraków. Teraz nie dbasz o kolejność, w jakiej te poszczególne warzywa są dodawane do twojej sałatki, o ile są tam wszystkie. Wszystko, na czym Ci zależy, to posiadanie wszystkich wymaganych warzyw w salaterce. Sałatka może składać się z „pomidorów, marchwi, rzodkiewki i buraków” lub „pomidory, marchew, buraki i rzodkiewka”. Oba scenariusze będą idealne dla Ciebie – jako konsumenta sałatek.

Dołącz dokursu uczenia maszynowego online z najlepszych światowych uniwersytetów – studiów magisterskich, programów studiów podyplomowych dla kadry kierowniczej oraz zaawansowanego programu certyfikacji w zakresie uczenia maszynowego i sztucznej inteligencji, aby przyspieszyć swoją karierę.

Zaczynając od permutacji

Teraz zmieńmy trochę przykład i pomyślmy o kodzie PIN karty debetowej. Jeśli Twój kod PIN to 7986, jest to zbiór cyfr 7, 8, 9 i 6. Jednak w tym przypadku nie wszystkie układy tych cyfr staną się Twoim kodem PIN. To tylko jedna konkretna sekwencja – 7896 – czyli Twój PIN. W tym przypadku kolejność jest niezbędna.

Permutacje są dokładnie takie, jak Twoje PIN-y – kolejność jest niezwykle ważna. Szczegóły są ważne dla permutacji. Do permutacji 6/8/9 jest całkowicie różne od 9/6/8, które różni się od 8/6/9 i tak dalej. Dlatego w przypadku permutacji kolejność podmiotów musi być zachowana za wszelką cenę.

Tak więc, definiując to w nieco bardziej technicznym sensie – Permutacja to proces wybierania różnych elementów, w którym kolejność wyboru ma znaczenie. Można ją opisać jako liczbę sposobów ułożenia niektórych lub wszystkich elementów danego zestawu.

Weźmy na przykład zbiór – {a, b, c}. W tym przypadku wszystkie permutacje elementów są następujące:

• ABC
• akb
• bac
• przed naszą erą
• taksówka
• cba

Specjalne przypadki permutacji

Istnieją dwa szczególne przypadki permutacji, o których należy pamiętać:

1. Z powtórzeniami

Można powiedzieć, że permutacje dla „k” czegoś z sumy „n” różnych typów są n*n*n*…k razy.

Powód jest prosty – gdy rzecz ma n różnych typów… za każdym razem masz „n” liczbę wyborów.

Na przykład: wybierając 3 z tych rzeczy, permutacje to:

n × n × n

(n pomnożone 3 razy)

Mówiąc bardziej ogólnie: wybierając „n” czegoś, co ma „k” różnych typów, permutacje są następujące:

n × n × … (k razy)

2. Bez powtórzeń

Bez powtórzeń wybory nie pozostaną „n” za każdym razem. Zamiast tego wartości maleją z każdym dokonanym wyborem. Oto przykład, aby lepiej to zrozumieć:

Spróbuj pomyśleć o liczbie różnych 4-kartowych układów utworzonych z talii kart?

Teraz, w przypadku pierwszej karty, masz możliwość wybrania dowolnej 1 z 52 kart. Masz więc 52 możliwości. Po dokonaniu pierwszego wyboru nie możesz ponownie wybrać tej samej karty, więc do wyboru w następnym gnieździe jest 51. Podobnie, każde następne losowanie spowoduje, że będziesz miał mniej wyborów niż wcześniej. Formułę tę można uogólnić jako:

Aby to uogólnić, wzór na różne permutacje „k” różnych obiektów z grupy „n” różnych obiektów można przedstawić jako:

P(n,k) = nPk = n! / (n-k)!

Gdzie nPk to liczba permutacji „k” różnych obiektów ze zbioru „n” różnych obiektów, a n! = n*(n-1)*(n-2)*(n-3)*…. .

Przejście od permutacji – teraz do kombinacji

Kombinację można rozumieć jako technikę określania liczby różnych możliwych układów w zbiorze różnych elementów – gdzie kolejność wyboru nie ma znaczenia. W kombinacji możesz wybrać elementy w dowolnej kolejności – pamiętaj o naszym wcześniejszym przykładzie swojej salaterki.

Dlatego kombinacja jest po prostu sposobem wybierania różnych elementów z kolekcji masowej, tak aby kolejność nie była ważna. Aby lepiej to zrozumieć, weźmy następujący przykład:

Załóżmy, że mamy trzy cyfry – 1, 2, 3 – i chcemy utworzyć liczbę trzycyfrową. Możliwe liczby to 123, 213, 132, 231, 312 i 321. Używając kombinacji, możemy łatwiej znaleźć liczbę sposobów, na jakie 1, 2, 3 można ustawić w określonej kolejności. Kombinacja jest wyborem k rzeczy ze zbioru n rzeczy bez zwracania i może być zapisana matematycznie w następujący sposób:

C(n,k) = nCk = n! / k! * (n-k)!

Zrozummy lepiej tę formułę na przykładzie. Spróbuj dowiedzieć się, na ile sposobów trener może wybrać trzech pływaków z grupy 6 pływaków.

Korzystając ze wzoru:

nCk = n! / k! * (n-k)!

W naszym pytaniu wartość n wynosi 6, a wartość k wynosi 3. Zachowując to we wzorze, otrzymujemy:

C(6,3) = 6! / 3!*2! = 60 => Trener może wybrać 3 pływaków z zestawu 6 pływaków na 60 różnych sposobów.

Niektóre typowe przykłady permutacji i kombinacji

Spójrzmy na kilka codziennych przykładów, które pomogą Ci lepiej zrozumieć różnice między permutacjami i kombinacjami. Dzięki tym przykładom łatwo zauważysz różnice między tymi dwiema technikami.

1. Permutacje

• Układanie różnych osób, liczb, alfabetów, cyfr, warzyw czy kolorów.
• Wybór kapitana drużyny spośród 11-osobowej drużyny.
• Wybieranie trzech ulubionych kolorów z kilku różnych kolorów.
• Wyłonienie pierwszego, drugiego i trzeciego zwycięzcy.

2. Kombinacje

• Wybieranie jadłospisu, ubrań z listy, tematów kursów itp.
• Wybieranie różnej liczby osób z grupy osób.
• Wybieranie dwóch kolorów z palety kolorów.
• Wyłonienie tylko czterech zwycięzców.

Związek między permutacją a kombinacją

Permutacje i kombinacje zasadniczo odnoszą się do różnych sposobów wybierania obiektów z zestawu – zarówno z powtórzeniem, jak i bez – w celu utworzenia nowych podmiotów. Tak więc obie te koncepcje można rozumieć jako zliczanie liczby podzbiorów dla danego zbioru. Ten wybór podzbiorów nazywa się permutacją, gdy kolejność wyboru jest ważna, a kombinacją, gdy kolejność nie jest tak ważna.

W bardziej matematycznym sensie permutacja i kombinacja są ze sobą ściśle powiązane. Kombinacja to po prostu zliczanie różnych selekcji, których można dokonać z n obiektów. Z drugiej strony permutacja to zliczanie różnych układów z n obiektów.

Jeśli przyjrzysz się uważnie poniższym dwóm formułom permutacji i kombinacji, będziesz w stanie samodzielnie wyprowadzić matematyczną zależność między nimi. Sprawdź to:

• nPr = n!/(nr)!
• nCr = n!/[r! (nr)!]

=> nPr = nCr / r!

=> nCr = r! * nPr

Wspomniane powyżej równanie to matematyczna zależność między permutacją a kombinacją.

Różnica między permutacją a kombinacją

Oto tabela, która ułatwi zrozumienie podstawowych różnic między permutacją a kombinacją.

Zrozummy różnicę między permutacją a kombinacją na przykładzie, aby dać ci wyobrażenie o tym, jak używamy ich w prawdziwym życiu.

• Tworzenie zespołu do gry: Często używamy kombinacji, aby określić, ile możliwych drużyn można utworzyć z dużej grupy graczy, aby zapewnić sprawiedliwy podział.
• Układy miejsc siedzących na wydarzeniu: możesz użyć formuły permutacji, aby określić liczbę możliwych układów miejsc siedzących na oficjalne wydarzenia lub oficjalne plany miejsc siedzących.
• Kombinacja podczas tworzenia komitetów: Możesz zastosować kombinacje, aby dowiedzieć się o możliwości utworzenia komitetu, wybierając kilka osób z większej grupy.
• Tworzenie hasła: permutacji możemy również użyć do obliczenia liczby możliwych haseł, które można utworzyć przy użyciu danego zestawu liczb, symboli i alfabetów.

Punkty do zapamiętania

• Kombinacja to liczba sposobów na wybranie podzbioru obiektów z większego zestawu bez uwzględniania kolejności. Podczas gdy permutacja to różna liczba sposobów ułożenia zestawu obiektów w określonej kolejności.
• Jeśli wartości n i k są takie same, to liczba permutacji zawsze będzie większa niż liczba kombinacji.
• Ponieważ kolejność nie ma znaczenia przy obliczaniu kombinacji, wynik wyboru tych samych k obiektów ze zbioru n elementów będzie zawsze taki sam.
• Ponieważ kolejność ma zasadnicze znaczenie w permutacji, nawet jeśli wybierzesz te same k obiektów ze zbioru n obiektów, wynik będzie się różnił w zależności od kolejności wyboru.

Podsumowując

Na tym kończymy ten wpis na blogu dotyczący różnic między permutacją a kombinacją. Należy pamiętać, że dziedzina kombinatoryki jest wyjątkowo obszerna i stanowi podstawę wielu innych ważnych dziedzin matematyki – zwłaszcza jeśli chodzi o dziedziny aplikacyjne, takie jak prawdopodobieństwo lub uczenie maszynowe. To, co omówiliśmy w artykule, to tylko podstawowe różnice między permutacją a kombinacją. Jednak mając tę ​​wiedzę po swojej stronie, możesz łatwo poradzić sobie ze wszystkimi nieporozumieniami, z którymi na ogół spotykają się studenci podczas rozwiązywania problemów związanych z PnC.

Jeśli zrozumiałeś wszystko w tym artykule, zalecamy głębsze nurkowanie i zapoznanie się z innymi niuansami kombinatoryki. Jeśli nie zrozumiałeś zbyt dobrze artykułu – zadaj swoje wątpliwości w komentarzach poniżej.

W upGrad szkoliliśmy początkujących i doświadczonych profesjonalistów i z powodzeniem pomogliśmy tysiącom studentów na całym świecie stawić czoła ich obawom i zmienić ich karierę. Nasze kursy z uczenia maszynowego i sztucznej inteligencji są zaprojektowane z myślą o nowicjuszach. Tak więc cała podstawowa matematyka, statystyka i obliczenia są nauczane w najbardziej praktyczny sposób. Jednym z takich kursów jest Executive PG Program in Machine Learning i AI oferowane we współpracy z IIIT-B. Sprawdź szczegóły kursu i zapisz się już dziś!