HalvingGridSearchCV should not care about parameter-grid layout but apparently does

### Describe the bug

I have two parameter-grid layouts, both specifying the exact same set of configurations. The difference is that the choices are listed in a different order, e.g., [False, True] versus [True, False]. My understanding is that this should not matter given that HalvingGridSearchCV tries all configurations on the first step. However, I get different results when using first grid versus the second.

### Steps/Code to Reproduce

```python
import numpy as np
from sklearn.svm import SVC
from sklearn.experimental import enable_halving_search_cv
from sklearn.model_selection import HalvingGridSearchCV

#three grids with identical configuration space

svc_grid_1 = dict(C=[1,2,3],
                gamma=['auto', 'scale'],
                shrinking=(True, False),
                kernel=['sigmoid', 'linear', 'poly', 'rbf'],
                max_iter = [5000, 10000, -1]
                )

svc_grid_2 = dict(C=[1,2,3],
                gamma=['auto', 'scale'],
                shrinking=(True, False),
                kernel=['rbf', 'poly', 'linear',  'sigmoid'],  #reordered choices
                max_iter = [5000, 10000, -1]
                )

svc_grid_3 = dict(kernel=['sigmoid', 'linear', 'poly', 'rbf'],  #reordered keys
                  C=[1,2,3],
                  shrinking=(True, False),
                  max_iter = [5000, 10000, -1],
                  gamma=['auto', 'scale'],
                )

###How many different combinations?

from sklearn.model_selection import ParameterGrid
param_grid_1 = ParameterGrid(svc_grid_1)  #a list of dictionaries, one for each combo
print(f'{len(param_grid_1)=}')  #144
param_grid_2 = ParameterGrid(svc_grid_2)  #a list of dictionaries, one for each combo
print(f'{len(param_grid_1)=}')  #144
param_grid_3 = ParameterGrid(svc_grid_3)  #a list of dictionaries, one for each combo
print(f'{len(param_grid_1)=}')  #144

all([d in param_grid_2 and d in param_grid_3 for d in param_grid_1])  #True

#random data

np.random.seed(0)
n_samples, n_features = 1313, 6
x_train = np.random.rand(n_samples, n_features)
y_train = np.random.randint(0, 2, n_samples)  # binary target with values in {0, 1}

#Try Grid 1

svc_model = SVC(probability=True, random_state=1)  #base model
min_res = 30

#do the grid search
halving_cv = HalvingGridSearchCV(
    svc_model, svc_grid_1,  
    scoring="roc_auc",  
    n_jobs=1,  
    min_resources=min_res,
    factor=2,  
    cv=5, random_state=1234,
    refit=True,  
)

grid_result_1 = halving_cv.fit(x_train, y_train)
grid_result_1.best_params_ 
#{'C': 1,
# 'gamma': 'scale',
# 'kernel': 'sigmoid',
# 'max_iter': -1,
# 'shrinking': True}

#Try grid 2

svc_model = SVC(probability=True, random_state=1)  #base model

min_res = 30

#do the grid search
halving_cv = HalvingGridSearchCV(
    svc_model, svc_grid_2,  
    scoring="roc_auc", 
    n_jobs=1,  
    min_resources=min_res,
    factor=2, 
    cv=5, random_state=1234,
    refit=True, 
)

grid_result_2 = halving_cv.fit(x_train, y_train)
grid_result_2.best_params_ 
#{'C': 1,
 #'gamma': 'scale',
 #'kernel': 'sigmoid',
 #'max_iter': 5000,
 #'shrinking': True}

set(grid_result_1.best_params_.values()) == set(grid_result_2.best_params_.values())  #False
```
### Expected Results

best_params_  would be same for both grids

### Actual Results

They are different.

### Versions

```shell
System:
    python: 3.10.12 (main, Jun 11 2023, 05:26:28) [GCC 11.4.0]
executable: /usr/bin/python3
   machine: Linux-5.15.120+-x86_64-with-glibc2.35

Python dependencies:
      sklearn: 1.2.2
          pip: 23.1.2
   setuptools: 67.7.2
        numpy: 1.23.5
        scipy: 1.11.3
       Cython: 3.0.4
       pandas: 1.5.3
   matplotlib: 3.7.1
       joblib: 1.3.2
threadpoolctl: 3.2.0

Built with OpenMP: True

threadpoolctl info:
       user_api: blas
   internal_api: openblas
    num_threads: 8
         prefix: libopenblas
       filepath: /usr/local/lib/python3.10/dist-packages/numpy.libs/libopenblas64_p-r0-742d56dc.3.20.so
        version: 0.3.20
threading_layer: pthreads
   architecture: Haswell

       user_api: openmp
   internal_api: openmp
    num_threads: 8
         prefix: libgomp
       filepath: /usr/local/lib/python3.10/dist-packages/scikit_learn.libs/libgomp-a34b3233.so.1.0.0
        version: None

       user_api: blas
   internal_api: openblas
    num_threads: 8
         prefix: libopenblas
       filepath: /usr/local/lib/python3.10/dist-packages/scipy.libs/libopenblasp-r0-23e5df77.3.21.dev.so
        version: 0.3.21.dev
threading_layer: pthreads
   architecture: Haswell
```

COMMENT:
So randomizing parameter grid in this case would make it certain that in this particular case the output varies, and preordering the grid is also not sounding like a good idea.

What we could do, is in cases of ties, if we're still not at the end of the search, pick all ties for the next round, instead of only one. However, it would require investigation as whether that would fix the issue of whether that really is the core of the issue.

Labels: Bug, Needs Investigation