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:
I also suspect that you cannot expect the equality to hold in the presence of tied CV scores.

To deal with tied results and avoid having them introduce a bias that depends on an arbitrary ordering of the parameter grid, the best thing we could do would be to add an option to randomize the parameter grid iteration. However, I am not 100% sure the added code complexity would be justified.

Labels: Bug, Needs Investigation