StratifiedGroupKFold(shuffle=True) breaks group-index mapping, leading to incorrect (effectively random) group assignments per fold

### Describe the bug

When `StratifiedGroupKFold` is instantiated with `shuffle=True`, the implementation shuffles the `y_counts_per_group` array **without** updating the associated `groups_inv` mapping. This decouples the internal row index used for each group’s class-count vector from the actual group IDs of the samples. The greedy assignment that follows then optimizes fold balance using indices of the **shuffled** `y_counts_per_group`, but later, when building `test_indices`, membership is checked against the **unshuffled** `groups_inv`. As a result, the reported groups in each test split correspond to a random permutation of the groups the greedy algorithm actually balanced, and the intended stratification by `y` is lost; in effect, with `shuffle=True` the splitter behaves like a `GroupKFold` (non-stratified) rather than a stratified group split.

### Steps/Code to Reproduce

```python
import numpy as np
from sklearn.model_selection import StratifiedGroupKFold

X = np.ones((18, 2))
y = np.array([0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1])
groups = np.array([1, 1, 2, 2, 3, 3, 3, 4, 5, 5, 5, 5, 6, 6, 7, 7, 8, 8])

sgkf = StratifiedGroupKFold(n_splits=3, shuffle=True, random_state=42)
for i, (_, test_idx) in enumerate(sgkf.split(X, y, groups)):
    print(
        f"Fold {i}: groups {np.unique(groups[test_idx])}, "
        f"positive class ratio {y[test_idx].mean():.3f}"
    )

sgkf = StratifiedGroupKFold(n_splits=3, shuffle=False, random_state=None)
for i, (_, test_idx) in enumerate(sgkf.split(X, y, groups)):
    print(
        f"Fold {i}: groups {np.unique(groups[test_idx])}, "
        f"positive class ratio {y[test_idx].mean():.3f}"
    )
```
Results with `shuffle=True` and `random_state=42`:
Fold 0: groups `[4 6]`, positive class ratio `0.667`
Fold 1: groups `[2 5 7]`, positive class ratio `0.250`
Fold 2: groups `[1 3 8]`, positive class ratio `0.286`

Results without shuffle:
Fold 0: groups `[5 8]`, positive class ratio `0.333`
Fold 1: groups `[3 4 6]`, positive class ratio `0.333`
Fold 2: groups `[1 2 7]`, positive class ratio `0.333`

### Expected Results

With `shuffle=True`, the `rng.shuffle(y_counts_per_group)` happens **before** computing per-group class-count variances and the subsequent stable sort. Because a stable sort is used, the shuffle should act **only as a tie-breaker among groups with exactly the same variance**; it should not reorder groups that have different variances. Crucially, the permutation applied to `y_counts_per_group` must be mirrored in `groups_inv` so that the mapping from matrix rows to true group IDs remains consistent. Under this condition, the groups reported in each test fold will be exactly those selected by the greedy algorithm, and stratification quality should be comparable to the `shuffle=False` case.
For the provided example (overall positive rate = 6/18 = 0.333), a perfectly stratified solution exists (as shown by the `shuffle=False` run yielding `0.333, 0.333, 0.333`), and with `shuffle=True` we would expect a (possibly different) grouping but still ~`0.333` per fold.


### Actual Results

With `shuffle=True` and `random_state=42`, the reported folds are:
Fold 0: groups `[4 6]`, positive class ratio `0.667`
Fold 1: groups `[2 5 7]`, positive class ratio `0.250`
Fold 2: groups `[1 3 8]`, positive class ratio `0.286`

These deviations indicate that stratification is not respected. The reason is that `y_counts_per_group` is shuffled **without** remapping `groups_inv`. As a result, even though the stable sort limits the shuffle’s effect to tie-breaking among equal-variance groups, the greedy assignment then operates on a **permuted** matrix whose row indices no longer correspond to the true group IDs. When building `test_indices`, membership is checked against the obsolete `groups_inv`, producing folds whose group sets are, in practice, a random permutation of those intended by the greedy algorithm; that is, in practice, the splitter behaves like a non-stratified `GroupKFold`.

### Versions

```shell
System:
    python: 3.12.11 | packaged by Anaconda, Inc. | (main, Jun  5 2025, 13:09:17) [GCC 11.2.0]
executable: /home/pfolch/anaconda3/envs/ecos/bin/python
   machine: Linux-6.6.87.2-microsoft-standard-WSL2-x86_64-with-glibc2.39

Python dependencies:
      sklearn: 1.7.2
          pip: 25.2
   setuptools: 80.9.0
        numpy: 2.2.6
        scipy: 1.16.2
       Cython: None
       pandas: 2.3.2
   matplotlib: 3.10.6
       joblib: 1.5.2
threadpoolctl: 3.6.0

Built with OpenMP: True

threadpoolctl info:
       user_api: blas
   internal_api: openblas
    num_threads: 24
         prefix: libscipy_openblas
       filepath: /home/pfolch/anaconda3/envs/ecos/lib/python3.12/site-packages/numpy.libs/libscipy_openblas64_-56d6093b.so
        version: 0.3.29
threading_layer: pthreads
   architecture: SkylakeX

       user_api: openmp
   internal_api: openmp
    num_threads: 12
         prefix: libgomp
       filepath: /home/pfolch/anaconda3/envs/ecos/lib/python3.12/site-packages/torch/lib/libgomp.so.1
        version: None

       user_api: blas
   internal_api: openblas
    num_threads: 24
         prefix: libscipy_openblas
       filepath: /home/pfolch/anaconda3/envs/ecos/lib/python3.12/site-packages/scipy.libs/libscipy_openblas-b75cc656.so
        version: 0.3.29.dev
threading_layer: pthreads
   architecture: SkylakeX

       user_api: openmp
   internal_api: openmp
    num_threads: 24
         prefix: libgomp
       filepath: /home/pfolch/anaconda3/envs/ecos/lib/python3.12/site-packages/scikit_learn.libs/libgomp-a34b3233.so.1.0.0
        version: None
```

COMMENT:
Related to [#24656](https://github.com/scikit-learn/scikit-learn/issues/24656).

Quick note: I opened this as a separate issue because [#24656](https://github.com/scikit-learn/scikit-learn/issues/24656) proposes an algorithmic improvement (replacing the current greedy heuristic with a local-search procedure), whereas this report is a **concise correctness bug** in the existing implementation that appears when `shuffle=True`.

In short, the code shuffles `y_counts_per_group` **without** remapping `groups_inv`, breaking the mapping between each row of the class-count matrix and the true group IDs. The greedy assignment then optimizes on permuted rows that no longer correspond to real groups, and the reported test folds effectively behave like a non-stratified `GroupKFold`. Repro and expected/actual details are in the description above.

A minimal, self-contained fix is to apply the same permutation to `groups_inv`:
```python
if self.shuffle:
    perm = np.arange(len(groups_cnt))
    rng.shuffle(perm)
    y_counts_per_group = y_counts_per_group[perm]
    inv_perm = np.empty(perm.size, perm.dtype)
    inv_perm[perm] = np.arange(perm.size)
    groups_inv = inv_perm[groups_inv]
```
I filed this separately to keep the scope small and make it easier to review/merge independently of any broader redesign, with the hope that **the correctness bug in the current implementation can be addressed independently**. Happy to close as a duplicate and track under [#24656](https://github.com/scikit-learn/scikit-learn/issues/24656) if maintainers prefer; I mainly wanted to highlight that this is a correctness bug, not a feature request. If helpful, I can open a PR with a failing test and the fix.

Labels: Bug