1286. Iterator for Combination

using System;
using System.Collections.Generic;
using System.Text;
public class CombinationIterator {
    private List<string> combinations;
    public CombinationIterator(string characters, int combinationLength) {
        combinations = new List<string>();
        int n = characters.Length;
        int k = combinationLength;
        for (int bitmask = 0; bitmask < (1 << n); ++bitmask) {
            if (CountBits(bitmask) == k) {
                StringBuilder curr = new StringBuilder();
                for (int j = 0; j < n; ++j) {
                    if ((bitmask & (1 << (n - j - 1))) != 0) {
                        curr.Append(characters[j]);
                    }
                }
                combinations.Add(curr.ToString());
            }
        }
    }
    public string Next() {
        var res = combinations[combinations.Count - 1];
        combinations.RemoveAt(combinations.Count - 1);
        return res;
    }
    public bool HasNext() {
        return combinations.Count > 0;
    }
    private int CountBits(int bitmask) {
        int count = 0;
        while (bitmask != 0) {
            count += bitmask & 1;
            bitmask >>= 1;
        }
        return count;
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class CombinationIterator {
    private List<string> combinations;
    public CombinationIterator(string characters, int combinationLength) {
        combinations = new List<string>();
        int n = characters.size();
        int k = combinationLength;
        for (int bitmask = 0; bitmask < (1 << n); ++bitmask) {
            if (CountBits(bitmask) == k) {
                StringBuilder curr = new StringBuilder();
                for (int j = 0; j < n; ++j) {
                    if ((bitmask & (1 << (n - j - 1))) != 0) {
                        curr.Append(characters[j]);
                    }
                }
                combinations.push_back(curr.ToString());
            }
        }
    }
    public string Next() {
        var res = combinations[combinations.size() - 1];
        combinations.RemoveAt(combinations.size() - 1);
        return res;
    }
    public bool HasNext() {
        return combinations.size() > 0;
    }
    private int CountBits(int bitmask) {
        int count = 0;
        while (bitmask != 0) {
            count += bitmask & 1;
            bitmask >>= 1;
        }
        return count;
    }
}

import java.util.ArrayList;
import java.util.List;

class CombinationIterator {
    private List<String> combinations;

    public CombinationIterator(String characters, int combinationLength) {
        combinations = new ArrayList<>();
        int n = characters.length();
        int k = combinationLength;
        for (int bitmask = 0; bitmask < (1 << n); ++bitmask) {
            if (Integer.bitCount(bitmask) == k) {
                StringBuilder curr = new StringBuilder();
                for (int j = 0; j < n; ++j) {
                    if ((bitmask & (1 << (n - j - 1))) != 0) {
                        curr.append(characters.charAt(j));
                    }
                }
                combinations.add(curr.toString());
            }
        }
    }

    public String next() {
        return combinations.remove(combinations.size() - 1);
    }

    public boolean hasNext() {
        return !combinations.isEmpty();
    }
}

class CombinationIterator {
    constructor(characters, combinationLength) {
        this.combinations = [];
        let n = characters.length;
        let k = combinationLength;
        for (let bitmask = 0; bitmask < (1 << n); bitmask++) {
            if (bitmask.toString(2).split('1').length - 1 === k) {
                let curr = [];
                for (let j = 0; j < n; j++) {
                    if (bitmask & (1 << (n - j - 1))) {
                        curr.push(characters[j]);
                    }
                }
                this.combinations.push(curr.join(''));
            }
        }
    }

    next() {
        return this.combinations.pop();
    }

    hasNext() {
        return this.combinations.length > 0;
    }
}

class CombinationIterator:
    def __init__(self, characters: str, combinationLength: int):
        self.combinations = []
        n, k = len(characters), combinationLength
        for bitmask in range(1 << n):
            if bin(bitmask).count('1') == k:
                curr = [characters[j] for j in range(n) if bitmask & (1 << n - j - 1)]
                self.combinations.append(''.join(curr))

    def next(self) -> str:
        return self.combinations.pop()

    def hasNext(self) -> bool:
        return self.combinations

package main

import (
    "fmt"
    "strings"
)

type CombinationIterator struct {
    combinations []string
}

func Constructor(characters string, combinationLength int) CombinationIterator {
    var combinations []string
    n, k := len(characters), combinationLength
    for bitmask := 0; bitmask < (1 << n); bitmask++ {
        if bits.OnesCount(uint(bitmask)) == k {
            var curr strings.Builder
            for j := 0; j < n; j++ {
                if bitmask&(1<<(n-j-1)) != 0 {
                    curr.WriteByte(characters[j])
                }
            }
            combinations = append(combinations, curr.String())
        }
    }
    return CombinationIterator{combinations}
}

func (this *CombinationIterator) Next() string {
    n := len(this.combinations)
    res := this.combinations[n-1]
    this.combinations = this.combinations[:n-1]
    return res
}

func (this *CombinationIterator) HasNext() bool {
    return len(this.combinations) > 0
}

Algorithm

Сгенерируйте все возможные бинарные битовые маски длины n: от 0 до 2^n - 1.

Используйте битовые маски с k установленными битами для генерации комбинаций из k elementов. Если n - 1 - j-й бит установлен в битовой маске, это указывает на присутствие символа characters[j] в комбинации и наоборот.

Теперь у вас есть все заранее вычисленные комбинации. Извлекайте их одну за другой по каждому запросу.

😎