Pytania otagowane jako permutations

1
Wydajny algorytm dla istnienia permutacji z sekwencją różnic?
To pytanie jest motywowane tym postem. Czy potrafisz określić sumę dwóch permutacji w czasie wielomianowym? oraz moje zainteresowanie obliczeniowymi właściwościami permutacji. Sekwencja różnic permutacji π liczb 1 , 2 , … n + 1 jest tworzona przez znalezienie różnicy między każdą dwiema sąsiednimi liczbami w permutacji π . Innymi słowy, …
1
Prawdopodobieństwo wygenerowania pożądanej permutacji przez losowe zamiany
Interesuje mnie następujący problem. Jako dane wejściowe podano „permutację docelową” , a także uporządkowaną listę indeksów . Następnie, zaczynając od listy (tj. Permutacja tożsamości), przy każdym kroku zamieniamy element w z element, z niezależnym prawdopodobieństwem . Niech będzie prawdopodobieństwem, że jest generowany jako wynik.I 1 , ... , i m …
1
Ostatnie postępy w algorytmach grup permutacji?
Interesują mnie algorytmy dla grup skończonych zaimplementowane w pakiecie GAP. Wydaje się, że wszystkie znane algorytmy w tej dziedzinie dotyczą grup permutacji / grup matryc; dwa podstawowe to Schreier-Sims [1970] i Butler [1979], patrz np. „Algorytmy dla grup permutacyjnych” Alice Niemeyer jako możliwy odnośnik (?) Dlatego zastanawiałem się, czy w …
1
Kodowanie zestawów permutacji za pomocą zestawu generującego i zestawu elementów wykluczonych
Algorytmy czasu wielomianowego znane są ze znajdowania generujących zestawów grup permutacji, co jest interesujące, ponieważ możemy następnie przedstawić te grupy zwięźle, nie rezygnując z algorytmów czasu wielomianowego do odpowiedzi na wiele interesujących pytań związanych z tymi grupami. Czasami jednak możemy być zainteresowani zestawem permutacji, który nie tworzy grupy, więc zestaw …
2
Jak tasować kolorowe kulki?
Mam 400 piłek, w których 100 to czerwone, 40 to żółte, 50 to zielone, 60 to niebieskie, 70 to fioletowe, 80 to czarne. (kule tego samego koloru są identyczne) Potrzebuję wydajnego algorytmu tasowania, aby po tasowaniu kulki znalazły się na liście i 3 kolejne kule nie są tego samego koloru. …
3
Dopasowanie wzorca permutacji w ciągach
Luźno mówiąc, dopasowanie wzorców permutacji dotyczy następujących problemów: Biorąc pod uwagę permutacje w S n i w , przy , czy zawiera podsekwencję o długości której elementy są uporządkowane według ?ππ\piSnSnS_nS m m ≤ n π τ m σσσ\sigmaSmSmS_mm≤nm≤nm\leq nππ\pi ττ\taummmσσ\sigma Na przykład, jeśli i , to podsekwencja pasuje do …
2
Czy istnieje skuteczny algorytm do znalezienia i-tej drogi?
Oto tło tego pytania. Graliśmy z przyjaciółmi w grę, w której każdy musi dać innym ludziom prezent. Aby ustalić, kto powinien komuś dać prezent, decydujemy się na losowanie. Problem w tym, że ktoś może dać sobie prezenty, co nie jest śmieszne. Widać, że oczekiwana liczba takich nieszczęśliwych osób wynosi 1, …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.