xdd/
generating_function.rs

1use std::fmt::Debug;
2use std::ops::{AddAssign, Mul, MulAssign};
3use num::Integer;
4use crate::{NoMultiplicity, VariableIndex};
5
6/// A Generating Function is some aggregate of the variables. This could be:
7///  * An integer, being the number of solutions. (u64, u128)
8///  * An array, being the number of solutions with a given number of the variables true (SingleVariableGeneratingFunction, SingleVariableGeneratingFunctionFixedLength)
9pub trait GeneratingFunction : Sized + Clone + Debug {
10    /// The base value for NodeIndex::FALSE
11    fn zero() -> Self;
12    /// The base value for NodeIndex::TRUE
13    fn one() -> Self;
14    /// Add two GFs.
15    fn add(self,other:Self) -> Self;
16    /// Effect of having this variable set. For a simple count, nothing. For a generating function, shift one left.
17    fn variable_set(self,variable:VariableIndex) -> Self;
18    /// Effect of having this variable set. Generally nothing
19    fn variable_not_set(self,_variable:VariableIndex) -> Self {self}
20    /// Effect of having this variable either set or not set.
21    fn deal_with_variable_being_indeterminate(self,variable:VariableIndex) -> Self {
22        let v1 = self.clone().variable_set(variable);
23        let v2 = self.variable_not_set(variable);
24        v1.add(v2)
25    }
26    /// Effect of variables inclusive_start..exclusive_end being indeterminate
27    fn deal_with_variable_range_being_indeterminate(self,inclusive_start:VariableIndex,exclusive_end:VariableIndex) -> Self {
28        let mut res = self;
29        for v in (inclusive_start.0 .. exclusive_end.0).rev() {
30            res = res.deal_with_variable_being_indeterminate(VariableIndex(v));
31        }
32        res
33    }
34}
35
36/// A generating function that can also multiply itself by some constant.
37pub trait GeneratingFunctionWithMultiplicity<M> : GeneratingFunction {
38    /// multiply self by M.
39    fn multiply(self,multiple:M) -> Self;
40}
41
42impl <G:GeneratingFunction> GeneratingFunctionWithMultiplicity<NoMultiplicity> for G {
43    fn multiply(self, _multiple: NoMultiplicity) -> Self { self }
44}
45
46/// A simple generating function that separates counts by the number of variables set.
47impl GeneratingFunction for u64 {
48    fn zero() -> Self { 0 }
49    fn one() -> Self { 1 }
50    fn add(self, other: Self) -> Self { self+other }
51    fn variable_set(self, _variable: VariableIndex) -> Self { self }
52}
53
54/// A simple generating function that separates counts by the number of variables set.
55impl GeneratingFunction for u128 {
56    fn zero() -> Self { 0 }
57    fn one() -> Self { 1 }
58    fn add(self, other: Self) -> Self { self+other }
59    fn variable_set(self, _variable: VariableIndex) -> Self { self }
60}
61
62impl <G:GeneratingFunction,I:Into<G>+Ord> GeneratingFunctionWithMultiplicity<I> for G // The requirement on Ord is to prevent a possible clash with NoMultiplicity.
63    where G:Mul<G,Output=G>,
64{
65
66    fn multiply(self, multiple: I) -> Self {
67        self*multiple.into()
68    }
69}
70
71
72
73#[derive(Clone,Eq, PartialEq,Debug)]
74/// Measure the number of solutions of the diagram separated
75/// by the number of variables that are true in the solution.
76pub struct SingleVariableGeneratingFunction<E:Integer>(pub Vec<E>);
77
78impl <E:Clone+Eq+PartialEq+Debug+Clone+Integer+AddAssign> GeneratingFunction for SingleVariableGeneratingFunction<E> {
79    fn zero() -> Self {
80        SingleVariableGeneratingFunction(vec![])
81    }
82
83    fn one() -> Self {
84        SingleVariableGeneratingFunction(vec![E::one()])
85    }
86
87    fn add(self, other: Self) -> Self {
88        let SingleVariableGeneratingFunction(mut res) = self;
89        let SingleVariableGeneratingFunction(other) = other;
90        for (i,v) in other.into_iter().enumerate() {
91            if res.len()>i { res[i]+=v } else { res.push(v) }
92        }
93        SingleVariableGeneratingFunction(res)
94    }
95
96    /// shift up by one
97    fn variable_set(self, _variable: VariableIndex) -> Self {
98        let SingleVariableGeneratingFunction(mut res) = self;
99        if res.len()>0 { res.insert(0,E::zero()); }
100        SingleVariableGeneratingFunction(res)
101    }
102}
103
104impl <E:Clone+Eq+PartialEq+Debug+Clone+Integer+AddAssign+MulAssign,M:Copy+Integer+TryInto<E>> GeneratingFunctionWithMultiplicity<M> for SingleVariableGeneratingFunction<E> {
105    fn multiply(self, multiple: M) -> Self {
106        let mut res = self;
107        let multiple : E = multiple.try_into().map_err(|_|()).expect("Could not convert multiplicity into generating function element type");
108        for i in 0..res.0.len() {
109            res.0[i]*=multiple.clone();
110        }
111        res
112    }
113}
114
115
116/// A generating function whose i^th element is the number of elements in the set with multiplicity i+1.
117#[derive(Clone,Eq, PartialEq,Debug)]
118pub struct GeneratingFunctionSplitByMultiplicity<E:Integer>(pub Vec<E>);
119
120impl <E:Clone+Eq+PartialEq+Debug+Clone+Integer+AddAssign> GeneratingFunction for GeneratingFunctionSplitByMultiplicity<E> {
121    fn zero() -> Self {
122        GeneratingFunctionSplitByMultiplicity(vec![])
123    }
124
125    fn one() -> Self {
126        GeneratingFunctionSplitByMultiplicity(vec![E::one()])
127    }
128
129    fn add(self, other: Self) -> Self {
130        let GeneratingFunctionSplitByMultiplicity(mut res) = self;
131        let GeneratingFunctionSplitByMultiplicity(other) = other;
132        for (i,v) in other.into_iter().enumerate() {
133            if res.len()>i { res[i]+=v } else { res.push(v) }
134        }
135        GeneratingFunctionSplitByMultiplicity(res)
136    }
137
138    /// don't care about variables.
139    fn variable_set(self, _variable: VariableIndex) -> Self { self }
140}
141
142impl <E:Clone+Eq+PartialEq+Debug+Clone+Integer+AddAssign,M:Copy+Integer+TryInto<u64>> GeneratingFunctionWithMultiplicity<M> for GeneratingFunctionSplitByMultiplicity<E> {
143    fn multiply(self, multiple: M) -> Self {
144        let multiple : u64 = multiple.try_into().map_err(|_|()).expect("Could not convert multiplicity into u64");
145        if multiple > 0 && self.0.len()>0 {
146            // want position i-1 to go to position multiple*i-1. So insert multiple-1 zeros before each element.
147            let mut res = vec![];
148            for e in self.0 {
149                for _ in 1..multiple { res.push(E::zero())}
150                res.push(e);
151            }
152            GeneratingFunctionSplitByMultiplicity(res)
153        } else { self }
154    }
155}
156
157
158#[derive(Clone,Eq, PartialEq,Debug)]
159/// a generating function with a fixed maximum length.
160/// Like SingleVariableGeneratingFunction but discard all values higher than a given size.
161pub struct SingleVariableGeneratingFunctionFixedLength<const L:usize>(pub Vec<u64>);
162
163impl <const L:usize> GeneratingFunction for SingleVariableGeneratingFunctionFixedLength<L> {
164    fn zero() -> Self {
165        SingleVariableGeneratingFunctionFixedLength::<L>(vec![])
166    }
167
168    fn one() -> Self {
169        SingleVariableGeneratingFunctionFixedLength::<L>(vec![1])
170    }
171
172    fn add(self, other: Self) -> Self {
173        let SingleVariableGeneratingFunctionFixedLength(mut res) = self;
174        let SingleVariableGeneratingFunctionFixedLength(other) = other;
175        for i in 0..other.len() {
176            let v = other[i];
177            if res.len()>i { res[i]+=v } else { res.push(v) }
178        }
179        SingleVariableGeneratingFunctionFixedLength::<L>(res)
180    }
181
182    /// shift up by one
183    fn variable_set(self, _variable: VariableIndex) -> Self {
184        let SingleVariableGeneratingFunctionFixedLength(mut res) = self;
185        if res.len()>0 { res.insert(0,0); }
186        if res.len()>L { res.pop(); }
187        SingleVariableGeneratingFunctionFixedLength::<L>(res)
188    }
189}
xdd/generating_function.rs

xdd/
generating_function.rs
