On Tue, 21 Feb 2012 18:48:01 -0800 (PST), Daniel Janus
<n...@g...com> wrote:

>Szkic:
>
>Wstępne przetwarzanie: liczymy domknięcie przechodnie wejściowego grafu G, odwracamy
w nim kierunki wszystkich krawędzi i otrzymany graf (oznaczmy go G') zapamiętujemy
jako listę zbiorów incydencji.
>
>Algorytm: rozbijamy naszą zmianę porządku topologicznego na złożenie inwersji, czyli
zamian miejscami dwóch elementów porządku. Intuicyjnie, jeśli zmiana była niewielka,
to i inwersji będzie mało. Teraz dla każdej inwersji elementu i-tego z j-tym, i < j,
rozważamy zbiór wierzchołków {a_{i+1}, a_{i+2}, ..., a_{j-1}} i liczymy jego
teoriomnogościowe przecięcie ze zbiorem krawędzi wychodzącym w G' z wierzchołka a_j.
Jeśli któreś przecięcie wyjdzie niepuste, to psuje ono porządek topologiczny, w
przeciwnym wypadku otrzymana permutacja dalej jest porządkiem.
>
>Wydaje mi się, że to działa, choć mogłem coś pochrzanić. Sprawdzenie poprawności i
szczegóły implementacyjne takie jak wybór reprezentacji zbiorów pozostawiam jako
ćwiczenie.
>

Tego sie nei da zrobic "parami", bo para moze naruszac porzadek, ale
dodanie drugiej pary powoduje ze czworka juz nie narusza porzadku. Nie
da sie robic sekwencyjnie parami. To byl pierwszy blad ktory
popelnilem na samym poczatku.

Neijaki Ruskey pokazal ze nei da sie wygenerowac wszystkich porzadkow
przez transpozycje

http://webhome.cs.uvic.ca/~ruskey/Publications/

Frank Ruskey, Generating Linear Extensions of Posets by
Transpositions, Journal of Combinatorial Theory (B), 54 (1992) 77-101.
G. Pruesse and F.Ruskey, Generating the Linear Extensions of Certain
Posets by Transpositions, SIAM J. Discrete Mathematics 4 (1991)
413-422.

Mozna sciagnac ze strony autora

A.L.