problème algo boulot

**gotax** · 05/09/2024, 13h35

Salut a tous,

tout est dans le titre. J'ai de tres serieux problemes de logique, ca veut pas rentrer dans ma tete, et si ca rentre c'est par par coeurisme a force de refaire 10 fois le meme exercice.
La pour le boulot j'ai un algorithme a faire et je suis coincé. en gros voici le probleme:

J'ai une table contratComponent avec une colonne ordre (int). j'ai plusieurs contrats avec leurs numeros d'ordre. je dois pouvoir modifier l'ordre.

ex. liste de 5 components.
components = [
{id: "comp1", order: 1},
{id: "comp2", order: 2},
{id: "comp3", order: 3},
{id: "comp4", order: 4}.
{id: "comp5", order: 5}
];
le component a changer est comp2 qui avait order = 2 et maintenant son newOrder = 3

{id: "comp2", order: 2} > {id: "comp2", order: 3}
1) liste triee avec comp2 enlevé:

components = [
{id: "comp1", order: 1},
{id: "comp3", order: 3},
{id: "comp4", order: 4}.
{id: "comp5", order: 5}
];

2) je decremente les ordres qui viennent apres comp2

components = [
{id: "comp1", order: 1},
{id: "comp3", order: 2},
{id: "comp4", order: 3}.
{id: "comp5", order: 4}
];

3) dans la liste il y avait deja un order = 3

{id: "comp3", order: 3} (qui est devenu {id: "comp3", order: 2})

4) donc j'incremente les order suivants

components = [
{id: "comp1", order: 1},
{id: "comp3", order: 2},
{id: "comp4", order: 4}.
{id: "comp5", order: 5}
];

5) je reinsere le component comp2 avec le newOrder:

components = [
{id: "comp1", order: 1},
{id: "comp3", order: 2},
{id: "comp2", order: 3},
{id: "comp4", order: 4}.
{id: "comp5", order: 5}
];

moi j'ai fait ca:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
31
32
33
34
35
36
37
38
39
40
41
42
43
public void SetOrder(ref Contract contract, Guid contractComponentId, int newOrder)
{
    ContractComponent? componentToMove = contract.ContractComponents
        .FirstOrDefault(c => c.Id == contractComponentId);
 
    List<ContractComponent> componentsListWithoutComponentToMove = contract.ContractComponents
        .Where(c => c.Id != contractComponentId)
        .OrderBy(c => c.Order)
        .ToList();
 
    if (componentToMove == null) return;
 
    int oldOrder = componentToMove.Order;
    //if (oldOrder == newOrder) return;
 
    if (newOrder > oldOrder)
    {
        foreach (var component in componentsListWithoutComponentToMove
            .Where(c => c.Order > oldOrder && c.Order <= newOrder))
        {
            component.Order -= 1;
        }
    }
    else
    {
        foreach (var component in componentsListWithoutComponentToMove
            .Where(c => c.Order >= newOrder && c.Order < oldOrder))
        {
            component.Order += 1;
        }
    }
 
    componentToMove.Order = newOrder;
 
    componentsListWithoutComponentToMove.Add(componentToMove);
 
    componentsListWithoutComponentToMove = componentsListWithoutComponentToMove
        .OrderBy(c => c.Order)
        .ToList();
 
    contract.ContractComponents = componentsListWithoutComponentToMove;
 
}

sauf que des l'entree de ma methode le contractComponent que je veux modifer a deja le newOrder et donc l'algo ne marche pas. Vous avez une idee de comment faire? Je suis desespere

**kaitlyn** · 05/09/2024, 19h42

Salut,

Un problème de logique, n'exagérons rien. Qu'est-ce qui t'a amené à l'algo que tu présentes.
A-t-il un nom, d'où vient-il ? N'y avait-il rien de plus adapté dans la librairie (genre file de priorité (priority queue)) ?

