Rozważ proces „wybierania” zagnieżdżonej listy. Wybór jest definiowany następująco:
- Jeśli argumentem jest lista, weź element z listy losowo (jednolicie) i wybierz z niego.
- Jeśli argumentem nie jest lista, po prostu ją zwróć.
Przykładowa implementacja w Pythonie:
import random
def pick(obj):
if isinstance(obj, list):
return pick(random.choice(obj))
else:
return obj
Dla uproszczenia zakładamy, że listy zagnieżdżone zawierają tylko liczby całkowite lub dalsze listy zagnieżdżone.
Na dowolnej liście można utworzyć spłaszczoną wersję, której nie można odróżnić pick
, tzn. Wybranie z niej daje te same wyniki z takim samym prawdopodobieństwem.
Na przykład „spłaszczanie” listy
[1, 2, [3, 4, 5]]
daje listę
[1, 1, 1, 2, 2, 2, 3, 4, 5]
. Powodem, dla którego po prostu spłaszczanie jest nieprawidłowe, jest to, że elementy list podrzędnych mają mniejsze prawdopodobieństwo wyboru, np. Na liście[1, [2, 3]]
1 ma szansę wyboru 2/4 = 1/2, podczas gdy 3 i 4 mają 1/4 przypadek każdy.
Zauważ również, że wybieranie z listy singletonów jest równoważne z wybieraniem z jego elementu i że wybieranie z pustej listy nie ma znaczenia.
Wyzwanie
Biorąc pod uwagę zagnieżdżoną listę nieujemnych liczb całkowitych, zwróć spłaszczoną listę nieujemnych liczb całkowitych, z których wybranie daje te same wyniki z takim samym prawdopodobieństwem.
To jest golf golfowy , więc wygrywa najkrótsza ważna odpowiedź (mierzona w bajtach).
Dane techniczne
- Wejścia
[2, 3, 4]
,[2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4]
i[2, [3, 3], [[4]]]
są równoważne (tj powinni dać równoważne wyniki). - Wyjścia
[2, 2, 2, 2, 3, 3, 3, 3]
i[2, 3]
są równoważne (tzn. Jedno z nich może być wyjściem). - Możesz założyć, że na listach będą znajdować się tylko liczby z przedziału 1-100.
- Możesz założyć, że wejściem najwyższego poziomu będzie lista, tzn. Że
2
nie jest to poprawne wejście. - Można użyć dowolnego rozsądną reprezentację zagnieżdżonych listach, na przykład:
[1, [2, 3]]
,1 {2 3}
,"[ 1 [ 2 3 ] ]"
, itd. - Zamiast listy można wyprowadzić multiset lub mapowanie, lub, ponieważ dozwolone są tylko liczby z zakresu 1-100, listę liczb całkowitych o długości 100 reprezentujących ilości.
Przypadki testowe
Zauważ, że wymienione dane wyjściowe są tylko jedną poprawną możliwością; zobacz specyfikację tego, co stanowi prawidłowy wkład lub wynik.
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]
źródło
Odpowiedzi:
Wolfram Language (Mathematica) ,
4120 bajtówWypróbuj online! Zignoruj wiele ostrzeżeń, wszystko się ostatecznie kończy.
Jak to działa
W przypadku listy o głębokości 2, takiej jak
{{1,2},{3},{4,5,6}}
,Tuples
wygenerowana zostanie lista{{1,3,4},{1,3,5},{1,3,6},{2,3,4},{2,3,5},{2,3,6}}
odpowiadająca wszystkim sposobom pobrania elementu{1,2}
i pobrania elementu{3}
oraz pobrania elementu z{4,5,6}
.Jeśli mamy
Flatten
to, to możemy uzyskać wszystkie elementy z odpowiednich częstotliwości, ponieważ zbieranie element z jednego dnia{1,2}
,{3}
czy{4,5,6}
jest równoważne zbieranie element z wszystkich z nich, a następnie wybiera, który z nich zachować.Używamy tego,
//@
aby zastosować to na wszystkich poziomach danych wejściowych. W tym czasie Mathematica bardzo narzeka, ponieważ zamienia atomy takie jak17
wTuples[17]
, co tak naprawdę nie powinno być niczym. Ale upraszczają one później właściwy wynik (zTuples
przyjemnością traktujeTuples[17]
jako listę długości 1, nawet jeśli ma głowę inną niżList
), więc narzekanie jest bez znaczenia.źródło
Python 2 ,
10510299 bajtówWypróbuj online!
źródło
Galaretka ,
98 bajtówWypróbuj online!
Jak to działa
źródło
Galaretka , 10 bajtów
Wypróbuj online!
źródło
Python 2 , 128 bajtów
Wypróbuj online!
Port mojej galaretki odpowiedzi.
-12 dzięki Jonathan Frech .
źródło
type(i)==int
może byći*0<[]
.0<[]
... itype(i)==list
może byći*0>0
;)C (gcc) ,
234223 bajtyWypróbuj online!
Wyjaśnienie:
źródło
Python 2 ,
144139 bajtówWypróbuj online!
źródło
JavaScript (ES6),
132131 bajtówPokaż fragment kodu
źródło