How to get all possible n-digit numbers that can b

Question

I am coding a part of a big application where I am facing this problem. I will abstract you all from all the details by presenting a similar plain-vanilla scenario.

I am given n (the no. of digits of the number to be formed at run-time).

I am also given a list of numbers say {2,4,8,9}.

I have to form all the possible numbers that can be formed from the above list of the given length.

e.g. if n = 3 and list = {4, 5, 6}

then the possible number are:

444,
445,
446,
454,
455,
456,
464,
465,
466, 

and so on...

Any help will be appreciated!

regards

shahensha

Answer 1

Use recursive function. This is an example in javascript...

var result;
function recurse(n,lst,s){
  var i,c;  
  for (i=0; i<lst.length; i++){
    if(n>1)recurse(n-1,lst,s+lst[i]);
    else result.push(s+lst[i])
  }
}
function generate(n,lst){
  result=[];
  if(n>0 && lst.length>0){
    for(var i=0; i<lst.length; i++)lst[i]=''+lst[i];
    recurse(n,lst,'')
  }
  return result
}
generate(3,[4,5,6]);

Answer 2

my approach would be the following:

list combine(list a, list b)
{
    list c;
    for ( i = 0, i < list.size(), ++i )
    {
        for ( j = 0, j < list.size(), ++j )
            c.add( a[i] * pow(10,log_10(b[j]) + 1) + b[j] );
    }
    return c;
}

and then for the n-digit problem:

list nDigit(list a, int n)
{
    list out;
    out = combine(a, a);
    for ( i = 1, i < n, ++i )
        out = combine(a, out);
    return out;
}

this should do the magic. The code should be self-explanatory, if it isn't please leave a comment.

You'll have to pay attention if the list items can be longer than a digit. Then you need to add the following in the combine function:

[....]
for ( j = 0, j < list.size(), ++j )
{
    if ( log_10(a[i]) + log_10(b[j]) + 1 <= n )
        c.add( a[i] * pow(10,log_10(b[j]) + 1) + b[j] );
}
[....]

and of course give n to the combine function.

In the end in nDigit you have to check if there are combinations with length less than n

Answer 3

I wrote following F# code to solve this problem:

let rec variations rank xs = 
    match rank with
    | 1 -> 
        seq {
            for x in xs do
            yield [x]
        }

    | _ -> 
        seq {
            for x in xs do
            for y in variations (rank-1) xs do   
            yield x::y
        }

So,

variations 3 (seq {4..6})
|> Seq.iter (printfn "%s")

Will print

444
445
446
454
455
...
666

all 27 values

Answer 4

Your task is equivalent to count in a base different from 10, as the following C++ program demonstrates:

#include <vector>
#include <iostream>

using std::vector;

unsigned int pow(unsigned int n, unsigned int m)
{
    unsigned int to_ret = 1;
    for (unsigned int i = 0; i < m; i++)
        to_ret *= n;
    return to_ret;
}

void print_all(vector<unsigned int> sym, unsigned int n)
{
    const unsigned int m = sym.size();
    unsigned int max = pow(m, n);
    char *text = new char[n + 1];
    text[n] = '\0';
    for (unsigned int i = 0; i < max; i++) {
        unsigned int to_print = i;
        for (unsigned int j = 1; j <= n; j++) {
            text[n - j] = sym[to_print % m];
            to_print /= m;
        }
        std::cout << text << std::endl;
    }
    delete[] text;
}

int main(int argc, char **argv)
{
    vector<unsigned int> a({'1','2','3','4','5'});
    print_all(a, 5);
    return 0;
}

The obvious problem with this approach is given by the easy overflow of max for high enough values of n and m. You can solve that by mimicking the counting using an array of m linked lists, which must represent the "digits".

Answer 5

You can use recursion. Say the numbers you can use are in an array.

C# code:

static int[] digits = new int[] {4, 5, 6};

static void Rec(int current, int numDigits) {
    if(numDigits==0)
        Console.WriteLine(current);
    else
        foreach(int x in digits)
            Rec(current*10+x, numDigits-1);
}

And then call:

static void Main(string[] args){
    Rec(0, 3);
}