Return well-formed numbers [closed]

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center. Closed 11 years ago.

I found this in an interview questions forum:

Write a function to return well formed numbers of size n. A well formed number is one in which digit i is less than digit i+1, for example 123, 246, 349 etc

So here's how I would do it in Python:

• input number of digits (x)
• loop over all the numbers of x digits
• for each number n, if str(n) == "".join(sorted(str(n))), print number

So my question is... Is this method efficient and pythonic? I开发者_如何转开发'm sure there should be a more elegant way out there, so any tips would be great appreciated.

Craig

---

How about this solution?

[int("".join(x)) for x in itertools.combinations("123456789", n)]

---

In my opinion, you've already lost if you're checking every number.

I'd implement this with a stack. Start by putting 1-9 on the stack. When you take a number off of the stack, add another number to it if you can following those rules. If it's n digits, then print it. If it's not n digits, put it back on the stack.

Let's say you grab 7 from the stack. 8 and 9 are the only numbers bigger than 7, so in o(1) time you can put 78 and 79 on the stack.

---

1) You are trying to return well formed numbers 'up to' n digits in your approach, that is probably not the thing they were asking for

2) Sorting each number in that range is a bit silly. You may check whether each number is a well formed one by comparing the consecutive digits, which will take O(d) time for each number. However, sorting will definitely take more than that.

---

My thought would be to follow the logic:

• For a given number, the digits we can add to the beginning of it and still get a well-formed number are all less than the minimum digit in the number
• For a given well-formed number, the minimum digit is always the first digit
• The maximum number of digits we can add to a given number and keep it well-formed is equal to it's (minimum digit - 1)

Given the above, the following could be used to solve the problem:

def _well_formed_numbers(current_number_str, size):
    if size == 0: 
        # we don't need to add any more
        return [current_number_str]
    if(len(current_number_str) == 0):
        min_digit = 9
    else:
        min_digit = int(current_number_str[0]) - 1
    if min_digit < size: 
        raise Exception("can't add " + str(size) + " more digits to " + current_number_str)
    # Return a list of all the numbers resulting from recursively applying 
    # this function to the "children" of the number we already have
    # Children are the input number with one valid digit added to the beginning
    # valid digits are [size .. min_digit], inclusive
    return reduce(lambda x,y: x+y, [_well_formed_numbers(str(digit) + str(current_number_str), size-1) for digit in range(size,min_digit+1)])

def well_formed_numbers(size):
    if size <= 0 or size >= 10:
        raise "invalid size for perfect number: " + str(size)
    return _well_formed_numbers("", size)

if __name__ == '__main__':
    import unittest
    class Tests(unittest.TestCase):
        def testMaxList(self):
            self.assertEqual(["123456789"], well_formed_numbers(9))

        def testEightList(self):
            self.assertEqual(sorted(['12345678', '12345679', '12345689', '12345789', '12346789', '12356789', '12456789', '13456789', '23456789']), sorted(well_formed_numbers(8)))

        def testOneList(self):
            self.assertEqual(sorted(["1","2","3","4","5","6","7","8","9"]), sorted(well_formed_numbers(1)))

        def testTwoList(self):
            self.assertEqual(sorted(['12', '13', '23', '14', '24', '34', '15', '25', '35', '45', '16', '26', '36', '46', '56', '17', '27', '37', '47', '57', '67', '18', '28', '38', '48', '58', '68', '78', '19', '29', '39', '49', '59', '69', '79', '89']), sorted(well_formed_numbers(2)))

    unittest.main()

Admittedly, Sven Marnach's answer is shorter and cleverer... but this one shows the thought process of a reasonable algorithm.

---

I'd propose the following:

the maximal value of the i-th digit is max[i] = 10 - (len - i)

• start with 1..n
• on each step, find the leftmost position i where digit[i] == max[i]
• if no such i is found, increase the rightmost digit
• if i is found, and it is = 0, we're done
• if i is found, and it is > 0, increase digit[i - 1] and fill the rest so that digit[j] = digit[j - 1] + 1

in (the intentionally ugly) python

a = [1, 2, 3]
n = len(a)

while 1:
    print a
    f = 0
    for i in range(n):
        if a[i] == 10 - (n - i):
            if i == 0:
                exit()
            else:
                f = 1
                a[i - 1] += 1
                for j in range(i, n):
                    a[j] = a[j - 1] + 1
                break

    if f == 0:
        a[n - 1] += 1

---

Your implementation doesn't ensure either the number of digits, or the strictly less than part of the well-formedness requirement.

---

Anyway, here's an efficient way to produce the sequence without any library functions (conversion to python is left as an exercise for the reader):

void find_well_formed(char* pfirst, char* pnext, int min, int slack, int digits_left)
{
    if (!digits_left) puts(pfirst);
    else for( int i = 0; i <= slack; ++i )
        find_well_formed(pfirst, pnext+1, (*pnext=min+i)+1, slack - i, digits_left-1);
}

char* result = malloc(n+2);
result[n] = '\n';
find_well_formed(&result[0], &result[0], '1', 9-n, n);
free(result);

Demo: http://ideone.com/0oZAV

If python is requiring more code to solve this than C++, something's wrong.