World's most popular travel blog for travel bloggers.

[Solved]: How many possible ways are there?

, , No Comments
Problem Detail: 

Suppose I have the given data set of length 11 of scores:

p=[2, 5, 1 ,2 ,4 ,1 ,6, 5, 2, 2, 1] 

I want to select scores 6, 5, 5, 4, 2, 2 from the data set. How many ways are there?

For the above example answer is: 6 ways

{p[1], p[2], p[4], p[5], p[7], p[8]} {p[10], p[2], p[4], p[5], p[7], p[8]} {p[1], p[2], p[10], p[5], p[7], p[8]} {p[9], p[2], p[4], p[5], p[7], p[8]} {p[1], p[2], p[9], p[5], p[7], p[8]} {p[10], p[2], p[9], p[5], p[7], p[8]} 

How can I count the ways in general?

Asked By : Jack

Answered By : Ran G.

Say you want to pick, out of a multiset $S$, the numbers $x_1$, $x_2$, ..., $x_n$ with multiplicity $m_1$, $m_2$, ..., $m_n$ (i.e., you want to pick $x_1$ exactly $m_1$ times). Furthermore, assume that in $S$ the numbers $x_1$, $x_2$, ..., $x_n$ have multiplicity $s_1$, $s_2$,..., $s_n$. (we assume for every $i$, $s_i \ge m_i$, otherwise no solution exists).

Consider the first element $x_1$: you have exactly $s_1 \choose m_1$ different ways to pick $m_1$ occurrences of $x_1$ from the $s_1$ times it appears in $S$.

In a similar way for all the other elements, the answer would be $${s_1 \choose m_1} {s_2 \choose m_2} \cdots {s_n \choose m_n} = \prod_{i=1}^n {s_i \choose m_i}$$


For your example, set $x_1=6$, $x_2=5$, $x_3=4$, $x_4=2$. In the data set they appear with multiplicity $s_1=1$, $s_2=2$, $s_3=1$, $s_4=4$ and you want to have $m_1=1$ sixes, $m_2=2$ fivess, $m_3=1$ fours and $m_3=2$ twos, so the number of different options is $$ {1 \choose 1} {2 \choose 2} {1 \choose 1}{4 \choose 2} = 1 \cdot 1 \cdot 1 \cdot 6$$

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/1444

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback