iTranslated by AI
The content below is an AI-generated translation. This is an experimental feature, and may contain errors. View original article
👻
Summary of Permutations and Combinations in Programming: nPr, nCr, nHr, nΠr
I have summarized information for handling permutations.
Four Patterns Table
| Name | English | Symbol | 2 items from {A, B} |
|---|---|---|---|
| Permutation | Permutation | nPr | AB BA |
| Permutation with replacement | Permutation with replacement | nΠr | AA AB BA BB |
| Combination | Combination | nCr | AB |
| Combination with replacement | Combination with replacement | nHr | AA AB BB |
Slightly More Complex Examples
Permutation
<sub>4</sub>P<sub>2</sub> (Select 2 from 4 and arrange them)
AB AC AD BA BC BD CA CB CD DA DB DC
[0, 1][0, 2][0, 3][1, 0][1, 2][1, 3][2, 0][2, 1][2, 3][3, 0][3, 1][3, 2]
Permutation with Replacement
Synonyms: sequence with repetition, Cartesian product, exhaustive enumeration.
<sub>2([0,1])</sub>Π<sub>n</sub> results in an n-bit brute-force search.
<sub>4</sub>Π<sub>2</sub> (Select 2 from 4 and arrange them with replacement)
AA AB AC AD BA BB BC BD CA CB CC CD DA DB DC DD
[0, 0][0, 1][0, 2][0, 3][1, 0][1, 1][1, 2][1, 3][2, 0][2, 1][2, 2][2, 3][3, 0][3, 1][3, 2][3, 3]
Combination
<sub>4</sub>C<sub>2</sub> (Select 2 from 4)
AB AC AD BC BD CD
[0, 1][0, 2][0, 3][1, 2][1, 3][2, 3]
Combination with Replacement
<sub>4</sub>H<sub>2</sub> (Select 2 from 4 with replacement)
AA AB AC AD BB BC BD CC CD DD
[0, 0][0, 1][0, 2][0, 3][1, 1][1, 2][1, 3][2, 2][2, 3][3, 3]
Code Examples
Rust
use itertools::{iproduct, Itertools};
// permutation
(0..3).permutations(2)
// [0, 1][0, 2][1, 0][1, 2][2, 0][2, 1]
// permutation with replacement
iproduct!(0..3, 0..3)
// (0, 0)(0, 1)(0, 2)(1, 0)(1, 1)(1, 2)(2, 0)(2, 1)(2, 2)
// combination
(0..3).combinations(2)
// [0, 1][0, 2][1, 2]
// combination with replacement
(0..3).combinations_with_replacement(2)
// [0, 0][0, 1][0, 2][1, 1][1, 2][2, 2]
I'm not as experienced with Rust, so I'm not sure how to handle permutations with replacement specifically.
In pseudocode, it looks like it could be achieved with something like this:
// Pass arrays of the same length for 'r' arguments using rest parameters (spread syntax)
iproduct!(...(0..3).repeat(2))
Python
import itertools
itertools.permutations('ABCD', 2)
# AB AC BA BC CA CB
itertools.product('ABCD', repeat=2)
# AA AB AC BA BB BC CA CB CC
itertools.combinations('ABCD', 2)
# AB AC BC
itertools.combinations_with_replacement('ABCD', 2)
# AA AB AC BB BC CC
Discussion