Est-ce que tes ordres sont uniques et se suivent (1,2,3,...) ? Si oui, est-ce que supprimer ton composant de ta liste triée pour le réinsérer à la position de ton choix, puis recalculer tes ordres (entre la position de départ et d'arrivée), ça pourrait faire l'affaire ?

**gotax** · 05/09/2024, 21h55

salut,

merci pour ta contribution. Alors l'exemple que j'ai donné m'a ete donné par mon boss, c'est ce qu'il veut que je fasse.

Est-ce que tes ordres sont uniques et se suivent (1,2,3,...) ? Si oui, est-ce que supprimer ton composant de ta liste triée pour le réinsérer à la position de ton choix, puis recalculer tes ordres (entre la position de départ et d'arrivée), ça pourrait faire l'affaire ?

Oui je pense que c'est ca mais je sais pas le faire. j'ai pondu ca en essayant de suivre son exemple mais c'est pas bon:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
public void SetOrder(ref Contract contract, Guid contractComponentId, int newOrder)
{
    // je get mon composant
    ContractComponent? componentToMove = contract.ContractComponents
        .FirstOrDefault(c => c.Id == contractComponentId);
 
    if (componentToMove == null) return; 
 
    // liste des composants sans mon composant
    List<ContractComponent> componentsListWithoutComponentToMove = contract.ContractComponents
        .Where(c => c.Id != contractComponentId)
        .OrderBy(c => c.Order)
        .ToList();
 
    // je decremente les composants qui viennent apres le miens
    foreach (var contractComponent in componentsListWithoutComponentToMove)
    {
        if(contractComponent.Order > componentToMove.Order)
        {
            contractComponent.Order -= 1;
 
        }
    }
 
    //j'incremente les composants qui viennent apres le miens
    foreach (var contractComponent in componentsListWithoutComponentToMove)
    {
        if (contractComponent.Order == newOrder || contractComponent.Order > newOrder)
        {
            contractComponent.Order += 1;
        }
    }
 
    //je decremente les composants qui viennent apres le miens
    foreach (var contractComponent in componentsListWithoutComponentToMove)
    {
        if (contractComponent.Order == newOrder || contractComponent.Order < newOrder)
        {
            contractComponent.Order -= 1;
            if (contractComponent.Order == 1)
            {
                contractComponent.Order = 1;
            }
        }
    }
 
    componentToMove.Order = newOrder;
 
    // je remets le composant dans la liste
    componentsListWithoutComponentToMove.Add(componentToMove);
 
    // je trie la liste
    componentsListWithoutComponentToMove = componentsListWithoutComponentToMove
        .OrderBy(c => c.Order)
        .ToList();
 
    // je mets a jour la liste des composants
    contract.ContractComponents = componentsListWithoutComponentToMove;
}

**kaitlyn** · 05/09/2024, 23h09

Je ne connais pas csharp, mais je vois que tu utilises une collection list, elle propose les méthodes RemoveAt() et Insert(), laisse la faire le travail pour toi.

essaye :

Code pseudo-code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
//on suppose mylist triée, sinon le faire.
//mylist.sort_by_order()
 
index_of_contractComponentId= order_of_contractComponentId - 1; // car l'index commence à 0 (order - 1)
mylist.RemoveAt(index_of_contractComponentId);
 
new_index_of_contractComponentId= newOrder - 1;
mylist.Insert(new_index_of_contractComponentId, {contractComponentId, newOrder});
 
index_min= Min(index_of_contractComponentId, new_index_of_contractComponentId);
index_max= Max(index_of_contractComponentId, new_index_of_contractComponentId);
for index= index_min to index_max
    mylist[index].Order= index + 1;

**gotax** · 05/09/2024, 23h40

ok je vais essayer si ca marche.

**tbc92** · 06/09/2024, 00h42

ok, je viens de comprendre cette phrase, en tout cas, je pense : sauf que des l'entree de ma methode le contractComponent que je veux modifer a deja le newOrder et donc l'algo ne marche pas

En fait, il y a une autre procédure qui tourne AVANT tout ça, et qui modifie la valeur Order pour le ContractComponent à déplacer.
Et donc l'instruction en ligne 13 oldOrder = componentToMove.Order; renvoie une valeur fausse, elle renvoie NewOrder.

Le reste de ton programme me paraît correct ; on ne va pas le réécrire. Mais à la place de cette ligne 13, il va falloir trouver un truc pour calculer oldOrder.

en ligne 13, tu auras donc int oldOrder = CalculeOldOrder(componentsListWithoutComponentToMove )

Et ta procédure CalculeOldOrder pourrait être quelque chose du genre (pseudo code, je ne connais pas du tout la syntaxe de ton langage) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
procédure  CalculeOldOrder (componentsListWithoutComponentToMove )
i=1
fini = False 
tantque fini = False
    faire une boucle pour voir si il y a un élément tel que Order=i
    si oui alors 
       i=i+1
    sinon
       return (i)
    fin
fin

Dans tout ça, on suppose que les n°s Order sont tous utilisés.

Edit : je n'avais pas vu tous les messages ... la piste de Kaitlyn me semble plus professionnelle que notre bricolage.

**gotax** · 06/09/2024, 11h20

alors en fait le lead m'a dit que c'est normal que le contractComponentToMove ait la nouvelle valeur de Order (newOrder).

@ Kaitlyn: j'ai essayé ta solution:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
//on suppose mylist triée, sinon le faire.
//mylist.sort_by_order()
 
index_of_contractComponentId= order_of_contractComponentId - 1; // car l'index commence à 0 (order - 1)
mylist.RemoveAt(index_of_contractComponentId);
 
new_index_of_contractComponentId= newOrder - 1;
mylist.Insert(new_index_of_contractComponentId, {contractComponentId, newOrder});
 
index_min= Min(index_of_contractComponentId, new_index_of_contractComponentId);
index_max= Max(index_of_contractComponentId, new_index_of_contractComponentId);
for index= index_min to index_max
    mylist[index].Order= index + 1;

malheureusement elle marche pas:

j'ai dans ma bdd 3 components:

component 1: ordre 1
component 2: ordre 2
component 3: ordre 3

je veux donner l'ordre 3 au component 1.

en appliquant ton code le resultat est:
component 1 : ordre 3
component 2: ordre 2
component 3: ordre 2

ce qui est pas bon

**mathieu** · 06/09/2024, 11h26

Envoyé par gotax

ex. liste de 5 components.
components = [
{id: "comp1", order: 1},
{id: "comp2", order: 2},
{id: "comp3", order: 3},
{id: "comp4", order: 4}.
{id: "comp5", order: 5}
];
le component a changer est comp2 qui avait order = 2 et maintenant son newOrder = 3

dans cet exemple, le changement d'ordre est que comp2 va au rang 3 donc comp3 va à l'ancienne place de comp2 et donc au final comp3 est au rang 2 ?
si c'est bien ça, je dirais qu'il suffit d'échanger le rang avec le "comp" qui est déjà à la place du rang de destination.

**kaitlyn** · 06/09/2024, 11h57

Envoyé par gotax

@ Kaitlyn: j'ai essayé ta solution:
.../...
malheureusement elle marche pas:

j'ai dans ma bdd 3 components:

component 1: ordre 1
component 2: ordre 2
component 3: ordre 3

je veux donner l'ordre 3 au component 1.

en appliquant ton code le resultat est:
component 1 : ordre 3
component 2: ordre 2
component 3: ordre 2

ce qui est pas bon

Je veux bien, mais où est le code ?

**kaitlyn** · 06/09/2024, 12h15

code édité et exécuté sur https://www.onlinegdb.com/online_csharp_compiler

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/******************************************************************************
 
                            Online C# Compiler.
                Code, Compile, Run and Debug C# program online.
Write your code in this editor and press "Run" button to execute it.
 
*******************************************************************************/
 
using System;
using System.Collections.Generic;
 
class HelloWorld {
 
class Component {
    public string id { get; set; }
    public int order { get; set; }
}
 
static void print_mylist(List<Component> mylist) {
    mylist.ForEach(comp => Console.WriteLine("{0},{1}", comp.id, comp.order));
    Console.WriteLine();
}
 
static void Main() 
{
    var mylist= new List<Component> {
          new Component() {id="comp1", order=1}
        , new Component() {id="comp2", order=2}
        , new Component() {id="comp3", order=3} 
    };
 
    var comp_id= "comp1";
    var new_order= 3;
 
    print_mylist(mylist);
    //=================================================================
    var tmplist= new List<Component>(mylist); //protect the original list against invalidation
    var index_of_comp= tmplist.FindIndex(c => c.id.Equals(comp_id));
    var comp= tmplist[index_of_comp];
    tmplist.RemoveAt(index_of_comp);
 
    var new_index_of_comp= new_order-1;
    comp.order= new_order;
    tmplist.Insert(new_index_of_comp, comp);
 
    var start= Math.Min(index_of_comp, new_index_of_comp);
    var end= Math.Max(index_of_comp, new_index_of_comp);
    for (int i= start; i <= end; i++) {
        tmplist[i].order= i+1;
    }
    mylist= tmplist;
    //=================================================================
    print_mylist(mylist);
 
}
}

output:

comp1,1
comp2,2
comp3,3

comp2,1
comp3,2
comp1,3

**tbc92** · 06/09/2024, 12h25

Si tu veux repartir avec ton tout premier code... et juste changer la ligne 13 'calcul de oldOrder',

Tu peux procéder ainsi :
- Calculer la taille totale de ton tableau nLignes=taille totale du tableau
- Calculer la somme de tous les Order sumOrder = Somme de tous les order

Normalement, si tous les Order étaient tous les nombres entre 1 et nLignes, on obtiendrait sumOrder= (nLignes)(nLignes+1)/2
Mais notre élément ComponentToMove n'a pas la bonne valeur Order, il a la valeur ComponentToMove.order au lieu de oldOrder. et donc la somme qu'on trouve est (nLignes)(nLignes+1)/2 + ComponentToMove.order -oldOrder

Et du coup, on peut retrouver oldOrder :

oldOrder = (nLignes)(nLignes+1)/2 + ComponentToMove.order - sumOrder

Du coup, tu dois remplacer ta ligne n°13 par :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
nLignes = taille totale du tableau
sumOrder = Somme de tous les order
oldOrder = (nLignes)(nLignes+1)/2 + ComponentToMove.order - sumOrder

**gotax** · 06/09/2024, 12h27

en fait je me suis probablement mal exrpimé. je dois tester plusieurs cas de figure:

- incrementer/decrementer les positions du milieu
- mettre le dernier au debut
- mettre le debut en dernier

pour ce qui est de mettre le dermier en premier j'ai comme output: 4 3 1 1 0 au lieu de 4 3 2 1 ou de 5 4 3 2 1 (le lead m'a finalement dit que ca n'0avait pas d'importance pour le frontend que ca parte de 1 ou de 0)

et le code est le suivant:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
public void SetOrder(ref Contract contract, Guid contractComponentId, int newOrder)
{
 
    ContractComponent? componentToMove = contract.ContractComponents
        .FirstOrDefault(c => c.Id == contractComponentId);
 
    if (componentToMove == null) return; 
 
 
    List<ContractComponent> componentsListWithoutComponentToMove = contract.ContractComponents
        .Where(c => c.Id != contractComponentId)
        .OrderBy(c => c.Order)
        .ToList();
 
 
    foreach (var contractComponent in componentsListWithoutComponentToMove)
    {
        if(contractComponent.Order >= componentToMove.Order)
        {
            contractComponent.Order -= 1;
 
        }
    }
 
    {
        if (contractComponent.Order < componentToMove.Order)
        {
            contractComponent.Order += 1;
 
        }
        else contractComponent.Order -= 1;
    }*/
 
 
    foreach (var contractComponent in componentsListWithoutComponentToMove)
    {
        if (contractComponent.Order > newOrder)
        {
            contractComponent.Order += 1;
        }
 
        if (contractComponent.Order <= newOrder)
        {
            if (contractComponent.Order == 1)
            {
                contractComponent.Order = 1;
            }
        }
    }
 
    componentToMove.Order = newOrder;
 
 
    componentsListWithoutComponentToMove.Add(componentToMove);
 
 
    componentsListWithoutComponentToMove = componentsListWithoutComponentToMove
        .OrderBy(c => c.Order)
        .ToList();
 
 
    contract.ContractComponents = componentsListWithoutComponentToMove;
}

**gotax** · 06/09/2024, 12h53

j'ai demandé a chatgpt l'algo utilisé dans Excel et il m'a genere ca et ca marche:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
31
32
33
34
35
36
37
38
public void SetComponentOrder(ref Contract contract, Guid contractComponentId, int newOrder)
{
    List<ContractComponent> myList = contract.ContractComponents.OrderBy(c => c.Order).ToList();
 
    int indexOfComponentToMove = myList.FindIndex(c => c.Id == contractComponentId);
 
    if (indexOfComponentToMove == -1) return;
 
    ContractComponent componentToMove = myList[indexOfComponentToMove];
    myList.RemoveAt(indexOfComponentToMove);
 
    int newIndexOfComponent = newOrder - 1;
 
    if (newIndexOfComponent > indexOfComponentToMove)
    {
        for (int i = indexOfComponentToMove; i < newIndexOfComponent; i++)
        {
            myList[i].Order -= 1; 
        }
    }
    else
    {
        for (int i = newIndexOfComponent; i < indexOfComponentToMove; i++)
        {
            myList[i].Order += 1; 
        }
    }
 
    componentToMove.Order = newOrder;
    myList.Insert(newIndexOfComponent, componentToMove);
 
    for (int i = 0; i < myList.Count; i++)
    {
        myList[i].Order = i + 1;
    }
 
    contract.ContractComponents = myList;
}

Suis je fier de moi? non. j'ai essayé mais j'y suis pas arrivé. je sais qu'un developpeur doit savoir gerer en algo mais c'est pas mon cas

**Guesset** · 06/09/2024, 13h07

Bonjour,

Je ne pratique pas C# aussi la difficulté m'échappe. Il y a 2 opérations, déplacement et renumérotation :

Déplacer le l'item choisi de sa place actuelle i à sa nouvelle place j. A défaut de l'existence d'un move, on peut effectivement en simuler un (extraction puis insert en supposant que l'insert prend la place et repousse l'actuel occupant vers l'indice supérieur).
Ensuite il faut renuméroter les ordres en séquence de i à j (si les indices de la liste commencent à 0, les ordres = indice + 1). Si la liste est préalablement triée et avec une séquence d'ordres sans trou, il faut éviter de modifier l'indice d'origine en ajoutant ou retranchant 1 car cela favorise les erreurs selon que l'ordre futur est supérieur ou inférieur à l'actuel.

