O desafio é simples: escreva um programa ou função que, quando recebe um número inteiro finito não negativo, gera uma matriz aninhada.

As regras

• Seu código deve produzir uma matriz aninhada válida e exclusiva para cada número inteiro 0 ‌≤ n ‌ <2 ³¹ .
• Cada matriz aninhada possível com até 16 colchetes abertos deve ser gerada dentro desse intervalo. (Isso não significa que seu código nunca pode gerar uma matriz aninhada com mais de 16 colchetes abertos.)
• Seu código pode gerar uma representação de seqüência de caracteres da matriz aninhada em vez de uma matriz real (com ou sem vírgulas).

Um mapeamento possível:

0 -> []
1 -> [[]]
2 -> [[[]]]
3 -> [[], []]
4 -> [[[[]]]]
5 -> [[[], []]]
6 -> [[[]], []]
7 -> [[], [[]]]
8 -> [[], [], []]
9 -> [[[[[]]]]]
etc.

Pontuação

Isso é código-golfe , então o código mais curto em bytes vence.

Python 2.7, 172 149 124 118 bytes

x=input();y="";z=0
for b in bin(x)[2+(x<1):]:y+="[]"[b<"1"];z+=b>"0"or-1;z+=99*(z<0)
print"["+(y,"[]"*(x+16))[z>0]+"]"

Explicação:

Defina uma bijeção por [↔ 1e ]↔ 0. Qualquer arranjo de suportes pode, então, ser representado por um número binário e vice-versa, por exemplo [][]↔ 1010(10) e [[][]]↔ 110100(52). Todas as disposições válidas de até 15 colchetes abertos (30 colchetes no total) são cobertas por números com até 30 bits (ignorando zeros à esquerda), que são precisamente os números menores que 2 ³¹ .

O primeiro loop for fornece o inverso dessa bijeção, convertendo um número em um arranjo de colchetes, enquanto verifica se o arranjo é válido.

