Problème invariant algorithme drapeau

Bonjour à tous, je bloque depuis hier sur un l'algorithme des drapeaux ,qui consiste à remettre dans l'ordre n boules blanches,rouges et bleues afin d'avoir les bleues en tête ,les blanches au milieu et les rouges à la fin par échanges successifs de boules prises deux à deux ,tout ceci en faisant le moins d'échanges possibles.
Dans cet exercice on doit écrire ce programme qui respecte l'invariant suivant :
- Si 1<=i<r1 alors couleur(i)=bleu
- Si r1<=i<r2 alors couleur(i)=blanc
- Si r3<i<=n alors couleur(i)=rouge
Mon idée de base après avoir un peu cherché était de fixer r1=1 ,r2=1 et r3=n au début puis faire varier r2 jusqu'à ce que r2=r3 ,sauf que cette solution ne respecte pas l'invariant puisque que r1>1 selon l'invariant. et je n'arrive pas à trouver des solutions qui respectent cet invariant ,donc si vous avez des idées je suis preneur. Sur ce bonne après-midi .

Vu que tu connais les valeurs $r_1$, $r_2$ et $r_3$, tu connais a l'avance la position des boules. Tu peux donc déterminer, pour chaque boule si elle est bien placée ou non.

Tant qu'il y a des boules mal placées.

1. Si il existe deux boules mal placées dont l'inversion les placerait¹ au bon endroit, faire cette inversion. (ex: Une boule bleue dans la zone blanche et une boule blanche dans la zone bleue.)
2. Sinon, intervertir deux boules mal placées prise¹ au hasard.

J'ai pas la preuve que ça marche. Mais vu qu'on a que 3 catégories, intervertir deux boules a l'étape (2) en place forcément une qui respecte la condition en (1).

Le problème c'est que ta deuxième condition ne respecte pas forcément l'invariant ,et l'on ne connait pas r1,r2,r3 à l'avance il faut les trouver de façon à ce qu'ils respectent l'invariant.Mais merci quand même.
PS : c'est bien "placerait" car c'est "l'inversion" qui est le sujet et "prises" avec "s"

Si tu ne peux pas compter les boules de chaque couleur avant de les trier, il va falloir utiliser un algorithme de tri. Si t'es obligé de n'intervertir que deux boules à la fois, tu vas devoir faire un tri en place.

Le problème c'est que ta deuxième condition ne respecte pas forcément l'invariant

Je suis pas sûr mais, avec la boucle while, je pense que, à la fin, les boules seront triés.

Je pense qu'on peut les compter ,le problème c'est que l'invariant doit être vérifié dès le début du programme. Parce que le problème c'est l'invariant je ne sais pas quelles valeurs je dois affectés à r1,r2,r3 au début du programme pour que l'invariant soit vérifié.

Tu pourrais passer l'énoncé précis du problème stp? Parce que là, je comprends pas ce qu'il faut faire.

Voilà l'énoncé (Drapeau) désolé s'il est un peu flou :/
Enoncé Drapeau

J'ai réussi à résoudre mon problème en posant comme conditions initiales sur r1,r2,r3 que : r1=0
r2=0 r3=n
Le problème est résolu dès que r2=r3
De là j'ai décidé de déplacer mon index r2 entre 0 et r3 (puisque c'est la zone qui n'est pas triée ) avec une boucle.
Du coup je met le code si ça peut servir on ne sait jamais . Après grâce à l'invariant j'ai déduit les conditions pour les déplacements et les permutations.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

import random
Taille=10
def retour_liste_initialise():
    type_boules={0:"Bleu",1:"Blanc",2:"Rouge"}
    liste=[]
    for i in range(Taille):
        liste.append([type_boules.get(random.randint(0,2))])
    return liste

#On échange les valeurs (valeur_1=valeur_2 et valeur_2=valeur_1)
def echanger_valeur(valeur_1,valeur_2):
    valeur_temporaire=valeur_1[0]
    valeur_1[0]=valeur_2[0]
    valeur_2[0]=valeur_temporaire


liste=retour_liste_initialise()
#Valeurs initialisées r1,r2,r3
r1,r2=0,0
r3=len(liste)-1
while r2!=r3:
    if liste[r2][0]=="Blanc":
        r2+=1
    elif liste[r2][0]=="Bleu":
        echanger_valeur(liste[r2],liste[r1])
        r1,r2=r1+1,r2+1
    else:
        echanger_valeur(liste[r2],liste[r3])
        r3-=1
    print(liste)

Merci quand même à ceux qui m'ont aidé