0

I have a list of tuples, for example [(1800, 3), (4000, 5), (1999, 4), (2000, 1), (2001, 2)]. I need a list of a set length (3, for example) using any combination of these tuples where BOTH elements are sorted in ascending order, like [(2000, 1), (2001, 2), (4000, 5)]. So [(1800, 3), (1999, 4), (2000, 1)] wouldn't work because it's sorted by the first element but not the second. Is it possible to sort a list the way I need?

Sable
  • 1
  • 1
    that's impossible, like how conceptually can you sort something by two things at once – Hippolippo Dec 19 '21 at 08:23
  • @Hippolippo yeah that's fair, thanks – Sable Dec 19 '21 at 08:27
  • @Sable Check [this](https://stackoverflow.com/questions/4233476/sort-a-list-by-multiple-attributes/4233482) out my friend – Dad Dec 19 '21 at 08:28
  • Welcome to Stack Overflow. "So `[(1800, 3), (1999, 4), (2000, 1)]` wouldn't work because it's sorted by the first element but not the second" Well, *what do you want the code to do* if that is the input? – Karl Knechtel Dec 19 '21 at 08:37
  • 1
    Looking more closely, it seems like you want to *choose a subset* of the input that has the desired property. Consider: what will you do if there is more than one valid subset? What will you do if there are no valid subsets? Also, please title your question in a way that reflects the *actual question*. – Karl Knechtel Dec 19 '21 at 08:39

1 Answers1

2

This is not really a sorting problem; it is a kind of search problem, since you're searching for a subset of the elements which satisfies some criteria.

You can solve it as follows. Sort the list normally, i.e. by first component (using the second component as a tie-breaker); then you are looking for an increasing subsequence in the second component. You can find a longest increasing subsequence using a standard algorithm. If this subsequence is not long enough, then there is no solution (so return None or raise an error); if it is longer than necessary, then simply slice it to the right size.

kaya3
  • 47,440
  • 4
  • 68
  • 97