Pytania otagowane jako permutations

Otrzymujesz tablicę elementów2n2n2n a1,a2,…,an,b1,b2,…bna1,a2,…,an,b1,b2,…bna_1, a_2, \dots, a_n, b_1, b_2, \dots b_n Zadanie polega na przeplataniu tablicy przy użyciu algorytmu lokalnego, takiego jak tablica wynikowa b1,a1,b2,a2,…,bn,anb1,a1,b2,a2,…,bn,anb_1, a_1, b_2, a_2, \dots , b_n, a_n Gdyby nie istniał wymóg lokalny, moglibyśmy łatwo utworzyć nową tablicę i skopiować elementy, dając algorytm czasowy .O(n)O(n)\mathcal{O}(n) Z …

62 algorithms  arrays  permutations  in-place 

Wikipedia, jak również inne źródła, które znalazłem, wskazują voidtyp C jako typ jednostki, a nie typ pusty. Uważam to za mylące, ponieważ wydaje mi się, że voidlepiej pasuje do definicji typu pustego / dolnego. voidO ile wiem, nie zamieszkują żadnych wartości . Funkcja z typem zwracanym void określa, że ​​funkcja …

28 type-theory  c  logic  modal-logic  coq  equality  coinduction  artificial-intelligence  computer-architecture  compilers  asymptotics  formal-languages  asymptotics  landau-notation  asymptotics  turing-machines  optimization  decision-problem  rice-theorem  algorithms  arithmetic  floating-point  automata  finite-automata  data-structures  search-trees  balanced-search-trees  complexity-theory  asymptotics  amortized-analysis  complexity-theory  graphs  np-complete  reductions  np-hard  algorithms  string-metrics  computability  artificial-intelligence  halting-problem  turing-machines  computation-models  graph-theory  terminology  complexity-theory  decision-problem  polynomial-time  algorithms  algorithm-analysis  optimization  runtime-analysis  loops  turing-machines  computation-models  recurrence-relation  master-theorem  complexity-theory  asymptotics  parallel-computing  landau-notation  terminology  optimization  decision-problem  complexity-theory  polynomial-time  counting  coding-theory  permutations  encoding-scheme  error-correcting-codes  machine-learning  natural-language-processing  algorithms  graphs  social-networks  network-analysis  relational-algebra  constraint-satisfaction  polymorphisms  algorithms  graphs  trees 

Masz tablicę różnych elementów. Masz dostęp do komparatora (funkcja czarnej skrzynki, która bierze dwa elementy a i b i zwraca prawdziwy iff a &lt; b ) oraz naprawdę losowe źródło bitów (funkcja czarnej skrzynki nie przyjmuje argumentów i zwraca niezależnie jednakowo losowy bit). Rozważ następujące dwa zadania:nnnaaabbba&lt;ba&lt;ba < b Tablica …

18 algorithms  algorithm-analysis  information-theory  permutations  entropy 

Biorąc pod uwagę tubę z ponumerowanymi kulkami (losowa). Rurka ma otwory do usuwania kulki. Rozważ następujące kroki dla jednej operacji: Możesz wybrać jedną lub więcej piłek z dołków i zapamiętać kolejność, w jakiej je wybrałeś. Musisz przechylić rurę w lewą stronę, aby pozostałe kulki w rurze przesunęły się w lewo …

14 sorting  permutations 

Ostatnio zostałem zapytany o ten problem w wywiadzie algorytmicznym i nie udało mi się go rozwiązać. Biorąc pod uwagę dwie wartości N i M, musisz policzyć liczbę permutacji o długości N (używając liczb od 1 do N), tak aby absolutna różnica między dowolną liczbą w permutacji a jej pozycją w …

13 algorithms  permutations  algorithm-design 

tło \newcommand\ms[1]{\mathsf #1}\def\msD{\ms D}\def\msS{\ms S}\def\mfS{\mathfrak S}\newcommand\mfm[1]{#1}\def\po{\color{#f63}{\mfm{1}}}\def\pc{\color{#6c0}{\mfm{c}}}\def\pt{\color{#08d}{\mfm{2}}}\def\pth{\color{#6c0}{\mfm{3}}}\def\pf{4}\def\pv{\color{#999}5}\def\gr{\color{#ccc}}\let\ss\gr Załóżmy, że mam dwie identyczne partie nnn kulek. Każdy marmur może mieć jeden z kolorów ccc , gdzie c≤nc≤nc≤n . Niech ninin_i oznacza liczbę kulek koloru iii w każdej partii. Niech SS\msS będzie multiset {1,…,1n1,2,…,2n2,…,1c,…,cnc}{1,…,1⏞n1,2,…,2⏞n2,…,1c,…,c⏞nc}\small\{\overbrace{\po,…,\po}^{n_1},\;\overbrace{\pt,…,\pt}^{n_2},\;…,\;\overbrace{\vphantom 1\pc,…,\pc}^{n_c}\} reprezentujący jedną partię. W reprezentacji częstotliwości , SS\msS …

13 algorithms  combinatorics  probability-theory  permutations  sampling 

Jako zabawny projekt pracowałem nad implementacją C # Richarda Korfa - Znalezienie optymalnych rozwiązań dla kostki Rubika przy użyciu baz danych wzorców. https://www.cs.princeton.edu/courses/archive/fall06/cos402/papers/korfrubik.pdf Właściwie to działa, staram się tylko ulepszyć swoje rozwiązanie. Jedną rzeczą, na którą Korf patrzy w swoim artykule, jest to, jak przechowuje i indeksuje bazy danych wzorców. …

11 algorithms  permutations 

Natknąłem się na ten problem i staram się znaleźć sposób, aby go rozwiązać. Jakiekolwiek propozycje będą mile widziane! Załóżmy, że mamy matrycę {−1,0,1}n × k{−1,0,1}n × k\{-1, 0, 1\}^{n\ \times\ k} , na przykład, ⎡⎣⎢⎢⎢⎢⎢⎢1−10−11001−101010000010−11−11−1⎤⎦⎥⎥⎥⎥⎥⎥[1010−1−100010110−1−1−10111000−1]\begin{bmatrix} 1 & 0 & 1 & 0 & -1 \\ -1 & 0 & 0 …

9 algorithms  optimization  combinatorics  matrices  permutations 

Zainspirowane tym pytaniem, w którym pytający chce wiedzieć, czy czas działania zmienia się, gdy komparator użyty w standardowym algorytmie wyszukiwania zostaje zastąpiony uczciwym rzucie monetą, a także wyraźnym niepowodzeniem Microsoftu w napisaniu jednolitego generatora permutacji, moje pytanie jest zatem : Czy istnieje algorytm sortowania oparty na porównaniu, który w zależności …

9 sorting  randomized-algorithms  permutations 

Utknąłem na tym problemie: Biorąc pod uwagę tablicę AZAA z pierwszego nnn liczby naturalne losowo permutowane, tablica BbB jest zbudowany tak, że B(k)b(k)B(k) jest liczbą elementów od A(1)ZA(1)A(1) do A(k−1)ZA(k-1)A(k-1) które są mniejsze niż A(k)ZA(k)A(k). i) Biorąc pod uwagę AZAA czy możesz znaleźć BbB w O(n)O(n)O(n)czas? ii) Biorąc pod uwagęBbB …

9 algorithms  arrays  permutations