Self-describing numbers: Difference between revisions

From Rosetta Code
Content added Content deleted
m (→‎{{header|Go}}: language change. rune type)
(Updated D code functional version)
Line 180: Line 180:
<lang d>import std.stdio, std.algorithm, std.range, std.conv;
<lang d>import std.stdio, std.algorithm, std.range, std.conv;


bool isSelfDescribing(long n) {
bool isSelfDescribing(in long n) {
auto nu = map!q{a - '0'}(text(n));
auto nu = map!q{a - '0'}(text(n));
auto f = map!((a){ return count(nu, a); })(iota(walkLength(nu)));
auto f = map!(a => count(nu, a))(iota(walkLength(nu)));
return equal(nu, f);
return equal(nu, f);
}
}


void main() {
void main() {
writeln(filter!isSelfDescribing(iota(4_000_000)));
writeln(filter!isSelfDescribing(iota(4_000_000)));
}</lang>
}</lang>
Output:
Output:
<pre>[1210, 2020, 21200, 3211000]</pre>
<pre>[1210, 2020, 21200, 3211000]</pre>
(About 5.2 seconds run time.)
(About 5.2 seconds run time.)

===A faster version===
===A faster version===
<lang d>import std.stdio;
<lang d>import std.stdio;

Revision as of 23:05, 27 December 2011

This task has been clarified. Its programming examples are in need of review to ensure that they still fit the requirements of the task.
Task
Self-describing numbers
You are encouraged to solve this task according to the task description, using any language you may know.

There are several integers numbers called "self-describing".

Integers with the property that, when digit positions are labeled 0 to N-1, the digit in each position is equal to the number of times that that digit appears in the number.

For example 2020 is a four digit self describing number.

Position "0" has value 2 and there is two 0 in the number. Position "1" has value 0 because there are not 1's in the number. Position "2" has value 2 and there is two 2. And the position "3" has value 0 and there are zero 3's.

Self-describing numbers < 100.000.000: 1210 - 2020 - 21200 - 3211000 - 42101000

Task Description
  1. Write a function/routine/method/... that will check whether a given positive integer is self-describing.
  2. As an optional stretch goal - generate and display the set of self-describing numbers.

AutoHotkey

Uses CountSubString: http://rosettacode.org/wiki/Count_occurrences_of_a_substring#AutoHotkey <lang AutoHotkey>; The following directives and commands speed up execution:

  1. NoEnv

SetBatchlines -1 ListLines Off Process, Priority,, high

MsgBox % 2020 ": " IsSelfDescribing(2020) "`n" 1337 ": " IsSelfDescribing(1337) "`n" 1210 ": " IsSelfDescribing(1210) Loop 100000000 

  If IsSelfDescribing(A_Index)
     list .= A_Index "`n"

MsgBox % "Self-describing numbers < 100000000 :`n" . list

CountSubstring(fullstring, substring){ 

  StringReplace, junk, fullstring, %substring%, , UseErrorLevel
  return errorlevel

}

IsSelfDescribing(number){ 

  Loop Parse, number
     If Not CountSubString(number, A_Index-1) = A_LoopField
        return false
  return true

}</lang> Output: 

---------------------------
Self.ahk
---------------------------
Self-describing numbers < 100000000 :
1210
2020
21200
3211000
42101000

---------------------------
OK   
---------------------------

BASIC

<lang qbasic>Dim x, r, b, c, n, m As Integer Dim a, d As String Dim v(10), w(10) As Integer Cls For x = 1 To 5000000 

  a$ = ltrim$(Str$(x))
  b = Len(a$)
  For c = 1 To b
     d$ = Mid$(a$, c, 1)
     v(Val(d$)) = v(Val(d$)) + 1
     w(c - 1) = Val(d$)
  Next c
  r = 0
  For n = 0 To 10
     If v(n) = w(n) Then r = r + 1 
     v(n) = 0 
     w(n) = 0
  Next n
  If r = 11 Then Print x; " Yes,is autodescriptive number"

Next x Print Print "End" sleep end</lang>

C

<lang c>#include <stdio.h>

int self_desc(char *s) { unsigned char cnt[10] = {0}; int i; for (i = 0; s[i] != '\0'; i++) cnt[s[i] - '0']++; for (i = 0; s[i] != '\0'; i++) if (cnt[i] + '0' != s[i]) return 0; return 1; }

