generate all possible combinations of a number while each digit got different range

Question

i been searching the internet for few days now but haven't found good approach for my needs. so ill try asking.

Im looking for a way to generate all possible combinations of a number while each digit got different range.

let me give you an example:

my input: [1-3],[0-9],[4],[2-3] few of the combinations will be: 1042 1043 1142 1143 1242 and so on...

1. the code must not store all of the combinations at some variable in memory, because i'll be working with big numbers (up to 10 digits) the program can make txt file with all the possibilities and write them one by one or just print them in console.

2. the input number length and the range for each digit is unknown until it been given. so no hard coded nested loops. it must be dynamic.

i hope i was clear..

tnx

Answer 1

You can use a technique called backtracking.

Here's an example in 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;
}

Here's the output:

---------- 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

Even though this is a very old question, seeing as it's tagged C# but has no C# answers, here's my variant. It's non-recursive, which helps with performance in tight loops:

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;
}