Iterator for Combination

class CombinationGenerator {
    int[] sequenceIndices;
    boolean moreCombinations;
    int length, combinationSize;
    String sequence;

    public CombinationGenerator(String sequenceInput, int combSize) {
        length = sequenceInput.length();
        combinationSize = combSize;
        sequence = sequenceInput;

        moreCombinations = true;
        sequenceIndices = new int[combinationSize];
        for (int idx = 0; idx < combinationSize; ++idx) {
            sequenceIndices[idx] = idx;
        }
    }

    public String next() {
        StringBuilder currentCombination = new StringBuilder();
        for (int index : sequenceIndices) {
            currentCombination.append(sequence.charAt(index));
        }

        int idx = combinationSize - 1;
        while (idx >= 0 && sequenceIndices[idx] == length - combinationSize + idx) {
            idx--;
        }

        if (idx >= 0) {
            sequenceIndices[idx]++;
            for (int j = idx + 1; j < combinationSize; j++) {
                sequenceIndices[j] = sequenceIndices[idx] + j - idx;
            }
        } else {
            moreCombinations = false;
        }

        return currentCombination.toString();
    }

    public boolean hasNext() {
        return moreCombinations;
    }
}

The Java class CombinationGenerator provides a mechanism to iterate over combinations of characters from a given string. It allows determining all possible combinations of a specified size from the sequence of characters. Here's an overview of how this class functions and can be utilized:

• Initialization: The class is initialized with two arguments: a string (sequenceInput) and an integer (combSize). sequenceInput specifies the characters to combine, and combSize specifies the size of each combination. The initialization process involves setting up an array sequenceIndices which keeps track of the current indices of the characters in the combination.

• Generating the Next Combination:

  1. Call the next method to retrieve the next combination.
  2. Construct the current combination based on the indices and update the indices to prepare for the next call.
  3. Update the internal state to ensure that combinations can continue to be provided until all possibilities are exhausted.

• Checking for More Combinations: The hasNext method checks whether there are more combinations to generate by examining the moreCombinations flag.

Usage Example:

• Instantiate the CombinationGenerator with a specific string and combination size.
• Use a loop that continues as long as hasNext returns true, within which next is called to retrieve the next combination.

This approach provides an efficient way to iterate over combinations without calculating them all at once, thereby supporting large sequences or large combinations sizes effectively.

class ComboIterator:
    def __init__(self, chars: str, comboLength: int):
        self.total_chars = len(chars)
        self.combo_size = comboLength
        self.all_chars = chars
        
        # Initialize the first combination indices
        self.indices = list(range(comboLength))
        self.can_continue = True
    
    def next(self) -> str:
        idxs = self.indices
        chars_num, combo_num = self.total_chars, self.combo_size
        combination = [self.all_chars[j] for j in idxs]
        
        # Finding the first index that can be incremented
        i = combo_num - 1
        while i >= 0 and idxs[i] == chars_num - combo_num + i:
            i -= 1
        idxs[i] += 1
        
        # Create the next combination by increasing subsequent indices
        if i >= 0:
            for j in range(i + 1, combo_num):
                idxs[j] = idxs[i] + j - i
        else:
            self.can_continue = False
        
        return ''.join(combination)
    
    def hasNext(self) -> bool:
        return self.can_continue

This solution introduces a class ComboIterator to generate combinations of a specific length from a given string. The implementation is done in Python and encompasses two main methods (next and hasNext) along with an initialization method (__init__).

• Initialize the ComboIterator class with a string (chars) and the desired combination length (comboLength). During initialization, the method calculates the length of chars, sets the combination length, and initializes the indices for the first combination.

• The next method is responsible for returning the current combination as a string. It calculates the combination based on current indices, then updates these indices to prepare for the next combination. The index updating involves checking which elements can still be incremented without exceeding the allowed combinations. If adjustments to indices can be made, the method sets up for the next combination; otherwise, it marks that no more combinations can be generated.

• The hasNext method simply checks and returns a boolean value (self.can_continue) indicating whether there are more combinations to be returned.

This iterator efficiently handles combinations, leveraging sequential index adjustments to generate each subsequent combination, avoiding the need for recalculating or storing all possible combinations in memory. Such an approach is particularly useful for handling large datasets where memory efficiency is crucial.