fork download 
  1. use std::collections::{BTreeSet, HashMap};
  2. use std::iter::FromIterator;
  3. fn f<'a>(a: &[&'a str]) -> Vec<Vec<&'a str>> { // '
  4. 	fn g(mut a: Vec<BTreeSet<usize>>) -> Vec<BTreeSet<usize>> {
  5. 		let comb = |n| (0..n).flat_map(move |i| (i + 1..n).map(move |j| (i, j)));
  6. 		match comb(a.len()).find(|&(i, j)| !a[i].is_disjoint(&a[j])) {
  7. 			None => a,
  8. 			Some((i, j)) => g(a.iter().enumerate().filter_map(|(k, set)|
  9. 				if k == i {
  10. 					Some(BTreeSet::from_iter(a[i].union(&a[j]).cloned()))
  11. 				} else if k == j {
  12. 					None
  13. 				} else {
  14. 					Some(set.clone())
  15. 				}
  16. 			).collect()),
  17. 		}
  18. 	}
  19.     let h = a.iter().map(|&s| s.split('=')).flatten().rev().enumerate().map(|(p, s)| (s, a.len() * 2 - p)).collect::<HashMap<_, _>>();
  20. 	let a = a.iter().map(|&s| s.split('=').flat_map(|k| h.get(k)).cloned().collect::<BTreeSet<_>>()).collect();
  21. 	let hi = h.iter().map(|(&k, &v)| (v, k)).collect::<HashMap<_, _>>();
  22. 	g(a).iter().map(|set| set.iter().flat_map(|i| hi.get(i)).cloned().collect()).collect()
  23. }
  24. fn main() {
  25.     let v = ["a1=a2", "b1=b2", "b3=b2", "c1=c2", "e1=e2",
  26.              "a3=a4", "c3=c4", "e1=e3", "a2=a4", "c3=c1",
  27.              "b3=a4", "c2=d1", "a4=a5", "d2=c1", "b4=b3", "d3=c3"];
  28.     println!("{:?}", f(&v));
  29. }
Success #stdin #stdout 0s 5280KB
comments (?)
stdin 
Standard input is empty
stdout 
[["a1", "a2", "b1", "b2", "b3", "a3", "a4", "a5", "b4"], ["c1", "c2", "c3", "c4", "d1", "d2", "d3"], ["e1", "e2", "e3"]]
https://ideone.com/1PNKbR
language:
Rust (rust 1.56)
created:
101 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!