Beefy Boxes and Bandwidth Generously Provided by pair Networks
Syntactic Confectionery Delight
 
PerlMonks  

Comment on

( #3333=superdoc: print w/ replies, xml ) Need Help??
Your code doesn't do the complete patience sorting, it does more or less sort, but you're left with some sorted piles of cards after it finishes — typically 11 piles for a deck of 52 cards, I read. You still need to do the second step: pick the lowest card from every pile, but you don't know what pile that is — except when you just start, then it's the leftmost one. It would be some form of merge sort.

I found one of the original scientific papers in PDF format (30 pages, 277k), in year 1999, item 2.

On to your questions.

Do the algorithms still work if the original list sorted in ascending order is non-continguous (! 1..N)?
Of course they do. All you use for the sorting action, is compare two items. Apart from that, their actual value is never used.

Do the algorithms still work if the original list contains duplicates?
Yes, but depending on what you do when they compare the same, your sort might be a stable sort, or not. You would get a stable sort if you treat the current card as the larger one, when they do agree.

Are there ways to maintain the same speed and decrease the memory consumption?
If so, I haven't found one.

Would there be a benefit in replacing the linear card placement search with a binary one or would the overhead outweigh the benefit.
No idea... In practice, I found binary search often to be slower than linear search, for few items — sometimes not even that few, as I've seen linear search being faster for a search in 500 items.

But we're still stuck with an incomplete sorting.

Perhaps binary search, or rather, a binary tree, could be benificial to complete the sorting: when you have constructed the piles, put (just) the top cards in the binary tree, remove the lowest value from it and from the pile, and insert the next one from the same pile that it came from. Repeat until all piles are expleted and the tree is empty.


In reply to Re: Patience Sorting To Find Longest Increasing Subsequence by bart
in thread Patience Sorting To Find Longest Increasing Subsequence by Limbic~Region

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • Outside of code tags, you may need to use entities for some characters:
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?
    Username:
    Password:

    What's my password?
    Create A New User
    Chatterbox?
    and the web crawler heard nothing...

    How do I use this? | Other CB clients
    Other Users?
    Others pondering the Monastery: (6)
    As of 2014-09-17 02:58 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      How do you remember the number of days in each month?











      Results (56 votes), past polls