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

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

}
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