CODEWITHSUNDEEP
algorithm
InsaneCoder
InsaneCoder

Reputation: 8268

Algorithm to generate all possible N-digit numbers with whose digits are in increasing order

I want an algorithm to generate all possible N-digit numbers, whose digits are in increasing order.

e.g.: if N=3, then possible numbers are: 012,123,234,246,567,259, because:

0<1<2

...

2<5<9

etc.

How can I do it?

I developed the following algorithm but it only generates the numbers with consecutive increasing digits like 123,234,345,456,567, etc.. Hence, a large set of numbers is missed out.

private static void generate(int start,int n)
{
    if((start+n)>9)
        return;
    else
    {
        for(int i=0;i<n;i++)
            System.out.print(start+i);

        System.out.println();
        generate(start+1,n);
     }
}

Upvotes: 7

Views: 4343

Answers (2)

jev
jev

Reputation: 2013

From a more declarative angle the algorithm would look almost like mathematical notation (in Haskell):

generate = toInt [[a,b,c] | a <- x, b <- x, c <- x, a < b, b < c]
  where x = [0..9]
        toInt = map (foldl (\n m -> 10*n + m) 0)

where map (foldl (\n m -> 10*n + m) 0) just translates a list of digits to an integer and there rest is kind of self-documenting: take three digits whilst obeying to a given constraint.

Upvotes: 0

Henrik
Henrik

Reputation: 23324

Trying to preserve your original idea:

private static void generate(int prefix, int start, int n)
    {
        if (n == 0)
        {
            System.out.print(prefix);
            System.out.println();
        }
        else
        {
            for(int i=start;i<10;i++)
                generate(10*prefix+i, i+1, n-1);
        }
    }

Upvotes: 6

Related Questions