Created
April 29, 2017 18:00
-
-
Save henninglive/b697950363ab00745cd82fcfa77b37fb to your computer and use it in GitHub Desktop.
k-element subsets of an n-element set using bijection
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // k-element subsets of an n-element set. | |
| // Implemented using the Bijection Rule. The Bijection Rule | |
| // lets us find subsets of an equivalent bit set and map | |
| // those subsets to our original set to get our subsets. | |
| fn ksubset<T: Clone>(set: &[T], k: usize) -> Vec<Vec<T>> { | |
| assert!(set.len() < std::mem::size_of::<usize>() * 8); | |
| assert!(k <= set.len()); | |
| let mut subsets = Vec::new(); | |
| // Bijection to bitset(usize integer) with n elements. | |
| // Iterate all possible subsets, with all sizes 1..n. | |
| for i in 1..(1usize << set.len()) { | |
| // Return subsets with k-elements. | |
| if i.count_ones() == k as u32 { | |
| let mut subset = Vec::with_capacity(set.len()); | |
| // Map bits to elemets in set. | |
| for j in 0..set.len() { | |
| if ((i >> j) & 0x1) != 0 { | |
| subset.push(set[j].clone()); | |
| } | |
| } | |
| subsets.push(subset); | |
| } | |
| } | |
| subsets | |
| } | |
| fn main() { | |
| let set = [50, 55, 57, 58, 60]; | |
| let subset = ksubset(&set[..], 3); | |
| println!("{:?}", subset); | |
| assert_eq!(subset, vec![ | |
| vec![50,55,57], | |
| vec![50,55,58], | |
| vec![50,57,58], | |
| vec![55,57,58], | |
| vec![50,55,60], | |
| vec![50,57,60], | |
| vec![55,57,60], | |
| vec![50,58,60], | |
| vec![55,58,60], | |
| vec![57,58,60] | |
| ]); | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment