生成一个数字的所有可能组合，同时每个数字都有不同的范围

Question

我已经在互联网上搜索了几天，但还没有找到满足我需求的好方法。所以我试着问问。

我正在寻找一种方法来生成数字的所有可能组合，同时每个数字都有不同的范围。

让我举个例子：

我的输入：[1-3]，[0-9]，[4]，[2-3] 其中一些组合将是： 1042 1043 第1142章 第1143章 1242 依此类推...

1. 代码不得将所有组合存储在内存中的某个变量中，因为我将处理程序可以生成的大数字（最多 10 位数字） txt 文件包含所有可能性，然后将它们一一写入，或者只是在控制台中打印它们。

2. 输入数字的长度和每个数字的范围在给出之前是未知的。所以没有硬编码的嵌套循环。它必须是动态的。

我希望我说清楚了

..tnx

Answer 1

您可以使用一种名为回溯的技术。

这是一个 C++ 示例。

#include <iostream>
#include <fstream>
#include <algorithm>
#include <numeric>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <cassert>
#include <cmath>
#include <complex>
#include <stack>
#include "time.h"
using namespace std;
template <typename T> string tostr(const T& t) { ostringstream os; os<<t; return os.str(); } 

vector< pair< int, int > > ranges;
string cur;

void go(int at) {
  if (at == (int)ranges.size()) {
    // we're at the end of the ranges vector, print the number
    cout<<cur<<endl;
    return;
  }
  for(int i = ranges[at].first; i <= ranges[at].second; ++i) {
    // add the digit for this range to the string
    cur += tostr(i);

    // recursive call
    go(at+1);

    // erase the last digit we added (this is where the backtracking part comes in)
    cur.erase(cur.end()-1);
  }
}

int main() {
  ranges.push_back(make_pair(1,3));
  ranges.push_back(make_pair(0,9));
  ranges.push_back(make_pair(4,4));
  ranges.push_back(make_pair(2,3));
  cur = "";
  go(0);
  return 0;
}

这是输出：

---------- Capture Output ----------
> "c:\windows\system32\cmd.exe" /c C:\temp\temp2.exe
1042
1043
1142
1143
1242
1243
1342
1343
1442
1443
1542
1543
1642
1643
1742
1743
1842
1843
1942
1943
2042
2043
2142
2143
2242
2243
2342
2343
2442
2443
2542
2543
2642
2643
2742
2743
2842
2843
2942
2943
3042
3043
3142
3143
3242
3243
3342
3343
3442
3443
3542
3543
3642
3643
3742
3743
3842
3843
3942
3943

> Terminated with exit code 0.

Answer 2

尽管这是一个非常古老的问题，但由于它被标记为 C# 但没有 C# 答案，因此这是我的变体。它是非递归的，这有助于提高紧密循环中的性能：

var minimums = new[] { 2, 0, 1, 7, 1 };
var maximums = new[] { 4, 6, 3, 9, 4 };

var current = minimums.ToArray();
while (true)
{
    Console.WriteLine(string.Join("", current));

    int pos = 0;
    while (pos < maximums.Length)
    {
        current[pos]++;
        if (current[pos] <= maximums[pos])
            break;
        current[pos] = minimums[pos];
        pos++;
    }
    if (pos == maximums.Length)
        break;
}