Thursday, June 26, 2014

Combinations and Permutations



If the order doesn't matter, it is a Combination.
If the order does matter it is a Permutation.
A Permutation is an ordered Combination.
Permutations
  1. Repetition is Allowed: such as the lock above. It could be "333". n × n × ... (r times) = nr
  2. No Repetition: for example the first three people in a running race. You can't be first andsecond.
Permutations without Repetition
if we wanted to select all: then it's n!.
The factorial function (symbol: !) just means to multiply a series of descending natural numbers. 
if we wanted to select just r, then it's 
where n is the number of things to choose from, and we choose r of them
(No repetition, order matters)


Combinations

Combinations without Repetition

The easiest way to explain it is to:
  • assume that the order does matter (ie permutations),
  • then alter it so the order does not matter

where n is the number of things to choose from, and we choose r of them
(No repetition, order doesn't matter)

So remember, do the permutation, then reduce by a further "r!"
This formula is symmetrical:
In other words choosing 3 balls out of 16, or choosing 13 balls out of 16 have the same number of combinations.

Combinations with Repetition

From http://kruel.co/2012/05/06/number-of-combinations-with-repetition/#sthash.8TnqDEyX.dpbs
There are n = 4 sorts of candy to choose from and you want to buy k = 10 candies. How many ways can you do it?
Note that there are 10 symbols ‘C’ and 3 partition walls, represented by a ‘+’ sign. That is, there are n-1+k = 13, equivalently n+k-1, symbols. Further note that each of the 3 partition walls could be in 1 of 13 positions. In other words, to represent various choices of 10 candies from 4 categories, the positions of the partition walls could be rearranged by choosing n-1 = 3 of n+k-1 = 13 positions
C++CCC+CCCCCC
CCCCCCCCCC+++
We have now translated the original problem into choosing 3 of 13 available positions.
(n+k-1)!/k!(n-1)!

where n is the number of things to choose from, and we choose r of them
(Repetition allowed, order doesn't matter)
Interestingly, we could have looked at the arrows instead of the circles, and we would have then been saying "we have r + (n-1) positions and want to choose (n-1) of them to have arrows", and the answer would be the same ...
Read full article from Combinations and Permutations

Labels

Review (572) System Design (334) System Design - Review (198) Java (189) Coding (75) Interview-System Design (65) Interview (63) Book Notes (59) Coding - Review (59) to-do (45) Linux (43) Knowledge (39) Interview-Java (35) Knowledge - Review (32) Database (31) Design Patterns (31) Big Data (29) Product Architecture (28) MultiThread (27) Soft Skills (27) Concurrency (26) Cracking Code Interview (26) Miscs (25) Distributed (24) OOD Design (24) Google (23) Career (22) Interview - Review (21) Java - Code (21) Operating System (21) Interview Q&A (20) System Design - Practice (20) Tips (19) Algorithm (17) Company - Facebook (17) Security (17) How to Ace Interview (16) Brain Teaser (14) Linux - Shell (14) Redis (14) Testing (14) Tools (14) Code Quality (13) Search (13) Spark (13) Spring (13) Company - LinkedIn (12) How to (12) Interview-Database (12) Interview-Operating System (12) Solr (12) Architecture Principles (11) Resource (10) Amazon (9) Cache (9) Git (9) Interview - MultiThread (9) Scalability (9) Trouble Shooting (9) Web Dev (9) Architecture Model (8) Better Programmer (8) Cassandra (8) Company - Uber (8) Java67 (8) Math (8) OO Design principles (8) SOLID (8) Design (7) Interview Corner (7) JVM (7) Java Basics (7) Kafka (7) Mac (7) Machine Learning (7) NoSQL (7) C++ (6) Chrome (6) File System (6) Highscalability (6) How to Better (6) Network (6) Restful (6) CareerCup (5) Code Review (5) Hash (5) How to Interview (5) JDK Source Code (5) JavaScript (5) Leetcode (5) Must Known (5) Python (5)

Popular Posts