How to get all possible n-digit numbers that can be formed using given digits?

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

Solution 1

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

Solution 2

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]);