{"entities":{"Q7361034":{"pageid":31518641,"ns":120,"title":"Item:Q7361034","lastrevid":105362465,"modified":"2026-10-07T13:34:13Z","type":"item","id":"Q7361034","labels":{"en":{"language":"en","value":"Swap Distance"}},"descriptions":{"en":{"language":"en","value":"AFP entry Swap_Distance"}},"aliases":{},"claims":{"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"67616c9361eac8b69ebe82efe32c19b9dc9ee0db","datavalue":{"value":"https://isa-afp.org/entries/Swap_Distance.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q7361034$9D96715D-2DC8-49CA-8650-DB3715E14FEE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ed0acfea66d72dabedf8248efd6bd273a34db1fe","datavalue":{"value":{"time":"+2026-01-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q7361034$5BD3BE1B-70E6-44C1-8A4A-FB2974ABAE57","rank":"normal"}],"P43":[{"mainsnak":{"snaktype":"value","property":"P43","hash":"85859c7ab42dcb8b36208f2902b7ce0d86423a6f","datavalue":{"value":"Manuel Eberl","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361034$9AFF1902-1FB0-4DE2-93F7-74320002AFAA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8967800bc9f53ac035619883d4e3db95e499a5c9","datavalue":{"value":{"text":"Swap Distance","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q7361034$8E3F2D28-3B75-46D8-8C59-3E2EDB63C1EC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"bcac2ca788f18c13c7279ce00c2bfa579dbfcf53","datavalue":{"value":"Given two lists that are permutations of one another, the swap distance (also known as the Kendall tau distance ) is the minimum number of swap operations of adjacent elements required to make the two lists the same. Equivalently, the swap distance of two finite linear orders $\\preceq$ and $\\unlhd$ is the number of disagreements of the two orders, i.e. of pairs $(x,y)$ such that $x\\prec y$ and $y\\lhd x$. This article defines these two notions of swap distance as well as their equivalence under the obvious isomorphism between lists and linear orders given by interpreting a list as a ranking of elements in descending order. An efficient $O(n\\log n)$ algorithm to compute the swap distance is also provided via the connection to the number of inversions of a list, for which an efficient algorithm is already available in the AFP.","type":"string"},"datatype":"string"},"type":"statement","id":"Q7361034$982D4673-8809-4DA9-8919-B50B63734977","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"191734449ceba4bc2a76e944da27595387f6a747","datavalue":{"value":{"entity-type":"item","numeric-id":3194802,"id":"Q3194802"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361034$331BC733-7A03-4F2F-ABF0-9541E3077642","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb081c24d3f308759ffc5be25d93bb06a52b464f","datavalue":{"value":{"entity-type":"item","numeric-id":3192088,"id":"Q3192088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361034$32620785-A993-43C3-A6FA-A4338A507D62","rank":"normal"}],"P37":[{"mainsnak":{"snaktype":"value","property":"P37","hash":"9a21a8eebe97539644aa32b24dda137c12e751dc","datavalue":{"value":{"entity-type":"item","numeric-id":40327,"id":"Q40327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361034$FF42AFB7-900A-4E60-A301-9FBEEDA0F706","rank":"normal"}],"P585":[{"mainsnak":{"snaktype":"value","property":"P585","hash":"e0b5465b6a0d9e05645cdb7168eee1aaf7eb2845","datavalue":{"value":{"entity-type":"item","numeric-id":7361518,"id":"Q7361518"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361034$26596F6E-3783-43A5-8156-ED5B6A8830F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P585","hash":"a2bc3c32469f67af243c54b77c1449b625c9c86f","datavalue":{"value":{"entity-type":"item","numeric-id":7361696,"id":"Q7361696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361034$375ADD62-EA91-4697-B5C8-0B340285FE44","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P585","hash":"51ca2f2f612e24efc8e74d5209617a4410e3452c","datavalue":{"value":{"entity-type":"item","numeric-id":7361236,"id":"Q7361236"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361034$5FA9F240-070B-4767-A429-8193C1C97D78","rank":"normal"}],"P2651":[{"mainsnak":{"snaktype":"value","property":"P2651","hash":"5634edfbfbc0239093a6d080d47ef70273afec4d","datavalue":{"value":{"entity-type":"item","numeric-id":7360824,"id":"Q7360824"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361034$EB4EB6B3-E228-435C-B0C4-A0C4FBB04773","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"908c3454b3659c4b140ccce33c5aee31081edc8d","datavalue":{"value":{"entity-type":"item","numeric-id":5976450,"id":"Q5976450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7361034$91140010-B1EE-4D77-8B6B-97EFEE47C5F3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Swap Distance","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Swap_Distance"}}}}}