Subsets

Permutations

“Order matters”

There are two versions of the formula to calculate the number of permutations.

• When the order matters, use Permutations, and
• When the order doesn’t matter, use Combinations

Suppose we select $k$ slots from $n$ objects (where order matters), the number of ways this can be done is (”$n$ choose $k$”): $\frac{n!}{(n-k)!}=n^{(k)}{=}_n{P}_k$

Think about it this way. You have $n$ objects to choose from for the first slot. You have $n-1$ objects to choose for the second slot, etc, until for the last slot you have $n-k$ objects to choose from. Thus, the answer is just: $(n)(n-1)(n-2)\cdots (n-k)=\frac{n!}{(n-k)!}$

Method 1

void search() {
   if (permutation.size() == n) {
   	// process permutation
   } else {
   	for (int i = 0; i < n; i++) {
   		if (chosen[i]) continue;
   		chosen[i] = true;
   		permutation.push_back(i);
   		search();
   		chosen[i] = false;
   		permutation.pop_back();
   	}
   }
}

This is kind of similar to the Subsets logic, but be careful about the difference.

Method 2

Using Built in method in C++.

vector<int> v; 
for (int i = 0; i < n; i++) { 
	permutation.push_back(i); 
} // Store values in permutation
 
// Recommend sorting
sort(v.begin(), v.end());
 
do { check(v); // process or check the current permutation for validity 
   } while(next_permutation(v.begin(), v.end()));

Example

Create a 3-letter word using A,B,C,D without replacement. In how many ways can the letters be arranged? Answer: $4P3=4!$