Czytałem Flatten (an irregular) list of lists i zdecydowałem się przyjąć go jako ćwiczenie Python - małą funkcję, którą będę czasem przepisywać bez odwoływania się do oryginału, tylko po to, aby ćwiczyć. Po raz pierwszy próbowałem to miałem coś jak następuje:Jak określić, czy kontener jest nieskończenie rekurencyjny i czy znajduje najmniejszy unikalny kontener?
def flat(iterable):
try:
iter(iterable)
except TypeError:
yield iterable
else:
for item in iterable:
yield from flatten(item)
Działa to dobrze dla podstawowych struktur jak zagnieżdżonych list s zawierających cyfry, ale struny katastrofy, ponieważ pierwszym elementem łańcucha jest pojedynczym znaków ciąg, którego pierwszym elementem jest sam, którego pierwszy element jest ponownie, i tak dalej. Sprawdzając powyższe pytanie, zdałem sobie sprawę, że to wyjaśnia sprawdzanie ciągów. To dało mi następujące:
def flatter(iterable):
try:
iter(iterable)
if isinstance(iterable, str):
raise TypeError
except TypeError:
yield iterable
else:
for item in iterable:
yield from flatten(item)
Teraz działa również na strunach. Jednak przypomniałem sobie, że list może zawierać odniesienia do siebie.
>>> lst = []
>>> lst.append(lst)
>>> lst
[[...]]
>>> lst[0][0][0][0] is lst
True
Tak więc łańcuch nie jest jedynym rodzajem, który może powodować tego rodzaju problemy. W tym momencie zacząłem szukać sposobu na zabezpieczenie się przed tym problemem bez wyraźnego sprawdzania typu.
Nastąpił następujący . flattish() to wersja, która sprawdza tylko ciągi. flatten_notype() sprawdza, czy pierwszy element obiektu pierwszego przedmiotu jest równy samemu sobie w celu określenia rekursji. flatten() robi to, a następnie sprawdza, czy pierwszy obiekt lub pierwszy element tego elementu jest instancją typu drugiego. Klasa Fake po prostu definiuje opakowanie dla sekwencji. Komentarze na liniach testujących każdą funkcję opisują wyniki w postaci should be `desired_result` [> `undesired_actual_result`]. Jak widać, każda z nich kończy się na różne sposoby Fake owiniętym wokół sznurka, Fake owiniętym wokół list liczb całkowitych, ciągów jednoznakowych i ciągów zawierających wiele znaków.
def flattish(*i):
for item in i:
try: iter(item)
except: yield item
else:
if isinstance(item, str): yield item
else: yield from flattish(*item)
class Fake:
def __init__(self, l):
self.l = l
self.index = 0
def __iter__(self):
return self
def __next__(self):
if self.index >= len(self.l):
raise StopIteration
else:
self.index +=1
return self.l[self.index-1]
def __str__(self):
return str(self.l)
def flatten_notype(*i):
for item in i:
try:
n = next(iter(item))
try:
n2 = next(iter(n))
recur = n == n2
except TypeError:
yield from flatten(*item)
else:
if recur:
yield item
else:
yield from flatten(*item)
except TypeError:
yield item
def flatten(*i):
for item in i:
try:
n = next(iter(item))
try:
n2 = next(iter(n))
recur = n == n2
except TypeError:
yield from flatten(*item)
else:
if recur:
yield item if isinstance(n2, type(item)) or isinstance(item, type(n2)) else n2
else:
yield from flatten(*item)
except TypeError:
yield item
f = Fake('abc')
print(*flattish(f)) # should be `abc`
print(*flattish((f,))) # should be `abc` > ``
print(*flattish(1, ('a',), ('bc',))) # should be `1 a bc`
f = Fake([1, 2, 3])
print(*flattish(f)) # should be `1 2 3`
print(*flattish((f,))) # should be `1 2 3` > ``
print(*flattish(1, ('a',), ('bc',))) # should be `1 a bc`
f = Fake('abc')
print(*flatten_notype(f)) # should be `abc`
print(*flatten_notype((f,))) # should be `abc` > `c`
print(*flatten_notype(1, ('a',), ('bc',))) # should be `1 a bc` > `1 ('a',) bc`
f = Fake([1, 2, 3])
print(*flatten_notype(f)) # should be `1 2 3` > `2 3`
print(*flatten_notype((f,))) # should be `1 2 3` > ``
print(*flatten_notype(1, ('a',), ('bc',))) # should be `1 a bc` > `1 ('a',) bc`
f = Fake('abc')
print(*flatten(f)) # should be `abc` > `a`
print(*flatten((f,))) # should be `abc` > `c`
print(*flatten(1, ('a',), ('bc',))) # should be `1 a bc`
f = Fake([1, 2, 3])
print(*flatten(f)) # should be `1 2 3` > `2 3`
print(*flatten((f,))) # should be `1 2 3` > ``
print(*flatten(1, ('a',), ('bc',))) # should be `1 a bc`
Próbowałem zostały również następujące z rekurencyjnym lst zdefiniowano powyżej i flatten():
>>> print(*flatten(lst))
[[...]]
>>> lst.append(0)
>>> print(*flatten(lst))
[[...], 0]
>>> print(*list(flatten(lst))[0])
[[...], 0] 0
Jak widać, nie jest on podobny do 1 ('a',) bc jak również we własnym specjalny sposób.
czytam how can python function access its own attributes? myśleć, że być może funkcja mogła śledzić każdy obiekt to widział, ale to nie działa albo ponieważ nasz lst zawiera obiekt z pasującymi tożsamość i równości, struny zawierać obiekty, które mogą mieć tylko dopasowanie równości , a równość nie jest wystarczająca ze względu na możliwość czegoś takiego jak flatten([1, 2], [1, 2]).
Czy istnieje jakiś niezawodny sposób (tj. Nie sprawdza się po prostu znanych typów, nie wymaga, aby pojemnik rekursywny i jego pojemniki były tego samego typu itp.), Aby sprawdzić, czy pojemnik zawiera obiekty z możliwością iteracji nieskończona rekurencja i niezawodnie określić najmniejszy unikalny pojemnik? Jeśli tak, proszę wyjaśnić, jak to zrobić, dlaczego jest wiarygodny i jak radzi sobie z różnymi okolicznościami rekurencyjnymi. Jeśli nie, proszę wyjaśnić, dlaczego jest to logicznie niemożliwe.
Myślę, że można to zredukować do wykrywania cykli w ukierunkowanych wykresach. Więc wszystkie rozwiązania, które mają tam zastosowanie, powinny mieć zastosowanie tutaj: http://stackoverflow.com/questions/261573/best-algorithm-for-detecting-cycles-in-a-directed-graph –