Arranjos inválidos são substituídos na declaração de impressão por longas sequências de colchetes para evitar colisões. Por exemplo 11(3) ↔ [[não é válido, portanto concatenamos 3 + 16 colchetes. Isso garante que todos os arranjos sejam únicos.

O arranjo resultante é colocado dentro de um par de colchetes para formar uma matriz aninhada, de modo que 1010(10) se torne [[][]]e 110100(52) se torne[[[][]]] . O suporte extra aberto significa que agora cobrimos todas as matrizes com 16 colchetes abertos.

O programa a seguir pode ser usado para descobrir o número de um determinado array com até 16 colchetes.

s=raw_input();o="";
for c in s[1:-1]:
 if c=="[":o+="1"
 if c=="]":o+="0"
print int(o,2)

Python, 153 128 bytes

s=l=0;r="";n=input()
for d in bin(n)[2:]*(n>0):c=d<"1";l=[l,s>1][c];r+="]"*c+(1-l*c)*"[";s+=1-c-l*c
print"["+r+"["*l+"]"*(s+l+1)

Mapeamos um número n para uma lista aninhada, observando seus dígitos binários da esquerda para a direita. Esse algoritmo funciona para qualquer número, não para menos de 2 ³² .

1. Se o dígito binário atual for 1, faça a saída [.
2. Caso contrário, se a sequência de colchetes que produzimos até agora for equilibrada por um único colchete de fechamento, a saída ][.
3. Caso contrário, se este for o último 0 no número binário, a saída ][ .
4. Caso contrário, saída ].

Finalmente, fechamos todos os colchetes abertos.

Colher , 63 bytes (501 bits)

000001001001001011001101001010011011111001010001000000101010
101101100110100101101001000101100010001000000100011000010000
000000000000001110111110010000001110110110010100100100100100
000110011010001000000110110000010000001010110011011011011001
000000011010010010010001000000111011011011101001001001000110
110110010100100101011001000100000011010001000000111011011001
010010010010010001101101101001000110110010110001101101101101
100100010001010010001010011011001000000011001101001001010010
000001100101001000111

Este é o seguinte programa de conversão cerebral convertido em colher:

-[+[+<]>>+]<+++.[->+>+<<]>>++>>,[>-[<->-----]+<+++[-<+<<.>>>>-<]>[-<<-[->+<]<<<[-]>>>>[-<+<<<+>>>>]<<.>>+<[>-]>[-<+<<.>>>>]<<>>]<,]<<<<[>.>.<<[-]]>>>+[-<.>]+

Lê um número inteiro em binário no stdin e gera a lista aninhada no stdin. Requer que 0 seja inserido como uma sequência vazia (sem dígitos) e requer um intérprete de cérebro com células de 8 bits. Mesmo algoritmo que minha resposta em Python.

Versão legível:

-[+[+<]>>+]<+++.           push open bracket and print it
[->+>+<<]                  dup
>>++                       increment to close bracket

>>,[                       read input loop
    >-[<->-----]+<+++          subtract 48 and set up if/else
    [-                         if c == 1
        <+                         increment s
        <<.>>>                     output open bracket
    >-<]>[-<                   else
        <-[->+<]                   decrement and move s
        <<<[-]                     zero l
        >>>>[-<+<<<+>>>>]          l = s and restore s
        <<.>                       output close bracket
        >+<[>-]>[-                 if s == 0
            <+                         undo s decrement
            <<.                        output open bracket
        >>>>]<<
    >>]<
,]

<<<<[                      if l
    >.>.                   output pair
<<[-]]
>>>+[-<.>]                 output close bracket s+1 times

Gelatina , 28 bytes

ḃ2-*µSN;+\>-Ạ
1Ç#Ṫḃ2ṭ2;1ị⁾][

Este itera sobre todas as cadeias de caracteres [e ]que começam com um [e terminam com um ], verifica se os suportes de corresponder, e imprime o n ^º jogo.

Experimente online!

Perl, 80 79 bytes

Novamente usa orlp o algoritmo do , mas desta vez verifiquei primeiro se ele funciona ...

Inclui +1 para -p

Forneça o número de entrada no STDIN

nest.pl <<< 8

nest.pl:

#!/usr/bin/perl -p
($_=sprintf"%b",$_).=2x(s^.^$&or++$n-pos&&/.0/g?++$n%1:$`&&21^eg-$n);y;102;();

A solução de Linus é de 64 bytes em perl:

#!/usr/bin/perl -p
$_=sprintf"%b",/.+/g;$_=10x($&&&$&+16)if!/^(1(?1)*0)+$/;y;10;()

A solução de Dennis é de 59 bytes em perl (cada vez mais lenta para grandes números):

#!/usr/bin/perl -p
1while$_-=(sprintf"%b",$n++)=~/^(1(?1)*0)+$/;$_=$&;y;10;()

Python 3, 120 114 bytes

def f(n,k=0):
 while~n:
  k+=1
  try:r=eval(bin(k).translate({48:'],',49:'['})[3:-1])+[];n-=1
  except:0
 print(r)

Test it on Ideone.

How it works

The defined function f takes input n and initializes k to 0. We'll keep incrementing k until n + 1 values of k result in a valid output. Every time we find such a value of k, n is decremented once it reaches -1, ~n yields 0, and the list r that corresponds to the last value of k is printed.

The partial mapping from the positive integers to nested lists (i.e., k ↦ r) has to be bijective, but there are no other constraints. The one used in this answer operates as follows.

1. Convert k to a binary string representation, staring with 0b.

   For example, 44 ↦ "0b101100".

2. Replace all 0's (code point 48) in the string representation with the string "]," and all 1's (code point 49) with [.

   For example, "0b101100" ↦ "],b[],[[],],".

3. Remove the first three characters (they correspond to "0b") and the trailing character (hopefully a comma).

   For example, "],b[],[[],]," ↦ "[],[[],]".

4. Try evaluating the generated code. If this results in an error, k isn't mapped to any list.

   For example, "[],[[],]" ↦ ([], [[]]).

5. Concatenate the result (if any) with the empty list. If this results in an error, k isn't mapped to any list.

   For example, ([], [[]]) + [] errors since + cannot concatenate lists and tuples.

Haskell, 71 bytes

p 1=["[]"]
p n=['[':h++t|k<-[1..n-1],h<-p k,_:t<-p$n-k]
((p=<<[1..])!!)

The main function on the last line indexes into a list of all nested arrays, sorted by size (number of open brackets). So, all the arrays of size at most 16 are listed first.

Let's first look at code that's nicer and shorter, but Haskell's typechecker refuses to accept.

p 1=[[]]
p n=[h:t|k<-[1..n-1],h<-p k,t<-p$n-k]
((p=<<[1..])!!)

The function p on input n gives a list of all nested arrays of size n (open brackets). This is done recursively. Each such array consists of some head h (first member) of size k and some tail t (other members) of size n-k, both sizes nonzero. Or, it's the empty array for size n==1.

The expression p=<<[1..] then flattens p(1), p(2), ... into a single infinite list of all arrays sorted by size

[ [], [[]], [[],[]], [[[]]], [[],[],[]], [[],[[]]], [[[]],[]], [[[],[]]], ...

and the main function indexes into it.

... Or, it would, if Haskell didn't whine about "construct[ing] the infinite type: t ~ [t]". Haskell cannot represent the infinite list above whose elements are arbitrarily nested arrays. All its elements must have the same type, but a type t cannot be the same as a list of t's. In fact, the function p itself cannot be assigned a consistent type without dependent typing, which Haskell lacks.

So, instead we work on strings of brackets, simulating the cons operation by acting on [ and ] characters. This takes an extra 9 bytes. The perils of golfing in a type-safe language.

Haskell, 87 82 bytes

0#0=[""]
n#m=['[':x|n>0,x<-(n-1)#m]++[']':x|n<m,x<-n#(m-1)]
(([0..]>>= \y->y#y)!!)

Outputs the array elements. Usage example: (([0..]>>= \y->y#y)!!) 3 -> "[][]".

Function # builds all nested arrays as strings for n open and m close brackets, by keeping track of how many of each are left over. Always starts with n == m. The main function calls y # y for every y <- [0,1,...] and picks the element at the index given by the input.

MATL, 31 bytes

O`@BEqXJYs0&)0>w~hA+tG>~]x92J-c

Try it online! Or verify the first few test cases (takes a few seconds).

The produced mapping is:

0 -> []
1 -> [[]]
2 -> [[][]]
3 -> [[[]]]
4 -> [[][][]]
5 -> [[][[]]]
6 -> [[[]][]]
7 -> [[[][]]]
...

Explanation

The code keeps testing increasing binary numbers, with digit 0 replaced by -1; that is, using 1 and -1 as digits. Digit 1 will represent '[' and -1 will represent ']'.

The program counts until n+1 valid numbers have been obtained. A number is valid if the following two conditions hold:

1. The sum of digits is zero (that is, there is an equal number of 1 and -1)
2. The cumulative sum of digits is always positive (that is, the accumulated number of 1 digits always exceeds that of -1) except at the end (where it is zero by condition 1).

Once n+1 valid numbers have been obtained, the last one is transliterated by changing 1 into [ and -1 into ], and then it is displayed.

Code:

O          % Push 0: initial count of valid numbers
`          % Do...while
  @        %   Push iteretation index k, starting at 1
  B        %   Convert to binary. For example, k=6 gives [1 1 0 0]
  Eq       %   Multiply by 2, subtract 1: transforms [1 1 0 0] into [1 1 -1 -1]
  XJ       %   Copy that to clipboard J, without popping it
  Ys       %   Cumulative sum: gives [1 2 1 0]
  0&)      %   Split array into its final element and the rest. Gives 0, [1 2 1]
  0>       %   Yields 1 for positive entries (condition 2). So in this case it
           %   gives [1 1 1]
  w        %   Swap: moves second-top element in the stack (0 in this case) to top
  ~        %   Negate: yields 1 if input is 0 (condition 1). Gives 1 in this case
  h        %   Concatenate horizontally. Gives [1 1 1 1]
  A        %   All: gives 1 if all elements are 1. Gives 1 in this case, meaning
           %   that this k is valid
  +        %   Add the result (0 or 1) to the count of valid numbers
  t        %   Duplicate
  G        %   Push input n
  >~       %   Loop condition: false (exit loop) if count exceeds input n
]          % End loop. At this point the result is in clipboard J, in 1/-1 format
x          % Delete count
92         % Push 92. Will be used to convert 1, -1 to '[', ']' (ASCII 91, 93)
J          % Push result in 1/-1 format
-          % Subtract: converts 1 to 91, -1 to 93
c          % Convert to char. Implicitly display