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.
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.
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'])
Podobne pytania
Nowe pytania
python
Python to wielozadaniowy, wielozadaniowy język programowania dynamicznie typowany. Został zaprojektowany tak, aby był szybki do nauczenia się, zrozumienia i użycia oraz wymuszania czystej i jednolitej składni. Należy pamiętać, że Python 2 oficjalnie nie jest obsługiwany od 01-01-2020. Mimo to, w przypadku pytań Pythona specyficznych dla wersji, dodaj znacznik [python-2.7] lub [python-3.x]. Korzystając z wariantu Pythona (np. Jython, PyPy) lub biblioteki (np. Pandas i NumPy), należy umieścić go w tagach.