1286. Iterator for Combination

Description of Problem

Design the CombinationIterator class:

• CombinationIterator(string characters, int combinationLength) Initializes the object with a string characters of sorted distinct lowercase English letters and a number combinationLength as arguments.
• next() Returns the next combination of length combinationLength in lexicographical order.
• hasNext() Returns true if and only if there exists a next combination.

Example 1:

Input
["CombinationIterator", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[["abc", 2], [], [], [], [], [], []]
Output
[null, "ab", true, "ac", true, "bc", false]


Explanation
CombinationIterator itr = new CombinationIterator("abc", 2);
itr.next();    // return "ab"
itr.hasNext(); // return True
itr.next();    // return "ac"
itr.hasNext(); // return True
itr.next();    // return "bc"
itr.hasNext(); // return False

Constraints:

• 1 <= combinationLength <= characters.length <= 15
• All the characters of characters are unique.
• At most 10^4 calls will be made to next and hasNext.
• It is guaranteed that all calls of the function next are valid.

Solution

Tags: Permutation and Combination

Explanation

We can reduce combination problems to permutation problems since choosing k elements from n elements can be treated as permutating list of 0 and 1 where the number of 1 equals to k and of 0 equals to n-k.

For example, choosing 3 elements from [1,2,3,4,5], we have [1,2,3] ([1,1,1,0,0]), [1,2,4] ([1,1,0,1,0]) and so on.

Therefore, we can reuse the solution from [46. Permutations]

Code (Rust)

struct CombinationIterator {
    characters : Vec<char>,
    perm_iter : PermutationIteratorReverse<bool>,
}

impl CombinationIterator {

    fn new(characters: String, length: i32) -> Self {
        let mut state = vec![false ; characters.len()];
        for i in 0..length as usize {
            state[i] = true;
        }
        
        CombinationIterator {
            characters : characters.chars().collect(),
            perm_iter : PermutationIteratorReverse::new(state),
        }
    }
    
    fn next(&mut self) -> String {
        use std::iter::zip;
        zip(
            &self.characters, 
            &self.perm_iter.next().unwrap()
        ).into_iter()
        .filter(|(_,b)| {
            **b
        })
        .map(|(c,_)| *c)
        .collect() 
    }

    fn has_next(&self) -> bool {
        self.perm_iter.has_next()
    }
    
}

Appendix A1 - PermutationIteratorReverse

pub struct PermutationIteratorReverse<T : Ord + Clone>(Option<Vec<T>>);

impl<T : Ord + Clone> PermutationIteratorReverse<T> {

    pub fn new(mut elements : Vec<T>) -> Self {
        elements.sort();
        elements.reverse();
        PermutationIteratorReverse(Some(elements))
    }

    pub fn has_next(&self) -> bool {
        self.0.is_some()
    }

    fn next_permutation(&mut self) -> Option<Vec<T>> {
        let res = self.0.clone();

        self.0 = self.0.take().and_then(|mut v|{
            let i = Self::find_pivot(&v)?;
            let j = Self::find_target(&mut v,  i);
            v.swap(i,j);
            let _ = &mut v[i+1..].reverse();
            Some(v)
        });

        return res;
    }

    fn find_pivot(elements : &[T]) -> Option<usize> {
        if elements.len() < 2 {
            return None;
        }

        let (mut i, mut j) = (elements.len() - 2, elements.len() - 1);
        while /* i >= 0  && */ j >= 1 {
            if elements[i] > elements[j] {
                return Some(i);
            }
            i = i.checked_sub(1).unwrap_or(0);
            j = j.checked_sub(1).unwrap_or(0);

        }

        return None;
    }

    fn find_target(elements : &mut [T], pivot : usize) -> usize {
        let pivot_value = &elements[pivot];
        let mut target_index = pivot+1;
        let mut target_value = &elements[target_index];
        for j in pivot+2..elements.len() {
            let v = &elements[j];
            if v < pivot_value && v >= target_value {
                target_value = v;
                target_index = j;
            }
        }
        return target_index;
    }

}

impl<T : Ord + Clone> Iterator for PermutationIteratorReverse<T> {
    type Item = Vec<T>;

    fn next(&mut self) -> Option<Self::Item> {
        self.next_permutation()
    }

}