Project

General

Profile

Feature #1535

New functions: argmin, argmax

Added by John Abbott over 3 years ago. Updated over 3 years ago.

Status:
In Progress
Priority:
Normal
Assignee:
-
Category:
CoCoA-5 function: new
Target version:
CoCoA-5.4.2
Start date:
11 Nov 2020
Due date:
% Done:

10%

Estimated time:
Spent time:
0.70 h

Description

Proposal:
create new functions argmin and argmax which operate on lists.

The idea is that they return an/all elements in a list which minimize/maximize a given fn.
For example,

L := [-2,-1,0,1,2];
argmax(L, func(x) return abs(x) endfunc);
[-2,2]

Perhaps there could also be argmin_first and argmax_first which return just the first entry which minimizes/maximizes...

Discuss..., maybe implement.

Related issues

Related to CoCoA-5 - Feature #1372: New function: find ?In Progress2019-11-29

History

#1 Updated by John Abbott over 3 years ago

  • Status changed from New to In Progress
  • % Done changed from 0 to 10

Here is a first prototype in CoCoA-5

define argmin(L, fn)
  if L = [] then error("empty list"); endif;
  indices := [1];
  BestVal := fn(L[1]);
  for j := 2 to len(L) do
    CurrVal := fn(L[j]);
    if CurrVal > BestVal then continue; endif;
    if CurrVal < BestVal then BestVal := CurrVal; indices := [j]; continue; endif;
    append(ref indices, j);
  endfor;
  return [L[i] | i in indices];
enddefine; -- argmin

define argmin_first(L, fn)
  if L = [] then error("empty list"); endif;
  index := 1;
  BestVal := fn(L[1]);
  for j := 2 to len(L) do
    CurrVal := fn(L[j]);
    if CurrVal > BestVal then continue; endif;
    if CurrVal < BestVal then BestVal := CurrVal; index := j; continue; endif;
  endfor;
  return L[index];
enddefine; -- argmin_first

#2 Updated by John Abbott over 3 years ago

Should this actually be in CoCoALib?

Might it be handy to have a version which returns the index (or indices) of the relevant elements?
Then the impls above become one-liners:

define argmin_first(L,fn)
  return L[argmin_first_index(L,fn)];
enddefine;

#3 Updated by John Abbott over 3 years ago

What should the names be?
In most contexts they are written argmin (or maybe arg min with a space).
Should be use argmin or ArgMin? :-/

#4 Updated by Julian Danner over 3 years ago

I clearly prefer argmin, since its easier to type and lower-case is also more common in mathematics, but (as for many other functions) you could offer both variants.

#5 Updated by John Abbott over 3 years ago

Here is a little background/motivation.
I demoed to the students how one can impl in CoCoA-5 the algm to compute a min basis for a monoideal in PP monoid.
At one point one should pick a PP of minimal degree from a list/set. How to do this neatly in CoCoA-5?

  G := list of PPs;
  D := [deg(g) | g in G];
  MinDeg := min(D);
  GoodPPs := [g in G | deg(g) = MinDeg];
  t := GoodPPs[1]; // we know that GoodPPs is not empty

Yes, of course, I can make this shorter (but not clearer). Also as written it computes deg(g) twice for each g in G.

With argmin_first this would become a single line:

  t := argmin_first(G, deg);

and deg is evaluated only once for each element!

#6 Updated by Anna Maria Bigatti over 3 years ago

I like the idea. We need another mane for the funzion with indices.

#7 Updated by John Abbott over 2 years ago

Also available in: Atom PDF