Grcov report - combinatorics.rs

1

use thiserror::Error;

2

use ustr::Ustr;

3

4

#[derive(Clone, Debug, PartialEq, Eq, Error)]

5

pub enum CombinatoricsError {

6

    #[error("The operation is not defined for the given input: {0}")]

7

    NotDefined(Ustr),

8

    #[error("The result is too large to fit into the return type")]

9

    Overflow,

10

11

12

impl CombinatoricsError {

13

    pub fn not_defined(input: impl Into<Ustr>) -> Self {

14

        Self::NotDefined(input.into())

15

16

17

18

/// Count *combinations* - the number of ways to pick `n_choose` items from `n_total`,

19

/// where order does not matter.

20

///

21

/// # Formula

22

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

23

///

24

/// Not defined for r > n.

25

218458

pub fn count_combinations(n_total: u64, n_choose: u64) -> Result<u64, CombinatoricsError> {

26

218458

    if n_choose > n_total {

27

        return Err(CombinatoricsError::not_defined(

28

            "n_choose must be <= n_total",

29

));

30

218458

31

32

    // Use symmetry C(n, k) == C(n, n-k) to make the loop smaller

33

218458

    let k = n_choose.min(n_total - n_choose);

34

35

    // Repeatedly multiply / divide as factors get big fast;

36

    // return None if we overflow anyway

37

218817

    (1u64..=k).try_fold(1u64, |acc, val| {

38

181059

        n_total

39

181059

            .checked_sub(val)

40

181059

            .ok_or(CombinatoricsError::Overflow)? // n_total - val

41

181059

            .checked_add(1u64)

42

181059

            .ok_or(CombinatoricsError::Overflow)? // + 1

43

181059

            .checked_mul(acc)

44

181059

            .ok_or(CombinatoricsError::Overflow)? // * acc

45

181058

            .checked_div(val)

46

181058

            .ok_or(CombinatoricsError::Overflow) // / val

47

181059

})

48

218458

49

50

/// Count *permutations* - the number of ways to pick `n_choose` items from `n_total`,

51

/// where order matters.

52

///

53

/// # Formula

54

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

55

///

56

/// Not defined for r > n.

57

818

pub fn count_permutations(n_total: u64, n_choose: u64) -> Result<u64, CombinatoricsError> {

58

818

    if n_choose > n_total {

59

        return Err(CombinatoricsError::not_defined(

60

            "n_choose must be <= n_total",

61

));

62

818

63

64

818

    let start = n_total

65

818

        .checked_sub(n_choose)

66

818

        .ok_or(CombinatoricsError::Overflow)?

67

818

        .checked_add(1u64)

68

818

        .ok_or(CombinatoricsError::Overflow)?;

69

3490

    (start..=n_total).try_fold(1u64, |acc, val| {

70

3490

        acc.checked_mul(val).ok_or(CombinatoricsError::Overflow)

71

3490

})

72

818

73

74

/// Count *surjections* from an `n`-element set onto a `k`-element set: the Stirling number of the

75

/// second kind `S(n, k)`, i.e. the number of ways to partition `n` labelled elements into exactly

76

/// `k` non-empty unlabelled blocks (a surjection onto `k` elements is exactly a choice of which

77

/// block maps to which target element, and blocks are otherwise interchangeable until that

78

/// assignment -- so partitioning first and multiplying by `k!` elsewhere gives the surjection

79

/// count; this function returns the partition count alone).

80

///

81

/// # Formula

82

/// `S(n, k) = k * S(n-1, k) + S(n-1, k-1)`, with `S(0, 0) = 1`, `S(n, 0) = 0` for `n > 0`, and

83

/// `S(n, k) = 0` for `k > n`.

84

2

pub fn stirling_second_kind(n: u64, k: u64) -> Result<u64, CombinatoricsError> {

85

2

    if k > n {

86

        return Ok(0);

87

2

88

    // table[i][j] = S(i, j), for i in 0..=n, j in 0..=k.

89

2

    let mut table = vec![vec![0u64; (k + 1) as usize]; (n + 1) as usize];

90

2

    table[0][0] = 1;

91

2

    for i in 1..=n {

92

7

        for j in 1..=k.min(i) {

93

12

            let term1 = j

94

12

                .checked_mul(table[(i - 1) as usize][j as usize])

95

12

                .ok_or(CombinatoricsError::Overflow)?;

96

12

            let term2 = table[(i - 1) as usize][(j - 1) as usize];

97

12

            table[i as usize][j as usize] = term1

98

12

                .checked_add(term2)

99

12

                .ok_or(CombinatoricsError::Overflow)?;

100

101

102

2

    Ok(table[n as usize][k as usize])

103

2

104

105

/// Count *derangements* of `n` elements: permutations with no fixed points at all.

106

///

107

/// # Formula

108

/// `D(n) = (n-1) * (D(n-1) + D(n-2))`, with `D(0) = 1`, `D(1) = 0`.

109

8

pub fn derangements(n: u64) -> Result<u64, CombinatoricsError> {

110

8

    if n == 0 {

111

1

        return Ok(1);

112

7

113

7

    let mut prev2 = 1u64; // D(0)

114

7

    let mut prev1 = 0u64; // D(1)

115

7

    if n == 1 {

116

2

        return Ok(prev1);

117

5

118

5

    for i in 2..=n {

119

10

        let sum = prev1

120

10

            .checked_add(prev2)

121

10

            .ok_or(CombinatoricsError::Overflow)?;

122

10

        let current = (i - 1)

123

10

            .checked_mul(sum)

124

10

            .ok_or(CombinatoricsError::Overflow)?;

125

10

        prev2 = prev1;

126

10

        prev1 = current;

127

128

5

    Ok(prev1)

129

8

130

131

/// Count ways to partition `n` labelled elements into exactly `k` unlabelled, non-empty blocks,

132

/// each block's size restricted to `[block_min, block_max]`.

133

///

134

/// Generalises [`stirling_second_kind`] (which is the `block_min = 1, block_max = n` case) to a

135

/// bounded block size, needed for a partition domain's own `numParts`/`partSize` attributes.

136

///

137

/// # Method

138

/// Builds each partition by always placing the smallest not-yet-placed element into a fresh

139

/// block, then choosing the rest of that block's members from the remaining elements -- this

140

/// canonical "root by smallest element" construction counts each unordered partition exactly

141

/// once, unlike naively assigning elements to numbered blocks (which overcounts by the blocks'

142

/// own arbitrary ordering). Recurrence, with `g(n, k)` counting `n` elements into `k` blocks:

143

/// `g(0, 0) = 1`, `g(n, 0) = 0` for `n > 0`, `g(0, k) = 0` for `k > 0`, and for `n, k > 0`:

144

/// `g(n, k) = sum_{s=block_min}^{min(block_max, n)} C(n-1, s-1) * g(n-s, k-1)`

145

/// (choose `s`, the size of the block containing the smallest remaining element, then its other

146

/// `s-1` members from the other `n-1` elements).

147

9

pub fn restricted_partition_count(

148

9

    n: u64,

149

9

    k: u64,

150

9

    block_min: u64,

151

9

    block_max: u64,

152

9

) -> Result<u64, CombinatoricsError> {

153

9

    let block_min = block_min.max(1);

154

9

    if block_max < block_min || k == 0 && n > 0 || k > 0 && n == 0 {

155

1

        return Ok(0);

156

8

157

8

    if n == 0 && k == 0 {

158

        return Ok(1);

159

8

160

161

    // table[i][j] = g(i, j), for i in 0..=n, j in 0..=k.

162

8

    let mut table = vec![vec![0u64; (k + 1) as usize]; (n + 1) as usize];

163

8

    table[0][0] = 1;

164

8

    for i in 1..=n {

165

32

        for j in 1..=k.min(i) {

166

60

            let mut total = 0u64;

167

60

            let s_max = block_max.min(i);

168

60

            for s in block_min..=s_max {

169

168

                let choose = count_combinations(i - 1, s - 1)?;

170

168

                let rest = table[(i - s) as usize][(j - 1) as usize];

171

168

                let term = choose

172

168

                    .checked_mul(rest)

173

168

                    .ok_or(CombinatoricsError::Overflow)?;

174

168

                total = total

175

168

                    .checked_add(term)

176

168

                    .ok_or(CombinatoricsError::Overflow)?;

177

178

60

            table[i as usize][j as usize] = total;

179

180

181

8

    Ok(table[n as usize][k as usize])

182

9