punkt A lista może być zweryfikowany jako klasyfikowane porównując każdy element do swojego sąsiada. W mojej aplikacji nie będę w stanie porównać każdego elementu z jego sąsiadem: zamiast tego porównania będą czasami dokonywane między odległymi elementami. Biorąc pod uwagę, że lista zawiera więcej niż trzy elementy, a także porównanie jest jedyną obsługiwaną operacją, czy kiedykolwiek istnieje „sieć” porównań, która udowodni, że lista jest posortowana, ale brakuje jej co najmniej jednego bezpośredniego sąsiada do sąsiada porównanie?
Formalnie dla sekwencji elementów mam zestaw par indeksów dla których wiem, czy , , czy . Istnieje para której brakuje w zestawie porównań. Czy jest zatem kiedykolwiek możliwe udowodnienie, że sekwencja jest posortowana?
Odpowiedzi:
To jest niemożliwe. Załóżmy, że masz wynik wszystkich porównań oprócz pary( i , i + 1 ) . Wówczas nie byłbyś w stanie rozróżnić następujących dwóch przypadków:
1 , 2 , … , i - 1 , i , i + 1 , i + 2 , … , n1 , 2 , … , i - 1 , i + 1 , i , i + 2 ,… , n
źródło