Setting aside the fact that tax lots (using specific id) should usually be assigned at the time of the trade (for stocks in the USA), let's assume instead we want an algorithm to optimally allocate them once we have the whole list of trades in hand for a single security. Each trade comprises: date-time, number-of-shares, total-dollar-amount and can be either buy or sell.
Our goal is to maximize the capital gains allocated to long term rather than short term, defined when a matching buy and sell are more than a year apart. A capital gain is the proceeds from the sale of the shares less the cost of those shares.
100 shares on Jan 01 2020 total cost \$100
200 shares on Aug 01 2020 total cost \$125
150 shares on Sep 01 2020 total proceeds \$110
150 shares on Mar 01 2021 total proceeds \$185
Total capital gain is \$(185+110-125-100) ie. \$70 which will be partly short term and partly long term such that short term capital gains + long term capital gains = \$70.
What's the optimal algorithm to allocate tax lots when doing it in retrospect, ie.
What is a general algorithm identifying which share purchase to match to each share sold in order to maximize the long term capital gain portion?
So output might be something like, for the 150 shares sold on 9/1/2020, 100 should come from the first buy, 50 from the second buy. For the 150 sold on 3/1/2021, all 150 come from the 2nd buy.