void gen(int n) { char d[11]; int one, i; /* one = 0 may be confusing. 'one' is the number of digit 1s */ for (one = 0; one <= 2 && one < n - 2; one++) { for (i = 0; i <= n; d[i++] = 0);

if ((d[0] = n - 2 - one) != 2) { d[2] = d[d[0] - 0] = 1; d[1] = 2; } else { d[1] = one ? 1 : 0; d[2] = 2; }

for (i = 0; i < n; d[i++] += '0'); if (self_desc(d)) printf("%s\n", d); } }

int main() { int i; char *nums[] = { "1210", "1337", "2020", "21200", "3211000", "42101000", 0};

for (i = 0; nums[i]; i++) printf("%s is %sself describing\n", nums[i], self_desc(nums[i]) ? "" : "not ");

printf("\nAll autobiograph numbers:\n"); for (i = 0; i < 11; i++) gen(i); return 0; }</lang>output<lang>1210 is self describing 1337 is not self describing 2020 is self describing 21200 is self describing 3211000 is self describing 42101000 is self describing

All autobiograph numbers: 2020 1210 21200 3211000 42101000 521001000 6210001000</lang>

Alternative version

Using integers instead of strings. <lang c>#include <stdio.h>

inline int self_desc(unsigned long long xx) { register unsigned int d, x; unsigned char cnt[10] = {0}, dig[10] = {0};

for (d = 0; xx > ~0U; xx /= 10) cnt[ dig[d++] = xx % 10 ]++;

for (x = xx; x; x /= 10) cnt[ dig[d++] = x % 10 ]++;

while(d-- && dig[x++] == cnt[d]);

return d == -1; }

int main() { int i; for (i = 1; i < 100000000; i++) /* don't handle 0 */ if (self_desc(i)) printf("%d\n", i);

return 0; }</lang>output<lang>1210 2020 21200 3211000 42101000</lang>

D

A functional version

Don't compile with -inline (DMD 2.053). <lang d>import std.stdio, std.algorithm, std.range, std.conv;

bool isSelfDescribing(in long n) { 

   auto nu = map!q{a - '0'}(text(n));
   auto f = map!(a => count(nu, a))(iota(walkLength(nu)));
   return equal(nu, f);

}

void main() { 

   writeln(filter!isSelfDescribing(iota(4_000_000)));

}</lang> Output: 

[1210, 2020, 21200, 3211000]

(About 5.2 seconds run time.)

A faster version

<lang d>import std.stdio;

bool isSelfDescribing2(long n) { 

 if (n <= 0)
   return false;

 __gshared static uint[10] digits, d;
 digits[] = 0;
 d[] = 0;
 int i;
 if (n < uint.max) {
   uint nu = cast(uint)n;
   for (i = 0; nu > 0 && i < digits.length; nu /= 10, i++) {
     d[i] = cast(ubyte)(nu % 10);
     digits[d[i]]++;
   }
   if (nu > 0)
     return false;
 } else {
   for (i = 0; n > 0 && i < digits.length; n /= 10, i++) {
     d[i] = cast(ubyte)(n % 10);
     digits[d[i]]++;
   }
   if (n > 0)
     return false;
 }

 foreach (k; 0 .. i)
   if (d[k] != digits[i - k - 1])
     return false;
 return true;

}

void main() { 

 foreach (x; [1210, 2020, 21200, 3211000,
              42101000, 521001000, 6210001000])
   assert(isSelfDescribing2(x));

 foreach (i; 0 .. 600_000_000)
   if (isSelfDescribing2(i))
     writeln(i);

}</lang> Output: 

1210
2020
21200
3211000
42101000
521001000

(About 0.5 seconds run time for 4 million tests.)

Forth

<lang forth>\ where unavailable.

third ( A b c -- A b c A ) >r over r> swap ;
(.) ( u -- c-addr u ) 0 <# #s #> ;

\ COUNT is a standard word with a very different meaning, so this \ would typically be beheaded, or given another name, or otherwise \ given a short lifespan, so to speak.

count ( c-addr1 u1 c -- c-addr1 u1 c+1 u )
 0 2over bounds do
   over i c@ = if 1+ then
 loop swap 1+ swap ;
self-descriptive? ( u -- f )
 (.) [char] 0 third third bounds ?do
   count i c@ [char] 0 - <> if drop 2drop false unloop exit then
 loop drop 2drop true ;</lang>

Go

<lang go>package main

import ( 

   "fmt"
   "strconv"
   "strings"

)