A vrai dire, l'utilité d'un ordre qui se contente de reprendre l'indice (éventuellement décalé de 1) dans la liste semble discutable. Rien ne semble empêcher la simulation de l'ordre en retournant l'indice. Mais peut être la liste est retriée parfois selon d'autres critères ?

Salutations

**kaitlyn** · 06/09/2024, 19h30

Envoyé par gotax

et le code est le suivant:

Le code que tu montres ne correspond pas du tout au pseudocode proposé, que j'avais d'ailleurs même fait l'effort de le traduire en un petit exemple complet (conf message #10).

**gotax** · 09/09/2024, 10h30

C'est le code du lead. De plus quand je cree un nouveau composant je me retrouve en bdd avec 2 composants qui ont order = 1. Le lead dit que sur fiddle son code marchait correctement et que c'est moi qui rate qqc.

**kaitlyn** · 09/09/2024, 16h45

Soit tu t'inspires du code proposé soit tu corriges celui de ton chef, on ne va pas choisir à ta place.
Si tu ajoutes un composant, tu fais un list.add(composant), il se retrouve en fin de liste, ensuite tu lui appliques son nouvel ordre.

**gotax** · 09/09/2024, 17h36

le chef veut sonc ode, donc j'ai fait comme il voulait. et pour le probleme lors de la creation, j'ai du rappeler la methode a un autre endroit pour que ca marche (meme le lead ne savait pas car il m'a demandé "qu'est ce qui clochait?" )