Mam listę wzorów kolorów, które chciałbym posortować przy minimalnych wymianach. Nie ma znaczenia, czy zaczyna się od największego, czy najmniejszego zestawu, a kolejność kolorów nie jest ważna. Na przykład wejście:

Pattern 1 = [blue, white, red, black]

Pattern 2 = [blue, green, white]

Pattern 3 = [blue, green, yellow]

Pattern 4 = [blue, white, red]

Wynik byłby:

3 -> 2 -> 4 -> 1

Zaczynając od wzoru 3, sprawdzamy, jaki wzór można by wykonać jako następny z najmniejszą liczbą zmian, czyli byłby to wzór 2, ponieważ zmieniono jeden kolor. Potem byłby wzór 4, ponieważ znowu zmienia się jeden kolor. Na koniec wzór 1, ponieważ dodawany jest 1 kolor. Dodawanie i odejmowanie jest uważane za zmianę.

Zidentyfikowałem unikalne wzorce, ale nie wiem od czego zacząć od sortowania.

0
Nasr Cheaib 16 grudzień 2019, 17:31
Co rozumiesz przez minimalne przezbrojenie? czy możesz wyjaśnić, jak dochodzisz do wyjścia?
 – 
vb_rises
16 grudzień 2019, 17:32
Czy chcesz uporządkować alfabetycznie?
 – 
Liuk
16 grudzień 2019, 17:34
1
 – 
chepner
16 grudzień 2019, 19:16
Wyobraź sobie wykres, w którym każdy wzór jest wierzchołkiem, a każda krawędź jest ważona odległością Levenshteina między dwoma wzorami. Szukasz najkrótszej ścieżki między dowolnymi dwoma wierzchołkami.
 – 
chepner
16 grudzień 2019, 19:17
Zmiana jest definiowana przez parę wzorców, więc nie jest to tak naprawdę problem z sortowaniem. (A raczej sortujesz pary wzorców, ale nie każda para jest porównywalna, więc nie ma całkowitego uporządkowania par. Jednak sortowanie topologiczne jest ściśle związane z ideą znajdowania ścieżek na wykresie).
 – 
chepner
16 grudzień 2019, 19:40

2 odpowiedzi

Jest to problem grafowy, a mianowicie znajdowanie najkrótszej ścieżki między dwoma wzorcami.

Niech każdy wzór będzie wierzchołkiem na wykresie, a waga krawędzi (p1, p2) będzie równa Levenshtein odległość między tymi dwoma wzorami. Dla dowolnych dwóch wzorców możesz obliczyć najkrótszą ścieżkę między tymi dwoma wzorcami (która niekoniecznie jest pojedynczą krawędzią łączącą je), używając (na przykład) Algorytm Dijkstry.

W przypadku małego wykresu można wielokrotnie uruchomić algorytm Dijkstry dla każdego potencjalnego punktu początkowego i końcowego. Jednak w zależności od wykresu prawdopodobnie będziesz chciał użyć algorytmu do obliczenia wszystkich najkrótszych ścieżek przy użyciu (na przykład) Algorytm Floyda-Warshalla, a następnie wybierz najkrótszą ścieżkę z prawidłowymi punktami początkowymi i końcowymi.

Odnośnie czasów działania: zbudowanie wykresu zajmie O(n^2) czasu, jeśli utworzysz wszystkie możliwe krawędzie. Możliwe, że możesz przeprowadzić wstępne przetwarzanie, aby wyeliminować te krawędzie, które nie mogą być częścią rozwiązania.

Algorytm Dijkstry to O(m + n lg n), co oznacza, że ​​na całym grafie skonstruowanym powyżej jest to O(n^2). Przy O(n^2) możliwych parach czas wykonania wyniesie O(n^4), co jest wolniejsze niż O(n^3), które przyjmie wykres Floyda-Warshalla na dowolnym wykresie. Jak widać, algorytm, którego chcesz użyć, będzie w dużej mierze zależeć od tego, jak konstruujesz i/lub przycinasz swój wykres, a także od tego, czy możesz przyciąć kandydujące zestawy punktów początkowych/końcowych.

2
chepner 16 grudzień 2019, 19:38
Jeśli dobrze to rozumiem, trzeba sprawdzić odległość od każdego punktu do drugiego, a następnie wybrać najkrótszą drogę spośród nich?
 – 
Andrej Kesely
16 grudzień 2019, 19:26
1
Prawidłowy. Przypadkowo pominąłem wzmiankę o najkrótszej ścieżce wszystkich par w poprzedniej wersji tej odpowiedzi.
 – 
chepner
16 grudzień 2019, 19:28

Nie jestem pewien, czy sorted() z niektórymi key= można zastosować tutaj. Mój przykład to podejście brutalne (sprawdzamy wszystkie permutacje wzorców pod kątem najmniejszej sumy przezbrojeń). Może jest najszybszy algorytm.

patterns = [
    ['blue', 'white', 'red', 'black'],
    ['blue', 'green', 'white'],
    ['blue', 'green', 'yellow'],
    ['blue', 'white', 'red']
]

from itertools import permutations

def get_num_changeovers(a, b):
    """ Get number of changeovers from a -> b """
    l = min(len(a), len(b))
    return l - len(set(a) & set(b)) + abs(len(a) - len(b))

cost = float('inf')
current = None
for p in permutations(patterns):
    s = sum(get_num_changeovers(a, b) for a, b in zip(p, p[1:]))
    if s < cost:
        cost = s
        current = p

print('Cost    : ', cost)
print('Patterns: ', current)

Wydruki:

Cost    :  3
Patterns:  (['blue', 'white', 'red', 'black'], ['blue', 'white', 'red'], ['blue', 'green', 'white'], ['blue', 'green', 'yellow'])
0
Andrej Kesely 16 grudzień 2019, 19:14