Inversion (discrete mathematics) (original) (raw)
In computer science and discrete mathematics, an inversion in a sequence is a pair of elements that are out of their natural order.
| Property | Value |
|---|---|
| dbo:abstract | Unter Fehlstand, Fehlstellung oder Inversion einer Permutation versteht man in der Kombinatorik ein Paar von Elementen einer geordneten Menge, deren Reihenfolge durch die Permutation vertauscht wird. Die Anzahl der Fehlstände einer Permutation heißt Fehlstandszahl oder Inversionszahl der Permutation. Über die Fehlstandszahl lässt sich das Vorzeichen einer Permutation ermitteln, wobei eine gerade Permutation eine gerade Fehlstandszahl und eine ungerade Permutation eine ungerade Fehlstandszahl aufweist. Es gibt verschiedene Möglichkeiten zur Darstellung der Fehlstände einer Permutation, beispielsweise über die Inversionstafel, den Lehmer-Code oder das Rothe-Diagramm. Fasst man die Einträge der Inversionstafel oder des Lehmer-Codes als Zahl in einem fakultätsbasierten Zahlensystem auf, kann jeder Permutation eine eindeutige Nummer zugewiesen werden. Weiter lässt sich mit Hilfe der Fehlstände auf der Menge der Permutationen eine partielle Ordnung definieren. Nachdem die Fehlstandszahl einer Permutation als Maß für die Unordnung der durch die Permutation vertauschten Zahlen angesehen werden kann, spielen Fehlstände eine wichtige Rolle bei der Analyse von Sortierverfahren. (de) In computer science and discrete mathematics, an inversion in a sequence is a pair of elements that are out of their natural order. (en) 計算機科学および離散数学における列の転倒（てんとう、英: inversion）は、その列の項の対であって、それらの項の成分が自然な順番から外れているようなものを言う。 (ja) Inwersja – para liczb: w ciągu: gdzie jeżeli Przykład:Niech dany będzie ciąg liczb: 1, 2, 5, 7, 4, 6 – pary (5, 4), (7,4) oraz (7, 6) tworzą inwersje w tym ciągu. Używa się do oznaczenia liczby inwersji w pewnej permutacji (pl) Inom kombinatorik avser en inversion ett par av element i en sekvens som står i omvänd naturlig ordning. En inversion kan också beskrivas som en omkastning av den inbördes ordningen för ett par av element vid en permutation. (sv) Інверсією в дискретній математиці називається послідовність із двох чисел впорядкованих в оберненому порядку. Інверсією в перестановці називається пара індексів така, що и . Парність числа інверсій в перестановці визначає парність перестановки. Числом інверсії послідовності є кількість інверсій в послідовності, це число в межах (uk) 设A为一个有n个数字的有序集（n>1），其中所有数字各不相同。 如果存在正整數i, j使得1 ≤ i ＜ j ≤ n而且A[i] ＞ A[j]，則這一個有序對稱為A的一個逆序對，也称作逆序。逆序對的數量称作「逆序数」或「反序數」。 例如：数组<2,3,8,6,1>的逆序对为：<2,1> <3,1> <8,1> <8,6> <6,1>共5个逆序对。 对于<2,1>:1 ≤ 1 ＜ 5 ≤ 5 ,A[1] ＞A[5]，所以为一个合法的逆序对。 目前求逆序对数目比较普遍的方法是利用归并排序做到的时间复杂度。 当然，也可以利用树状数组、线段树来实现这种基础功能。复杂度均为。 (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Inversion_qtl1.svg?width=300 |
| dbo:wikiPageExternalLink | https://oeis.org/wiki/Index_to_OEIS:_Section_Fa%23facbase https://archive.org/details/Comtet_Louis_-_Advanced_Coatorics |
| dbo:wikiPageID | 21473801 (xsd:integer) |
| dbo:wikiPageLength | 15252 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1114990542 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Rothe_diagram dbr:Permutation dbr:Permutation_matrix dbr:Permutohedron dbr:Introduction_to_Algorithms dbc:Order_theory dbc:Permutations dbr:Multiset dbc:String_metrics dbr:Comparison_sort dbr:Computer_science dbr:Parity_of_a_permutation dbc:Discrete_mathematics dbc:Sorting_algorithms dbr:Total_order dbr:Lattice_(order) dbc:Combinatorics dbr:Damerau–Levenshtein_distance dbr:Cardinality dbr:Cayley_graph dbr:Discrete_mathematics dbr:Journal_of_Graph_Algorithms_and_Applications dbr:Kendall_tau_distance dbr:Lehmer_code dbr:On-Line_Encyclopedia_of_Integer_Sequences dbr:Sequence dbr:Wolfram_Mathematica dbr:Factorial_number_system dbr:The_Art_of_Computer_Programming dbr:Partial_order dbr:Permutation_graph dbr:Permutation_group dbr:Subset dbr:Skeleton_(topology) dbr:Colexicographic_order dbr:File:2-element_subsets_of_4_elements;_array,_hexagonal.svg dbr:File:Inversion_example;_Rothe_1.svg dbr:File:Inversion_qtl1.svg dbr:File:Symmetric_group_4;_permutohedron_3D;_numbers.svg dbr:V:Inversion_(discrete_mathematics) |
| dbp:wikiPageUsesTemplate | dbt:OEIS_link dbt:4-el_perm_inversions dbt:Cite_book dbt:Cite_journal dbt:Commons_category dbt:Math dbt:Refbegin dbt:Refend dbt:Reflist dbt:Sfn dbt:Short_description dbt:Wikiversity dbt:3-el_perm_inversions |
| dcterms:subject | dbc:Order_theory dbc:Permutations dbc:String_metrics dbc:Discrete_mathematics dbc:Sorting_algorithms dbc:Combinatorics |
| gold:hypernym | dbr:Pair |
| rdf:type | dbo:Place yago:WikicatSortingAlgorithms yago:WikicatStringSimilarityMeasures yago:Abstraction100002137 yago:Act100030358 yago:Action100037396 yago:Activity100407535 yago:Algorithm105847438 yago:Change107296428 yago:Choice100161243 yago:Decision100162632 yago:Event100029378 yago:Happening107283608 yago:Maneuver100168237 yago:Measure100174412 yago:Move100165942 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:SortingAlgorithm105847658 yago:Substitution107443761 yago:Variation107337390 yago:WikicatPermutations |
| rdfs:comment | In computer science and discrete mathematics, an inversion in a sequence is a pair of elements that are out of their natural order. (en) 計算機科学および離散数学における列の転倒（てんとう、英: inversion）は、その列の項の対であって、それらの項の成分が自然な順番から外れているようなものを言う。 (ja) Inwersja – para liczb: w ciągu: gdzie jeżeli Przykład:Niech dany będzie ciąg liczb: 1, 2, 5, 7, 4, 6 – pary (5, 4), (7,4) oraz (7, 6) tworzą inwersje w tym ciągu. Używa się do oznaczenia liczby inwersji w pewnej permutacji (pl) Inom kombinatorik avser en inversion ett par av element i en sekvens som står i omvänd naturlig ordning. En inversion kan också beskrivas som en omkastning av den inbördes ordningen för ett par av element vid en permutation. (sv) Інверсією в дискретній математиці називається послідовність із двох чисел впорядкованих в оберненому порядку. Інверсією в перестановці називається пара індексів така, що и . Парність числа інверсій в перестановці визначає парність перестановки. Числом інверсії послідовності є кількість інверсій в послідовності, це число в межах (uk) 设A为一个有n个数字的有序集（n>1），其中所有数字各不相同。 如果存在正整數i, j使得1 ≤ i ＜ j ≤ n而且A[i] ＞ A[j]，則這一個有序對稱為A的一個逆序對，也称作逆序。逆序對的數量称作「逆序数」或「反序數」。 例如：数组<2,3,8,6,1>的逆序对为：<2,1> <3,1> <8,1> <8,6> <6,1>共5个逆序对。 对于<2,1>:1 ≤ 1 ＜ 5 ≤ 5 ,A[1] ＞A[5]，所以为一个合法的逆序对。 目前求逆序对数目比较普遍的方法是利用归并排序做到的时间复杂度。 当然，也可以利用树状数组、线段树来实现这种基础功能。复杂度均为。 (zh) Unter Fehlstand, Fehlstellung oder Inversion einer Permutation versteht man in der Kombinatorik ein Paar von Elementen einer geordneten Menge, deren Reihenfolge durch die Permutation vertauscht wird. Die Anzahl der Fehlstände einer Permutation heißt Fehlstandszahl oder Inversionszahl der Permutation. Über die Fehlstandszahl lässt sich das Vorzeichen einer Permutation ermitteln, wobei eine gerade Permutation eine gerade Fehlstandszahl und eine ungerade Permutation eine ungerade Fehlstandszahl aufweist. (de) |
| rdfs:label | Fehlstand (de) Inversion (discrete mathematics) (en) 転倒 (数学) (ja) Inwersja (kombinatoryka) (pl) Inversion (kombinatorik) (sv) 逆序对 (zh) Інверсія (дискретна математика) (uk) |
| owl:sameAs | freebase:Inversion (discrete mathematics) yago-res:Inversion (discrete mathematics) wikidata:Inversion (discrete mathematics) dbpedia-de:Inversion (discrete mathematics) dbpedia-fa:Inversion (discrete mathematics) dbpedia-ja:Inversion (discrete mathematics) dbpedia-kk:Inversion (discrete mathematics) dbpedia-pl:Inversion (discrete mathematics) dbpedia-sv:Inversion (discrete mathematics) dbpedia-uk:Inversion (discrete mathematics) dbpedia-zh:Inversion (discrete mathematics) https://global.dbpedia.org/id/NhMZ |
| prov:wasDerivedFrom | wikipedia-en:Inversion_(discrete_mathematics)?oldid=1114990542&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/2-element_subsets_of_4_elements;_array,_hexagonal.svg wiki-commons:Special:FilePath/Inversion_example;_Rothe_1.svg wiki-commons:Special:FilePath/Inversion_qtl1.svg wiki-commons:Special:FilePath/Symmetric_group_4;_permutohedron_3D;_numbers.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Inversion_(discrete_mathematics) |
| is dbo:wikiPageDisambiguates of | dbr:Inversion |
| is dbo:wikiPageRedirects of | dbr:Inversion_(combinatorics) dbr:Inversion_(computer_science) dbr:Inversion_number dbr:Inversion_vector dbr:Weak_order_of_permutations |
| is dbo:wikiPageWikiLink of | dbr:Ronald_Graham dbr:Permutation dbr:Cycle_graph_(algebra) dbr:List_of_permutation_topics dbr:Inversion dbr:Stanley_symmetric_function dbr:15_puzzle dbr:Necklace_(combinatorics) dbr:Q-analog dbr:Gaussian_binomial_coefficient dbr:Parity_of_a_permutation dbr:Stack-sortable_permutation dbr:Bubble_sort dbr:Adaptive_sort dbr:Heinrich_August_Rothe dbr:Separable_permutation dbr:Affine_symmetric_group dbr:Kendall_tau_distance dbr:Lehmer_code dbr:Kig_(software) dbr:SymPy dbr:Dihedral_group dbr:Sorting_algorithm dbr:Factorial_number_system dbr:Inversion_(combinatorics) dbr:Permutation_graph dbr:Splaysort dbr:Steinhaus–Johnson–Trotter_algorithm dbr:Inversion_(computer_science) dbr:Inversion_number dbr:Inversion_vector dbr:Weak_order_of_permutations |
| is foaf:primaryTopic of | wikipedia-en:Inversion_(discrete_mathematics) |
