Considere o processo de "escolher" uma lista aninhada. A escolha é definida da seguinte forma:
- Se o argumento for uma lista, pegue um elemento da lista aleatoriamente (uniformemente) e escolha uma opção.
- Se o argumento não for uma lista, basta devolvê-lo.
Um exemplo de implementação em Python:
import random
def pick(obj):
if isinstance(obj, list):
return pick(random.choice(obj))
else:
return obj
Para simplificar, assumimos que as listas aninhadas contêm apenas números inteiros ou outras listas aninhadas.
Dada qualquer lista, é possível criar uma versão achatada que é indistinguível por pick
, ou seja, escolher nela produz os mesmos resultados, com a mesma probabilidade.
Por exemplo, "achatar" a lista
[1, 2, [3, 4, 5]]
produz a lista
[1, 1, 1, 2, 2, 2, 3, 4, 5]
. O motivo pelo qual o achatamento é inválido é porque os elementos das sub-listas têm uma probabilidade menor de serem escolhidos; por exemplo, na lista, [1, [2, 3]]
o 1 tem uma chance de 2/4 = 1/2 de ser escolhido, enquanto 3 e 4 têm 1/4 chance cada.
Observe também que escolher em uma lista de singleton é equivalente a escolher em seu elemento e que escolher em uma lista vazia não tem significado.
O desafio
Dada uma lista aninhada de números inteiros não negativos, retorne uma lista achatada de números inteiros não negativos, a partir da qual a seleção produz os mesmos resultados com a mesma probabilidade.
Isso é código-golfe , então a resposta mais curta e válida (medida em bytes) vence.
Especificações
- As entradas
[2, 3, 4]
,[2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4]
e[2, [3, 3], [[4]]]
são equivalentes (ou seja, eles deveriam dar resultados equivalentes). - As saídas
[2, 2, 2, 2, 3, 3, 3, 3]
e[2, 3]
são equivalentes (ou seja, qualquer uma pode ser saída). - Você pode presumir que apenas números no intervalo inclusivo de 1 a 100 estarão presentes nas listas.
- Você pode assumir que a entrada de nível superior será uma lista, ou
2
seja, não é uma entrada válida. - Você pode usar qualquer representação razoável de listas aninhadas, por exemplo:
[1, [2, 3]]
,1 {2 3}
,"[ 1 [ 2 3 ] ]"
, etc. - Em vez de uma lista, você pode produzir um multiset ou um mapeamento ou, uma vez que apenas números no intervalo de 1 a 100 são permitidos, uma lista de 100 números inteiros representando quantidades.
Casos de teste
Observe que as saídas listadas são apenas uma possibilidade válida; consulte as especificações sobre o que constitui uma entrada ou saída válida.
format:
input -> output
[3] -> [3]
[1, [1, 1]] -> [1]
[1, [2, 3]] -> [1, 1, 2, 3]
[2, 3, [4, [5, 5, 6], 6, 7]] -> [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 5, 5, 6, 6, 6, 6, 7, 7, 7]
[[1, 1, 2], [2, 3, 3]] -> [1, 2, 3]
[[1, 1, 2], [2, 3, 3, 3]] -> [1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3]
fonte
Respostas:
Wolfram Language (Mathematica) ,
4120 bytesExperimente online! Ignore os muitos avisos, tudo funciona no final.
Como funciona
Para uma lista de profundidade 2, tais como
{{1,2},{3},{4,5,6}}
,Tuples
irá gerar a lista{{1,3,4},{1,3,5},{1,3,6},{2,3,4},{2,3,5},{2,3,6}}
correspondente de todas as maneiras para escolher um elemento de{1,2}
e escolher um elemento de{3}
e escolher um elemento de{4,5,6}
.Se
Flatten
isso, então temos todos os elementos com as frequências corretas, porque escolher um elemento de um dos{1,2}
,{3}
ou{4,5,6}
é equivalente a escolher um elemento de todos eles, em seguida, escolher um deles para manter.Usamos
//@
para aplicar isso em todos os níveis da entrada. No processo, Mathematica reclama muito, porque ele está girando átomos, como17
noTuples[17]
, o que realmente não é suposto ser uma coisa. Mas isso simplifica para o resultado certo mais tarde (Tuples
é um prazer tratá-loTuples[17]
como uma lista de comprimento 1, mesmo que tenha uma cabeça diferenteList
), portanto a reclamação é irrelevante.fonte
Python 2 ,
10510299 bytesExperimente online!
fonte
Geléia ,
98 bytesExperimente online!
Como funciona
fonte
Gelatina , 10 bytes
Experimente online!
fonte
Python 2 , 128 bytes
Experimente online!
Porto da minha resposta Jelly.
-12 agradecimentos a Jonathan Frech .
fonte
type(i)==int
pode seri*0<[]
.0<[]
... etype(i)==list
pode seri*0>0
;)C (GCC) ,
234223 bytesExperimente online!
Explicação:
fonte
Python 2 ,
144139 bytesExperimente online!
fonte
JavaScript (ES6),
132131 bytesMostrar snippet de código
fonte