diff options
author | Dan Davison <dandavison7@gmail.com> | 2019-07-26 20:18:05 -0400 |
---|---|---|
committer | Dan Davison <dandavison7@gmail.com> | 2019-07-28 21:49:57 -0400 |
commit | 5b3a8fc79e867d175c894399f8d9f98765856f3c (patch) | |
tree | 595e1fde7705a1353e636c705e5b63c0542985f7 /src | |
parent | 6ee4fb4db72eecb7704c74cb76f77b5ec7e29000 (diff) |
Interleavings
Diffstat (limited to 'src')
-rw-r--r-- | src/interleavings.rs | 88 | ||||
-rw-r--r-- | src/main.rs | 1 |
2 files changed, 89 insertions, 0 deletions
diff --git a/src/interleavings.rs b/src/interleavings.rs new file mode 100644 index 00000000..25dcc871 --- /dev/null +++ b/src/interleavings.rs @@ -0,0 +1,88 @@ +/// Return the set of all interleavings of two sequences. +pub fn interleavings<'a, T>(s1: &'a [T], s2: &'a [T]) -> Vec<Vec<&'a T>> { + let mut _interleavings = Vec::with_capacity(number_of_interleavings(s1, s2)); + if s1.len() > 0 || s2.len() > 0 { + if s1.len() == 0 { + _interleavings.push(s2.iter().collect()); + } else if s2.len() == 0 { + _interleavings.push(s1.iter().collect()); + } else { + extend_interleavings(s1, s2, &mut _interleavings); + extend_interleavings(s2, s1, &mut _interleavings); + } + } + _interleavings +} + +fn extend_interleavings<'a, T>(s1: &'a [T], s2: &'a [T], _interleavings: &mut Vec<Vec<&'a T>>) { + let (first, rest) = s1.split_first().unwrap(); + for child_interleaving in interleavings(rest, s2) { + let mut interleaving = Vec::new(); + interleaving.push(first); + interleaving.extend(child_interleaving); + _interleavings.push(interleaving); + } +} + +/// The number of possible interleavings of two sequences. +// Let s1.len() == n1 and s2.len() == n2. Then, since the subsequences +// retain their order, the number of possible interleavings is equal +// to the number of ways of choosing n1 slots from (n1 + n2) slots. +fn number_of_interleavings<T>(s1: &[T], s2: &[T]) -> usize { + number_of_subsets(s1.len() + s2.len(), s1.len()) +} + +/// The number of subsets of size k that can be formed from a set of size n, i.e. n choose k. +fn number_of_subsets(n: usize, k: usize) -> usize { + number_of_tuples(n, k) / number_of_tuples(k, k) +} + +/// The number of k-tuples that can be formed from a set of size n, i.e. the falling factorial. +/// prod_{i=0}^{k-1} (n - i) +fn number_of_tuples(n: usize, k: usize) -> usize { + (0..k).map(|i| n - i).product() +} + +mod tests { + use super::*; + + #[test] + fn test_number_of_tuples() { + assert_eq!(number_of_tuples(5, 3), 60); + } + + #[test] + fn test_number_of_subsets() { + assert_eq!(number_of_subsets(5, 3), 10); + } + + #[test] + fn test_number_of_interleavings() { + let s1 = vec![1, 2, 3, 4, 5, 6]; + let s2 = vec![7, 8, 9, 10, 11]; + assert_eq!(number_of_interleavings(&s1, &s2), number_of_subsets(11, 6)); + assert_eq!(interleavings(&s1, &s2).len(), number_of_subsets(11, 6)); + } + + #[test] + fn test_interleavings_0() { + assert_eq!( + interleavings(&Vec::<u8>::new(), &Vec::<u8>::new()), + Vec::<Vec::<&u8>>::new() + ); + } + + #[test] + fn test_interleavings_1() { + assert_eq!(interleavings(&vec![1], &Vec::<u8>::new()), vec![vec![&1]]); + } + + #[test] + fn test_interleavings_2() { + assert_eq!( + interleavings(&vec![1], &vec![2, 3]), + vec![vec![&1, &2, &3], vec![&2, &3, &1], vec![&2, &1, &3]] + ); + } + +} diff --git a/src/main.rs b/src/main.rs index cb13b118..b7838633 100644 --- a/src/main.rs +++ b/src/main.rs @@ -7,6 +7,7 @@ mod config; mod delta; mod draw; mod edits; +mod interleavings; mod paint; mod parse; mod style; |