View in EDS

A geometric form for the extended patience sorting algorithm

Saved in:
Bibliographic Details
Title: A geometric form for the extended patience sorting algorithm
Authors: Burstein, Alexander1 burstein@math.iastate.edu, Lankham, Isaiah2 issy@math.ucdavis.edu
Source: Advances in Applied Mathematics. Feb2006, Vol. 36 Issue 2, p106-117. 12p.
Subjects: Algorithms, Combinatorial probabilities, Configurations (Geometry), Permutations, Lattice paths
Abstract: Abstract: Patience Sorting is a combinatorial algorithm that can be viewed as an iterated, non-recursive form of the Schensted Insertion Algorithm. In recent work the authors extended Patience Sorting to a full bijection between the symmetric group and certain pairs of combinatorial objects (called pile configurations) that are most naturally defined in terms of generalized permutation patterns and barred pattern avoidance. This Extended Patience Sorting Algorithm is very similar to the Robinson–Schensted–Knuth (or RSK) Correspondence, which is itself built from repeated application of the Schensted Insertion Algorithm. In this work we introduce a geometric form for the Extended Patience Sorting Algorithm that is in some sense a natural dual algorithm to G. Viennot''s celebrated Geometric RSK Algorithm. Unlike Geometric RSK, though, the lattice paths coming from Patience Sorting are allowed to intersect. We thus also give a characterization for the intersections of these lattice paths in terms of the pile configurations associated with a given permutation under the Extended Patience Sorting Algorithm. [Copyright &y& Elsevier]
Copyright of Advances in Applied Mathematics is the property of Academic Press Inc. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 19593184
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: A geometric form for the extended patience sorting algorithm
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Burstein%2C+Alexander%22">Burstein, Alexander</searchLink><relatesTo>1</relatesTo><i> burstein@math.iastate.edu</i><br /><searchLink fieldCode="AR" term="%22Lankham%2C+Isaiah%22">Lankham, Isaiah</searchLink><relatesTo>2</relatesTo><i> issy@math.ucdavis.edu</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Advances+in+Applied+Mathematics%22">Advances in Applied Mathematics</searchLink>. Feb2006, Vol. 36 Issue 2, p106-117. 12p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Combinatorial+probabilities%22">Combinatorial probabilities</searchLink><br /><searchLink fieldCode="DE" term="%22Configurations+%28Geometry%29%22">Configurations (Geometry)</searchLink><br /><searchLink fieldCode="DE" term="%22Permutations%22">Permutations</searchLink><br /><searchLink fieldCode="DE" term="%22Lattice+paths%22">Lattice paths</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: Abstract: Patience Sorting is a combinatorial algorithm that can be viewed as an iterated, non-recursive form of the Schensted Insertion Algorithm. In recent work the authors extended Patience Sorting to a full bijection between the symmetric group and certain pairs of combinatorial objects (called pile configurations) that are most naturally defined in terms of generalized permutation patterns and barred pattern avoidance. This Extended Patience Sorting Algorithm is very similar to the Robinson–Schensted–Knuth (or RSK) Correspondence, which is itself built from repeated application of the Schensted Insertion Algorithm. In this work we introduce a geometric form for the Extended Patience Sorting Algorithm that is in some sense a natural dual algorithm to G. Viennot''s celebrated Geometric RSK Algorithm. Unlike Geometric RSK, though, the lattice paths coming from Patience Sorting are allowed to intersect. We thus also give a characterization for the intersections of these lattice paths in terms of the pile configurations associated with a given permutation under the Extended Patience Sorting Algorithm. [Copyright &y& Elsevier]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Advances in Applied Mathematics is the property of Academic Press Inc. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=19593184
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1016/j.aam.2005.08.001
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 12
        StartPage: 106
    Subjects:
      – SubjectFull: Algorithms
        Type: general
      – SubjectFull: Combinatorial probabilities
        Type: general
      – SubjectFull: Configurations (Geometry)
        Type: general
      – SubjectFull: Permutations
        Type: general
      – SubjectFull: Lattice paths
        Type: general
    Titles:
      – TitleFull: A geometric form for the extended patience sorting algorithm
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Burstein, Alexander
      – PersonEntity:
          Name:
            NameFull: Lankham, Isaiah
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 02
              Text: Feb2006
              Type: published
              Y: 2006
          Identifiers:
            – Type: issn-print
              Value: 01968858
          Numbering:
            – Type: volume
              Value: 36
            – Type: issue
              Value: 2
          Titles:
            – TitleFull: Advances in Applied Mathematics
              Type: main
ResultId 1