Trying to solve an algorithm for permutation or combination, without knowing the fundamentals is like convincing a girl for a night out without knowing what/when/where/how to do it ;)

So, here I'll cover all the concepts which won't let you in that situation ;)

Lets go through them one by one.

**What is factorial:**

Factorial n = n * (n-1) * (n-2) *... * 2 * 1

Ok, got it. I know this. I studied that in school. But, where does it come into Algorithm Design.

Think about this -

There are 13 cards, from 2 to A: 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K, A. We can arrange the 13 playing cards in a variety of orders, without removing any card. Factorial of 13 or 13!

There are 6 companies. In how many ways they can be merged. Answer: 6!

Factorial is about arranging/selecting "all" the available items (n out of n), without any duplicate arrangements.

Example: in how many ways 1,2,3 be arranged.

Answer: !3 = 3 * 2 * 1 = 6 ways.

123, 132, 213, 231, 312, 321

Now lets move on to the next level.

**What is Permutation:**

Yes, the order does matter!

Selecting/Arranging r items out of m, in problems where order does matter.

n P r or P(n,r) = n! / (n - r)!

When order matters AB != BA.

Now Suppose we want to take these four people and arrange them in groups of three at a time where order matters. The following demonstrates all the possible arrangements from B,A,M,S

BMS, BSM, BAS, BSA, BMA, BAM

MBS, MSB, MAS, MSA, MBA, MAB

SBM, SMB, SBA, SAB, SMA, SAM

ABM, AMB, ABS, ASB, AMS, ASM

There are 24 ways to arrange 4 objects taken 3 at a time.

There are !6/!(6-4) = !6/!2 = 360 ways to arrange 6 items taken 4 at a time when order matters.

Note:

nPn = !n/!0 = !n

There are n! ways to arrange n objects in groups of n at a time. And this is what is Factorial.

Now what if the order was not important? Lets see that.

**What is Combination:**

A combination is one of the different arrangements of a group of items where order does not matter, taking r elements out of n.

My fruit salad is a combination of apples, grapes and bananas.

When order does not matter AB = BA.

n C r or C(n,r) = !n/(!r * !(n - r))

Take 4 people and place them in groups of 3 at a time where order does not matter = C(4,3)

Select a subcommittee of 7 members from among a committee of 17 = C(17,7)

Thats it! Remember these concepts while trying for an algorithm involving select/arrange/combine/group. It helps alot to throughly get into the problem statement.

Thank you, this is so helpful :)

ReplyDeletedịch vụ kế toán

ReplyDeletedịch vụ kế toán tại quận cầu giấy

dịch vụ kế toán tại quận tại từ liêm

dịch vụ kế toán tại quận thanh xuân

dịch vụ kế toán tại quận hà đông

dịch vụ kế toán tại quận long biên

dịch vụ kế toán tại quận đống đa

dịch vụ kế toán tại quận ba đình

dịch vụ kế toán tại quận tây hồ

dịch vụ kế toán tại quận hoàng mai

dịch vụ kế toán tại thanh trì

dịch vụ kế toán tại quận hoàn kiếm

dịch vụ kế toán tại quận hai bà trưng

dịch vụ kế toán tại quận thủ đức

dịch vụ kế toán tại quận bình thạnh

dịch vụ kế toán tại quận tân phú

dịch vụ kế toán tại quận gò vấp

dịch vụ kế toán tại quận phú nhuận

dịch vụ kế toán tại quận bình tân

dịch vụ kế toán tại quận tân bình

dịch vụ kế toán tại đông anh

dịch vụ kế toán gia lâm

dịch vụ kế toán tại quận 1

dịch vụ kế toán tại quận 2

dịch vụ kế toán tại quận 3

dịch vụ kế toán tại quận 4

dịch vụ kế toán tại quận 5