问按字典顺序从范围中获取下一个数字(没有包含所有字符串的容器)

EN

template <typename T>
std::string str(const T& t)
{
    std::ostringstream oss; oss << t; return oss.str();
}

template <typename T>
class Lex_Counter
{
  public:
    typedef T value_type;

    Lex_Counter(T from, T to, T first = -1)
      : from_(from), to_(to),
        min_size_(str(from).size()), max_size_(str(to).size()),
        n_(first != -1 ? first : get_first()),
        max_unit_(pow(10, max_size_ - 1)), min_unit_(pow(10, min_size_ - 1))
    { }

    operator T() { return n_; }

    T& operator++()
    {
        if (n_ == 0)
            return n_ = 1;
        if (n_ < max_unit_ && n_ * 10 <= to_)
            return n_ = n_ * 10; // e.g. 10 -> 100, 89 -> 890
        if (n_ % 10 < 9 && n_ + 1 <= to_)
            return ++n_;         // e.g. 108 -> 109
        if (min_size_ == max_size_
            ? n_ == to_
            : (n_ == max_unit_ - 1 && to_ < 10 * max_unit_ - 10 || // 99/989
               n_ == to_ && to_ >= 10 * max_unit_ - 10))   // eg. 993
            return n_ = to_ + 1;

        // increment the right-most non-9 digit
        // note: all-9s case handled above (n_ == max_unit_ - 1 etc.)
        // e.g. 109 -> 11, 19 -> 2, 239999->24, 2999->3

        // comments below explain 230099 -> 230100

        // search from the right until we have exactly non-9 digit
        for (int k = 100; ; k *= 10)
            if (n_ % k != k - 1)
            {
                int l = k / 10; // n_ 230099, k 1000, l 100
                int r = ((n_ / l) + 1) * l; // 230100
                if (r > to_ && r / 10 < from_)
                    return n_ = from_; // e.g. from_ 8, r 20...
                while (r / 10 >= from_ && r % 10 == 0)
                    r /= 10; // e.g. 230100 -> 2301
                return n_ = r <= from_ ? from_ : r;
            }
        assert(false);
    }

  private:
    T get_first() const
    {
        if (min_size_ == max_size_ ||
            from_ / min_unit_ < 2 && from_ % min_unit_ == 0)
            return from_;

        // can "fall" from e.g. 321 to 1000
        return min_unit_ * 10;
    }
    T pow(T n, int exp)
        { return exp == 0 ? 1 : exp == 1 ? n : 10 * pow(n, exp - 1); }
    T from_, to_;
    size_t min_size_, max_size_;
    T n_;
    T max_unit_, min_unit_;
};

template <typename T>
struct Shahbaz
{
    std::set<std::string> s;
    Shahbaz(T from, T to)
      : to_(to)
    {
        s.insert(str(from));
        for (int n = 10; n < to_; n *= 10)
            if (n > from) s.insert(str(n));
        n_ = atoi(s.begin()->c_str());
    }

    operator T() const { return n_; }

    Shahbaz& operator++()
    {
        if (s.empty())
            n_ = to_ + 1;
        else
        {
            s.erase(s.begin());
            if (n_ + 1 <= to_)
            {
                s.insert(str(n_ + 1));
                n_ = atoi(s.begin()->c_str());
            }
        }
        return *this;
    }

  private:
    T n_, to_;
};

void perf()
{
    DWORD start = GetTickCount();
    int to = 1000 *1000;
    // Lex_Counter<int> counter(0, to);
    Shahbaz<int> counter(0, to);

    while (counter <= to)
        ++counter;
    DWORD elapsed = GetTickCount() - start;
    std::cout << '~' << elapsed << "ms\n";
}

import math

#iterates through all numbers between start and end, that start with `cur`'s digits
def lex(start, end, cur=0):
    if cur > end:
        return
    if cur >= start:
        yield cur
    for i in range(0,10):
        #add 0-9 to the right of the current number
        next_cur = cur * 10 + i
        if next_cur == 0: 
            #we already yielded 0, no need to do it again
            continue
        for ret in lex(start, end, next_cur):
            yield ret

print list(lex(8, 203))

[10, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 11, 110, 111, 112, 113, 
114, 115, 116, 117, 118, 119, 12, 120, 121, 122, 123, 124, 125, 126, 127, 128, 
129, 13, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 14, 140, 141, 142, 
143, 144, 145, 146, 147, 148, 149, 15, 150, 151, 152, 153, 154, 155, 156, 157, 
158, 159, 16, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 17, 170, 171, 
172, 173, 174, 175, 176, 177, 178, 179, 18, 180, 181, 182, 183, 184, 185, 186, 
187, 188, 189, 19, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 20, 200, 
201, 202, 203, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 
37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 
57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 
77, 78, 79, 8, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 9, 90, 91, 92, 93, 94, 95, 
96, 97, 98, 99]

public static void generateLexicographical(int lower, int upper)
{
   for (int i = 1; i < 10; i++)
      generateLexicographical(lower, upper, i);
}

private static void generateLexicographical(int lower, int upper, int current)
{
   if (lower <= current && current <= upper)
      System.out.println(current);

   if (current > upper)
      return;

   for (int i = 0; i < 10; i++)
      generateLexicographical(lower, upper, 10*current + i);
}

public static void main(String[] args)
{
   generateLexicographical(11, 1001);
}