// task 1 requirement func sdn(n int64) bool { 

   if n >= 1e10 {
       return false
   }
   s := strconv.FormatInt(n, 10)
   for d, p := range s {
       if int(p)-'0' != strings.Count(s, strconv.Itoa(d)) {
           return false
       }
   }
   return true

}

// task 2 code (takes a while to run) func main() { 

   for n := int64(0); n < 1e10; n++ {
       if sdn(n) {
           fmt.Println(n)
       }
   }

}</lang> Output produced by above program: 

1210
2020
21200
3211000
42101000
521001000
6210001000

Haskell

<lang Haskell>import Data.Char

count :: Int -> [Int] -> Int count x = length . filter (x ==)

isSelfDescribing :: Integer -> Bool isSelfDescribing n = 

   nu == f where
           nu = map digitToInt (show n)
           f = map (\a -> count a nu) [0 .. ((length nu)-1)]

main = do 

   let tests = [1210, 2020, 21200, 3211000,
                42101000, 521001000, 6210001000]
   print $ map isSelfDescribing tests
   print $ filter isSelfDescribing [0 .. 4000000]</lang>

Output: 

[True,True,True,True,True,True,True]
[1210,2020,21200,3211000]

Here are functions for generating all the self-describing numbers of a certain length. We capitalize on the fact (from Wikipedia) that a self-describing number of length n is a base-n number (i.e. all digits are 0..n-1). <lang haskell>import Data.Char (intToDigit) import Control.Monad (replicateM, forM_)

count :: Int -> [Int] -> Int count x = length . filter (x ==)

-- all the combinations of n digits of base n -- a base-n number are represented as a list of ints, one per digit allBaseNNumsOfLength :: Int -> Int allBaseNNumsOfLength n = replicateM n [0..n-1]

isSelfDescribing :: [Int] -> Bool isSelfDescribing num = 

 all (\(i,x) -> x == count i num) $ zip [0..] num

-- translate it back into an integer in base-10 decimalize :: [Int] -> Int decimalize = read . map intToDigit

main = forM_ [1..7] $ 

 print . map decimalize . filter isSelfDescribing . allBaseNNumsOfLength</lang>

Icon and Unicon

The following program contains the procedure is_self_describing to test if a number is a self-describing number, and the procedure self_describing_numbers to generate them.

<lang Icon> procedure count (test_item, str) 

 result := 0
 every item := !str do 
   if test_item == item then result +:= 1
 return result

end

procedure is_self_describing (n) 

 ns := string (n) # convert to a string
 every i := 1 to *ns do {
   if count (string(i-1), ns) ~= ns[i] then fail
 }
 return 1 # success

end

  1. generator for creating self_describing_numbers

procedure self_describing_numbers () 

 n := 1
 repeat {
   if is_self_describing(n) then suspend n
   n +:= 1
 }

end

procedure main () 

 # write the first 4 self-describing numbers
 every write (self_describing_numbers ()\4)

end </lang> A slightly more concise solution can be derived from the above by taking more advantage of Icon's (and Unicon's) automatic goal-directed evaluation: <lang unicon> procedure is_self_describing (n) 

 ns := string (n) # convert to a string
 every i := 1 to *ns do {
     if count (string(i-1), ns) ~= ns[i] then fail
     }
 return n # on success, return the self-described number

end

procedure self_describing_numbers () 

 suspend is_self_describing(seq())

end</lang>

J

<lang j> NB. background material: 

  digits=: 10 #.inv ]
  digits 2020

