krw12572 krw12572 - 7 months ago 21
Python Question

How to generate a 'N' digit Self describing number

How can I construct a

N
digit number which follows certain condition as follows.....

A) 1st digit equals to the numbers of 0's,

B) 2ond digit equals to the numbers of 1's,

C) 3rd digit equals to the numbers of 2's,

D) 4th equals number of 4's till Nth digit equals to the numbers of (N-1)'s.

I know that such number is called as Self-describing number

eg-
6210001000
is the 10 digit number of such kind.

But I need to know the
C#
or
Java
program to generate such number.

There is a bit similar question here which contain
python
program to find such number but I am not much familiar with python` and judging from that question and its comments, the programs given there faces serious performance issue.

Edit: this is python version of constructing such number

def to_the_number(n):
digits=list(map(int,n))
assert(len(digits))==10
done = False
while not done:
done = True
for i in range(10):
if digits[i]!=digits.count(i):
digits[i]=digits.count(i)
print(digits)
done = False
return ''.join(map(str, digits))


which only works for N=10

Answer

Following code generates 10 digit self describing number

class NumberConstructor
{
    uint inds_sum = 0;
    uint inds_val = 0;
    private uint noOfDigits;
    private uint inds_max;
    uint[] inds = new uint[10];
    uint[] nums = new uint[10];
    private uint[] digs = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

    public void SelfDesc()
    {
        noOfDigits = 10;

        inds_max = noOfDigits - 1;

        GenerateSelfDescribingNumber(noOfDigits);

        Console.ReadLine();
    }
    private void GenerateSelfDescribingNumber(uint i)
    {
        uint j;

        if (i != 0)
        {
            var diff_sum = noOfDigits - inds_sum;
            var upper_min = inds_sum != 0 ? diff_sum : inds_max;

            j = i - 1;

            uint lower;
            uint upper;

            if (j != 0)
            {
                lower = 0;
                upper = (noOfDigits - inds_val)/j;
            }
            else
            {
                lower = diff_sum;
                upper = diff_sum;
            }

            if (upper < upper_min)
                upper_min = upper;

            for (inds[j] = lower; inds[j] <= upper_min; inds[j]++)
            {
                if (inds[j] < i || nums[inds[j]] < inds[inds[j]])
                {
                    nums[inds[j]]++;
                    inds_sum += inds[j];
                    inds_val += inds[j]*j;
                    uint k;

                    for (k = inds_max; k > j && inds[k] - nums[k] <= i; k--) ;

                    if (k == j)
                        GenerateSelfDescribingNumber(i - 1);

                    inds_val -= inds[j]*j;
                    inds_sum -= inds[j];
                    nums[inds[j]]--;
                }
            }
        }
        else
        {
            for (j = 0; j < noOfDigits; j++)
                Console.Write(digs[inds[j]]);

            Console.WriteLine();
        }
    }
}

I got some help from here

Comments