Repository: sympy/sympy
Pull request: Fix: Bug in MinMax which returned an incorrect simplication which is not true for all ranges of the variables
<!-- Your title above should be a short description of what
was changed. Do not include the issue number in the title. -->

#### References to other Issues or PRs
<!-- If this pull request fixes an issue, write "Fixes #NNNN" in that exact
format, e.g. "Fixes #1234" (see
https://tinyurl.com/auto-closing for more information). Also, please
write a comment on that issue linking back to this pull request once it is
open. -->
Fixes #21399 

#### Brief description of what is fixed or changed
earlier, Max( Min(a, b), Min(a, b, c)) returned Min(a,b,c)
now, Max( Min(a, b), Min(a, b, c)) returns Min(a,b)

- Add test for the above fix
- Add the above example in doc

#### Other comments


#### Release Notes

<!-- Write the release notes for this release below between the BEGIN and END
statements. The basic format is a bulleted list with the name of the subpackage
and the release note for this PR. For example:

* solvers
  * Added a new solver for logarithmic equations.

* functions
  * Fixed a bug with log of integers.

or if no release note(s) should be included use:

NO ENTRY

See https://github.com/sympy/sympy/wiki/Writing-Release-Notes for more
information on how to write release notes. The bot will check your release
notes automatically to see if they are formatted correctly. -->

<!-- BEGIN RELEASE NOTES -->
* functions
   * Fixed a bug in MaxMin of elementary functions  
<!-- END RELEASE NOTES -->


Problem statement:
nested Max and Min give incorrect result
While working with different types of nested Max and Min expressions, I have encountered a problem in the following expression:
```
from sympy import sympify 
sympify( "Max( Min(a, b), Min(a, b, c))" )
```

output: `Min(a, b, c)`

This simplification is not correct for all possible values of a, b, and c.
I have not found any problems with other similar expressions, and I cannot find the specific reason why this one evaluates incorrectly.

Hints from issue discussion:
The issue isn't to do with sympify because it happens if you use Max/Min directly:
```python
In [1]: a, b, c = symbols('a, b, c')

In [2]: Max( Min(a, b), Min(a, b, c))
Out[2]: Min(a, b, c)
```
The logic for handling this is here:
https://github.com/sympy/sympy/blob/d43e9dc5aed4d2b695a3176cdf8ad4e3c79f0e5b/sympy/functions/elementary/miscellaneous.py#L515-L542
At the end here we have
```
(Pdb) p sets
[c]
(Pdb) p common
{b, a}
(Pdb) p cls
Max
(Pdb) p other
Min
(Pdb) p args
[Min(a, b, c)]
```
Thanks for pointing that out.

From my understanding, the code you quoted refactors `Max(Min(a, b), Min(a, b, c))` into `Min(a, b, Max(c))`, which then becomes `Min(a, b, c)`

A correct refactoring would be `Min(a, b)`, though I'm not sure how the code could be adapted to take this specific case into account.
I suppose one way to get there would be to realise that `Min(a, b) >= Min(a, b, c)` although that comparison isn't implemented. There must be a bug in here though to get this wrong result.

I'm just trying to get my head round how this `Max/Min` algebra works. The rule described in the code is
```
Min(Max(x, y), Max(x, z)) -> Max(x, Min(y, z)) 
```
which seems to be valid. Now we want to generalise to handle this:
```
Min(Max(a, b, c, d), Max(a, b, d, e))
```
The current implementation turns this into:
```python
In [4]: Min(Max(a, b, c, d), Max(a, b, e, f))
Out[4]: Max(a, b, Min(Max(c, d), Max(e, f)))
```

Applying that kind of reasoning to your case gives:
```
Max(Min(a, b), Min(a, b, c))  -> Min(a, b, Max(Min(), Min(c)))
```
Now the question is what a no arg `Min()` should be. If we suppose that `Min(a, b, c) <= Min(a, b)` then `Min(a) <= Min() = oo`. The simplification would then be:
```
Min(a, b, Max(Min(), Min(c))) -> Min(a, b, Max(oo, c)) -> Min(a, b, oo) -> Min(a, b)
```
The current code filters out a `Min` whose args are equal to the common subset so it simply removes `Min()`. Actually if any `Min` has args equal to common then I think it means that *all* `Min`s can be removed and the result is just `Min(*common)`.

Here is a diff that will fix this:
```diff
diff --git a/sympy/functions/elementary/miscellaneous.py b/sympy/functions/elementary/miscellaneous.py
index 85b606e754..c4d341501e 100644
--- a/sympy/functions/elementary/miscellaneous.py
+++ b/sympy/functions/elementary/miscellaneous.py
@@ -1,3 +1,4 @@
+from sympy.utilities.iterables import sift
 from sympy.core import Function, S, sympify
 from sympy.core.add import Add
 from sympy.core.containers import Tuple
@@ -518,28 +519,34 @@ def do(ai, a):
         # easy case where all functions contain something in common;
         # trying to find some optimal subset of args to modify takes
         # too long
+
+        def factor_minmax(args):
+            is_other = lambda arg: isinstance(arg, other)
+            other_args, remaining_args = sift(args, is_other, binary=True)
+            if not other_args:
+                return args
+
+            # Min(Max(x, y, z), Max(x, y, u, v)) -> {x,y}, ({z}, {u,v})
+            arg_sets = [set(arg.args) for arg in other_args]
+            common = set.intersection(*arg_sets)
+            if not common:
+                return args
+
+            new_other_args = list(common)
+            arg_sets_diff = [arg_set - common for arg_set in arg_sets]
+
+            # If any set is empty after removing common then all can be
+            # discarded e.g. Min(Max(a, b, c), Max(a, b)) -> Max(a, b)
+            if all(arg_sets_diff):
+                other_args_diff = [other(*s, evaluate=False) for s in arg_sets_diff]
+                new_other_args.append(cls(*other_args_diff, evaluate=False))
+
+            other_args_factored = other(*new_other_args, evaluate=False)
+            return remaining_args + [other_args_factored]
+
+
         if len(args) > 1:
-            common = None
-            remove = []
-            sets = []
-            for i in range(len(args)):
-                a = args[i]
-                if not isinstance(a, other):
-                    continue
-                s = set(a.args)
-                common = s if common is None else (common & s)
-                if not common:
-                    break
-                sets.append(s)
-                remove.append(i)
-            if common:
-                sets = filter(None, [s - common for s in sets])
-                sets = [other(*s, evaluate=False) for s in sets]
-                for i in reversed(remove):
-                    args.pop(i)
-                oargs = [cls(*sets)] if sets else []
-                oargs.extend(common)
-                args.append(other(*oargs, evaluate=False))
+            args = factor_minmax(args)
 
         return args
 
```

Commit message: Fix: Bug in MinMax which returned an incorrect simplication which is not true for all ranges of the variables
earlier, Max( Min(a, b), Min(a, b, c)) returned Min(a,b,c)
now, Max( Min(a, b), Min(a, b, c)) returns Min(a,b)

- Add test for the above fix
- Add the above example in doc

Patch to review:
diff --git a/sympy/functions/elementary/miscellaneous.py b/sympy/functions/elementary/miscellaneous.py
index 85b606e754bc..94067844ee0e 100644
--- a/sympy/functions/elementary/miscellaneous.py
+++ b/sympy/functions/elementary/miscellaneous.py
@@ -1,4 +1,5 @@
 from sympy.core import Function, S, sympify
+from sympy.utilities.iterables import sift
 from sympy.core.add import Add
 from sympy.core.containers import Tuple
 from sympy.core.compatibility import ordered
@@ -432,7 +433,8 @@ def _collapse_arguments(cls, args, **assumptions):
 
         >>> Min(a, Max(b, Min(c, d, Max(a, e))))
         Min(a, Max(b, Min(a, c, d)))
-
+        >>> Max( Min(a, b), Min(a, b, c))
+        Min(a,b)
         """
         from sympy.utilities.iterables import ordered
         from sympy.simplify.simplify import walk
@@ -518,28 +520,33 @@ def do(ai, a):
         # easy case where all functions contain something in common;
         # trying to find some optimal subset of args to modify takes
         # too long
+
+        def factor_minmax(args):
+            is_other = lambda arg: isinstance(arg, other)
+            other_args, remaining_args = sift(args, is_other, binary=True)
+            if not other_args:
+                return args
+
+            # Min(Max(x, y, z), Max(x, y, u, v)) -> {x,y}, ({z}, {u,v})
+            arg_sets = [set(arg.args) for arg in other_args]
+            common = set.intersection(*arg_sets)
+            if not common:
+                return args
+
+            new_other_args = list(common)
+            arg_sets_diff = [arg_set - common for arg_set in arg_sets]
+
+            # If any set is empty after removing common then all can be
+            # discarded e.g. Min(Max(a, b, c), Max(a, b)) -> Max(a, b)
+            if all(arg_sets_diff):
+                other_args_diff = [other(*s, evaluate=False) for s in arg_sets_diff]
+                new_other_args.append(cls(*other_args_diff, evaluate=False))
+
+            other_args_factored = other(*new_other_args, evaluate=False)
+            return remaining_args + [other_args_factored]
+
         if len(args) > 1:
-            common = None
-            remove = []
-            sets = []
-            for i in range(len(args)):
-                a = args[i]
-                if not isinstance(a, other):
-                    continue
-                s = set(a.args)
-                common = s if common is None else (common & s)
-                if not common:
-                    break
-                sets.append(s)
-                remove.append(i)
-            if common:
-                sets = filter(None, [s - common for s in sets])
-                sets = [other(*s, evaluate=False) for s in sets]
-                for i in reversed(remove):
-                    args.pop(i)
-                oargs = [cls(*sets)] if sets else []
-                oargs.extend(common)
-                args.append(other(*oargs, evaluate=False))
+            args = factor_minmax(args)
 
         return args
 
diff --git a/sympy/functions/elementary/tests/test_miscellaneous.py b/sympy/functions/elementary/tests/test_miscellaneous.py
index 0e1a5b1d08ce..2f6e16977967 100644
--- a/sympy/functions/elementary/tests/test_miscellaneous.py
+++ b/sympy/functions/elementary/tests/test_miscellaneous.py
@@ -410,6 +410,10 @@ def test_issue_12638():
     assert Min(a, b, Max(a, b, c)) == Min(a, b)
     assert Min(a, b, Max(a, c)) == Min(a, b)
 
+def test_issue_21399():
+    from sympy.abc import a, b, c
+    assert Max( Min(a, b), Min(a, b, c)) == Min(a,b)
+
 
 def test_instantiation_evaluation():
     from sympy.abc import v, w, x, y, z


Code review comments:
diff_hunk: @@ -432,7 +433,8 @@ def _collapse_arguments(cls, args, **assumptions):
 
         >>> Min(a, Max(b, Min(c, d, Max(a, e))))
         Min(a, Max(b, Min(a, c, d)))
-
+        >>> Max( Min(a, b), Min(a, b, c))
+        Min(a,b)
path: sympy/functions/elementary/miscellaneous.py
text: @user1:
```suggestion
```

diff_hunk: @@ -432,7 +433,8 @@ def _collapse_arguments(cls, args, **assumptions):
 
         >>> Min(a, Max(b, Min(c, d, Max(a, e))))
         Min(a, Max(b, Min(a, c, d)))
-
+        >>> Max( Min(a, b), Min(a, b, c))
+        Min(a,b)
path: sympy/functions/elementary/miscellaneous.py
text: @user1:
I don't think that an example needs to be added here.

diff_hunk: @@ -410,6 +410,10 @@ def test_issue_12638():
     assert Min(a, b, Max(a, b, c)) == Min(a, b)
     assert Min(a, b, Max(a, c)) == Min(a, b)
 
+def test_issue_21399():
+    from sympy.abc import a, b, c
+    assert Max( Min(a, b), Min(a, b, c)) == Min(a,b)
path: sympy/functions/elementary/tests/test_miscellaneous.py
text: @user1:
```suggestion
    assert Max(Min(a, b), Min(a, b, c)) == Min(a, b)
```