2 0 2 0 

  (,~ i.@#@digits)2020

0 1 2 3 2020 

  (digits ,~ i.@#@digits)2020

0 1 2 3 2 0 2 0 

  (,~ i.@#)&digits 2020

0 1 2 3 2 0 2 0 

  _1 + #/.~@(,~ i.@#)&digits 2020

2 0 2 0

NB. task item 1: 

  (digits -: _1 + #/.~@(,~ i.@#)&digits) 2020

1 

  (digits -: _1 + #/.~@(,~ i.@#)&digits) 1210

1 

  (digits -: _1 + #/.~@(,~ i.@#)&digits) 21200

1 

  (digits -: _1 + #/.~@(,~ i.@#)&digits) 3211000

1 

  (digits -: _1 + #/.~@(,~ i.@#)&digits) 43101000

0 

  (digits -: _1 + #/.~@(,~ i.@#)&digits) 42101000

1

NB. task item 2: 

  I. (digits -: _1 + #/.~@(,~ i.@#)&digits)"0 i.1e6  NB. task item 2

1210 2020 21200</lang>

K

<lang k> sdn: {n~+/'n=/:!#n:0$'$x}' 

 sdn 1210 2020 2121 21200 3211000 42101000

1 1 0 1 1 1 

 &sdn@!:1e6

1210 2020 21200</lang>

<lang logo>TO XX BT MAKE "AA (ARRAY 10 0) MAKE "BB (ARRAY 10 0) FOR [Z 0 9][SETITEM :Z :AA "0 SETITEM :Z :BB "0 ] 

  FOR [A 1 50000][
     MAKE "B COUNT :A
     MAKE "Y 0
     MAKE "X 0
     MAKE "R 0
     MAKE "J 0
     MAKE "K 0

  FOR [C 1 :B][MAKE "D ITEM :C :A
     SETITEM :C - 1 :AA :D 
     MAKE "X ITEM :D :BB 
     MAKE "Y :X + 1 
     SETITEM :D :BB :Y 
     MAKE "R 0]
  FOR [Z 0 9][MAKE "J ITEM :Z :AA 
     MAKE "K ITEM :Z :BB
     IF :J = :K [MAKE "R :R + 1]]

IF :R = 10 [PR :A] FOR [Z 0 9][SETITEM :Z :AA "0 SETITEM :Z :BB "0 ]] PR [END] END</lang>

Lua

<lang lua>function Is_self_describing( n ) 

   local s = tostring( n )

   local t = {}
   for i = 0, 9 do t[i] = 0 end

   for i = 1, s:len() do

local idx = tonumber( s:sub(i,i) ) 

       t[idx] = t[idx] + 1
   end

   for i = 1, s:len() do
       if t[i-1] ~= tonumber( s:sub(i,i) ) then return false end
   end

   return true

end

for i = 1, 999999999 do 

   print( Is_self_describing( i ) )

end</lang>

Pascal

<lang pascal>Program SelfDescribingNumber;

uses 

 SysUtils;

function check(number: longint): boolean; 

 var
   i, d: integer;
   a: string;
   count, w : array [0..9] of integer;

 begin
   a := intToStr(number);
   for i := 0 to 9 do
   begin
     count[i] := 0;
     w[i] := 0;
   end;
   for i := 1 to length(a) do
   begin
     d := ord(a[i]) - ord('0');
     inc(count[d]);
     w[i - 1] := d;
   end;
   check := true;
   i := 0;
   while check and (i <= 9) do
   begin
     check := count[i] = w[i];
     inc(i);
   end;
 end;

var 

 x: longint;

begin 

 writeln ('Autodescriptive numbers from 1 to 100000000:');
 for x := 1 to 100000000 do
   if check(x) then
     writeln (' ', x);
 writeln('Job done.');

end.</lang> Output: 

:> ./SelfDescribingNumber
Autodescriptive numbers from 1 to 100000000:
 1210
 2020
 21200
 3211000
 42101000
Job done.

Perl 6

<lang perl6>my @values = <1210 2020 21200 3211000 42101000 521001000 6210001000 27 115508>;

for @values -> $test { 

   say "$test is {$test.&sdn ??  !! 'NOT ' }a self describing number.";

}

sub sdn ($num) { 

   my @digits;
   my $chars = $num.chars;
   @digits[$_]++ for $num.comb;
   return 0 if @digits.elems > $chars;
   @digits[$_] //= '0' for ^$chars;
   my $string =  join , @digits;
   return 1 if $num eq $string;

}

say $_ if $_.&sdn for ^9999999;</lang> Output: 

1210 is a self describing number.
2020 is a self describing number.
21200 is a self describing number.
3211000 is a self describing number.
42101000 is a self describing number.
521001000 is a self describing number.
6210001000 is a self describing number.
27 is NOT a self describing number.
115508 is NOT a self describing number.
1210
2020
21200
3211000

PicoLisp

<lang PicoLisp>(de selfDescribing (N) 

  (not
     (find '((D I) (<> D (cnt = N (circ I))))
        (setq N (mapcar format (chop N)))
        (range 0 (length N)) ) ) )</lang>

Output: 

: (filter selfDescribing (range 1 4000000))
-> (1210 2020 21200 3211000)

Prolog

Works with SWI-Prolog and library clpfd written by Markus Triska. <lang Prolog>:- use_module(library(clpfd)).

self_describling :- forall(between(1, 10, I), (findall(N, self_describling(I,N), L), format('Len ~w, Numbers ~w~n', [I, L]))).

% search of the self_describling numbers of a given len self_describling(Len, N) :- length(L, Len), Len1 is Len - 1, L = [H|T],

% the first figure is greater than 0 H in 1..Len1,

% there is a least to figures so the number of these figures % is at most Len - 2 Len2 is Len - 2, T ins 0..Len2,

% the sum of the figures is equal to the len of the number sum(L, #=, Len),

% There is at least one figure corresponding to the number of zeros H1 #= H+1, element(H1, L, V), V #> 0,

% create the list label(L),

% test the list msort(L, LNS), packList(LNS,LNP), numlist(0, Len1, NumList), verif(LNP,NumList, L),

% list is OK, create the number maplist(atom_number, LA, L), number_chars(N, LA).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % testing a number (not use in this program) self_describling(N) :- number_chars(N, L), maplist(atom_number, L, LN), msort(LN, LNS), packList(LNS,LNP), !, length(L, Len), Len1 is Len - 1, numlist(0, Len1, NumList), verif(LNP,NumList, LN).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % verif(PackList, Order_of_Numeral, Numeral_of_the_nuber_to_test) % Packlist is of the form [[Number_of_Numeral, Order_of_Numeral]|_] % Test succeed when

% All lists are empty verif([], [], []).

% Packlist is empty and all lasting numerals are 0 verif([], [_N|S], [0|T]) :- verif([], S, T).

% Number of numerals N is V verif([[V, N]|R], [N|S], [V|T]) :- verif(R, S, T).

% Number of numerals N is 0 verif([[V, N1]|R], [N|S], [0|T]) :- N #< N1, verif([[V,N1]|R], S, T).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % ?- packList([a,a,a,b,c,c,c,d,d,e], L). % L = [[3,a],[1,b],[3,c],[2,d],[1,e]] . % ?- packList(R, [[3,a],[1,b],[3,c],[2,d],[1,e]]). % R = [a,a,a,b,c,c,c,d,d,e] . % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% packList([],[]).

packList([X],1,X) :- !.


packList([X|Rest],[XRun|Packed]):- 

   run(X,Rest, XRun,RRest),
   packList(RRest,Packed).


run(Var,[],[1, Var],[]).

run(Var,[Var|LRest],[N1, Var],RRest):- 

   N #> 0,
   N1 #= N + 1,
   run(Var,LRest,[N, Var],RRest).


run(Var,[Other|RRest], [1, Var],[Other|RRest]):- 

   dif(Var,Other).</lang>

Output 

 ?- self_describling.
Len 1, Numbers []
Len 2, Numbers []
Len 3, Numbers []
Len 4, Numbers [1210,2020]
Len 5, Numbers [21200]
Len 6, Numbers []
Len 7, Numbers [3211000]
Len 8, Numbers [42101000]
Len 9, Numbers [521001000]
Len 10, Numbers [6210001000]
true.

PureBasic

<lang PureBasic>Procedure isSelfDescribing(x.q) 

 ;returns 1 if number is self-describing, otherwise it returns 0
 Protected digitCount, digit, i, digitSum
 Dim digitTally(10)
 Dim digitprediction(10)
 
 If x <= 0
   ProcedureReturn 0 ;number must be positive and non-zero
 EndIf 
 
 While x > 0 And i < 10
   digit = x % 10
   digitSum + digit
   If digitSum > 10
     ProcedureReturn 0 ;sum of digits' values exceeds maximum possible
   EndIf 
   digitprediction(i) = digit 
   digitTally(digit) + 1
   x / 10
   i + 1 
 Wend 
 digitCount = i - 1
 
 If digitSum < digitCount Or x > 0
   ProcedureReturn 0  ;sum of digits' values is too small or number has more than 10 digits
 EndIf 
 
 For i = 0 To digitCount
   If digitTally(i) <> digitprediction(digitCount - i)
     ProcedureReturn 0 ;number is not self-describing
   EndIf
 Next
 ProcedureReturn 1 ;number is self-describing

EndProcedure

Procedure displayAll() 

 Protected i, j, t
 PrintN("Starting search for all self-describing numbers..." + #CRLF$)
 For j = 0 To 9
   PrintN(#CRLF$ + "Searching possibilites " + Str(j * 1000000000) + " -> " + Str((j + 1) * 1000000000 - 1)+ "...")
   t = ElapsedMilliseconds()
   For i = 0 To 999999999
     If isSelfDescribing(j * 1000000000 + i)
       PrintN(Str(j * 1000000000 + i))
     EndIf 
   Next
   PrintN("Time to search this range of possibilities: " + Str((ElapsedMilliseconds() - t) / 1000) + "s.")
 Next 
 PrintN(#CRLF$ + "Search complete.")

EndProcedure

If OpenConsole() 

 DataSection
   Data.q 1210, 2020, 21200, 3211000, 42101000, 521001000, 6210001000, 3214314
 EndDataSection
 
 Define i, x.q
 For i = 1 To 8
   Read.q x
   Print(Str(x) + " is ")
   If Not isSelfDescribing(x)
     Print("not ")
   EndIf
   PrintN("selfdescribing.")
 Next 
 PrintN(#CRLF$)
 
 displayAll()
 
 Print(#CRLF$ + #CRLF$ + "Press ENTER to exit"): Input()
 CloseConsole()

EndIf</lang> Sample output: 

1210 is selfdescribing.
2020 is selfdescribing.
21200 is selfdescribing.
3211000 is selfdescribing.
42101000 is selfdescribing.
521001000 is selfdescribing.
6210001000 is selfdescribing.
3214314 is not selfdescribing.


Starting search for all self-describing numbers...


Searching possibilites 0 -> 999999999...
1210
2020
21200
3211000
42101000
521001000
Time to search this range of possibilities: 615s.

Searching possibilites 1000000000 -> 1999999999...
Time to search this range of possibilities: 614s.

Searching possibilites 2000000000 -> 2999999999...
Time to search this range of possibilities: 628s.

Searching possibilites 3000000000 -> 3999999999...
Time to search this range of possibilities: 631s.

Searching possibilites 4000000000 -> 4999999999...
Time to search this range of possibilities: 630s.

Searching possibilites 5000000000 -> 5999999999...
Time to search this range of possibilities: 628s.

Searching possibilites 6000000000 -> 6999999999...
6210001000
Time to search this range of possibilities: 629s.

Searching possibilites 7000000000 -> 7999999999...
Time to search this range of possibilities: 631s.

Searching possibilites 8000000000 -> 8999999999...
Time to search this range of possibilities: 629s.

Searching possibilites 9000000000 -> 9999999999...
Time to search this range of possibilities: 629s.

Search complete.

Python

<lang python>>>> def isSelfDescribing(n): s = str(n) return all(s.count(str(i)) == int(ch) for i, ch in enumerate(s))

>>> [x for x in range(4000000) if isSelfDescribing(x)] [1210, 2020, 21200, 3211000] >>> [(x, isSelfDescribing(x)) for x in (1210, 2020, 21200, 3211000, 42101000, 521001000, 6210001000)] [(1210, True), (2020, True), (21200, True), (3211000, True), (42101000, True), (521001000, True), (6210001000, True)]</lang>

Generator

From here. <lang python>def impl(d, c, m): 

   if m < 0: return
   if d == c[:len(d)]: print d
   for i in range(c[len(d)],m+1):
       dd = d+[i]
       if i<len(dd) and c[i]==dd[i]: continue
       impl(dd,c[:i]+[c[i]+1]+c[i+1:],m-i)

def self(n): impl([], [0]*(n+1), n)

self(10)</lang> Output: 

[]
[1, 2, 1, 0]
[2, 0, 2, 0]
[2, 1, 2, 0, 0]
[3, 2, 1, 1, 0, 0, 0]
[4, 2, 1, 0, 1, 0, 0, 0]
[5, 2, 1, 0, 0, 1, 0, 0, 0]
[6, 2, 1, 0, 0, 0, 1, 0, 0, 0]

Ruby

<lang ruby>def is_self_describing?(n) 

 digits = n.to_s.chars.collect {|digit| digit.to_i}
 len = digits.length
 count = Array.new(len, 0)

 digits.each do |digit| 
   return false if digit >= len
   count[digit] = count[digit] + 1
 end

 digits.eql?(count)

end

3_300_000.times {|n| puts n if is_self_describing?(n)}</lang> outputs 

1210
2020
21200
3211000

Tcl

<lang tcl>package require Tcl 8.5 proc isSelfDescribing num { 

   set digits [split $num ""]
   set len [llength $digits]
   set count [lrepeat $len 0]
   foreach d $digits {

if {$d >= $len} {return false} lset count $d [expr {[lindex $count $d] + 1}] 

   }
   foreach d $digits c $count {if {$c != $d} {return false}}
   return true

}

for {set i 0} {$i < 100000000} {incr i} { 

   if {[isSelfDescribing $i]} {puts $i}

}</lang>

Retrieved from "https://rosettacode.org/wiki/Self-describing_numbers?oldid=179864"