Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Sorting a bridge hand
KTH, Superseded Departments, Numerical Analysis and Computer Science, NADA.
KTH, Superseded Departments, Numerical Analysis and Computer Science, NADA.
KTH, Superseded Departments, Mathematics.
Show others and affiliations
2001 (English)In: Discrete Mathematics, ISSN 0012-365X, E-ISSN 1872-681X, Vol. 241, no 1-3, 289-300 p.Article in journal (Refereed) Published
Abstract [en]

Sorting a permutation by block moves is a task that every bridge player has to solve every time she picks up a new hand of cards. It is also a problem for the computational biologist, for block moves are a fundamental type of mutation that can explain why genes common to two species do not occur in the same order in the chromosome, It is not known whether there exists an optimal sorting procedure running in polynomial time. Bafna and Pevzner gave a polynomial time algorithm that sorts any permutation of length n in at most 3n/4 moves. Our new algorithm improves this to [(2n - 2)/3] for n greater than or equal to 9. For the reverse permutation, we give an exact expression for the number of moves needed, namely [(n + 1)/2]. Computations of Bafha and Pevzner up to n = 10 seemed to suggest that this is the worst case; but as it turns out, a first counterexample occurs for n = 13, i.e. the bridge player's case. Professional card players never sort by rank, only by suit. For this case, we give a complete answer to the optimal sorting problem.

Place, publisher, year, edition, pages
2001. Vol. 241, no 1-3, 289-300 p.
Keyword [en]
sorting by transpositions, sorting a bridge hand, Cayley graph, toric permutation
National Category
Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-21070DOI: 10.1016/S0012-365X(01)00150-9ISI: 000171917500023OAI: oai:DiVA.org:kth-21070DiVA: diva2:339767
Note
QC 20100525Available from: 2010-08-10 Created: 2010-08-10 Last updated: 2010-09-29Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Eriksson, HenrikKarlander, JohanSvensson, Lars ErikWästlund, Johan
By organisation
Numerical Analysis and Computer Science, NADAMathematics
In the same journal
Discrete Mathematics
Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 61 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf