Beefy Boxes and Bandwidth Generously Provided by pair Networks
Just another Perl shrine
 
PerlMonks  

comment on

( #3333=superdoc: print w/replies, xml ) Need Help??
Sorry I did not mean to say you did not attribute the idea, I was just curious because you mentioned about implementation

I don't think I explained it very clearly. The idea I was trying to convey was if you have list of factorials then we should be able to find the besy way to subract them

Let's consider your example

a b c d --------- v w x y z Suppose you sort the numerator and denominator separately you might ge +t - d c b a --------- z y x w v i.e. d > c > b > a and z > y > x > w > v.
Under this situation subracting  d & z, c & y, b & x, a & w and leaving v as is will be the best ordering possible or in other words, there will not be a better subtraction process that will give us fewer total number of elements.

I left at subract (d & z) because (d can > z) or (d can be < z) so it will either go into the numerator or denomiator. But that's a simple logic to check and assign correctly

What i set out to prove was just that i.e. if you sort the lists and subract the like indices then you are gauranteed (?yet to be proved rigourously) to get the least possible number of elements after one round of cancellation! I do not think I was able to prove it in a sophisticated way but it seems to be suggesting it is correct...maybe it will be easier to run some test cases to actually check if the conjecture is true :)

If the above conjecture is true or at least intuitive then there is no ambiguity in the way subtraction should be done!

cheers

SK


In reply to Re^5: Algorithm for cancelling common factors between two lists of multiplicands by sk
in thread Algorithm for cancelling common factors between two lists of multiplicands by BrowserUk

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!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • 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
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            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 exploiting the Monastery: (5)
    As of 2019-11-17 23:16 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?
      Strict and warnings: which comes first?



      Results (87 votes). Check out past polls.

      Notices?