Trier une liste avec une fonction de comparaison qui ne respecte pas le "strict weak ordering" (ordre faible strict)

Question

J'ai une liste de 10 articles. Je voudrais les trier d'une manière particulière.

Par exemple, les éléments sont A1, B, C1, A2, A3, F, G, C2, H, A4.

Les règles sont les suivantes

• C doit toujours passer avant A
• B doit toujours venir après A
• Tous les autres éléments doivent conserver leur ordre.

Après le tri, la liste devrait donc se présenter dans l'ordre suivant C1 C2 A1 A2 A3 F G H A4 B

J'essaie d'utiliser C++ std::stable_sort() pour y parvenir. Dans mon programme, tous les éléments sont des instances d'une structure "SItem" qui possède un membre "type" pour indiquer sa catégorie (A, B, etc.). Ma fonction de comparaison ressemble à ceci

bool CompareItems(SItem const& item1, SItem const& item2) 
{
    if (item1.type == A && item2.type == C)
        return false;

    if (item1.type == B && item2.type == A)
        return false;

    return true;
}

D'après ce que j'ai compris de stable_sort Il exige que la fonction de comparaison suive un "ordre faible strict". De toute évidence, ma méthode ne respecte pas cette exigence, et je ne peux donc pas utiliser le stable_sort. Existe-t-il un algorithme de tri permettant d'obtenir ce type d'ordre ?

Code complet

#include <list>
#include <algorithm>
#include <iostream>

enum ItemType
{
    A, B, C, D, E, F, G, H,
};

struct SItem
{
    SItem(ItemType t, int i) {
        type = t;
        index = i;
    }

    ItemType type;
    int index;
};

//do not follow strict week ordering
bool CompareItems(SItem const& item1, SItem const& item2) 
{
    if (item1.type == A && item2.type == C)
        return false;

    if (item1.type == B && item2.type == A)
        return false;

    return true;
}

int main()
{
    std::list<SItem> lstItems = { {A, 1}, {B, 1}, {C, 1}, {A, 2}, {A, 3}, {F, 1}, {G, 1}, {C, 2}, {H, 1}, {A, 4} };
    std::stable_sort(lstItems.begin(), lstItems.end(), CompareItems);

    return 0;
}

Answer 1

Il ne s'agit pas d'une sorte de

En tout cas, pas autant que std définit ses types.

Vous souhaitez simplement déplacer certains éléments.

4 étapes :

• Trouvez le premier A. C'est là que nous voulons placer les C.

• Cloison stable tous les C pour être juste avant le premier A.

• Trouvez le dernier A. C'est là que nous voulons placer les B.

• La partition stable des B se situe juste après le dernier A.

Tous les C précédant le premier A restent immobiles. Tous les B après le dernier A restent immobiles.

Les C conservent leur ordre relatif. Les B conservent leur ordre relatif. Tous deux se déplacent le moins possible pour générer la garantie que vous souhaitez.

Tout ce qui n'est pas un C ou un B conserve son ordre relatif.

Code :

template<class It, class IsA, class IsB, class IsC>
void do_it(It s, It f, IsA a, IsB b, IsC c){
  auto first_a = std::find_if(s,f,a);
  first_a = std::stable_partition(first_a,f,c);
  auto last_a = std::find_if(std::make_reverse_iterator(f), std::make_reverse_iterator(first_a), a).base();
  std::stable_partition(s,last_a, [&b](auto&&x){return !b(x);});
}

Exemple concret .

Si la mémoire disponible est suffisante, l'opération ci-dessus est O(n).

Bien entendu, cela pourrait être fait en une seule ligne :

std::stable_partition(s,std::find_if(std::make_reverse_iterator(f), std::make_reverse_iterator(std::stable_partition(std::find_if(s,f,a),f,c)), a).base(), [&b](auto&&x){return !b(x);});

mais je ne le recommande pas.

Answer 2

Il ne s'agit pas d'un ordre faible strict, mais d'un ordre faible. commande partielle . Un algorithme de tri par ordre partiel est appelé "algorithme de tri". tri topologique comme cette mise en œuvre naïve :

template <typename Iterator, typename Compare>
void stable_toposort(Iterator begin, Iterator end, Compare cmp)
{
    while (begin != end)
    {
        auto const new_begin = std::stable_partition(begin, end, [&](auto const& a)
        {
            return std::none_of(begin, end, [&](auto const& b) { return cmp(b, a); });
        });
        assert(new_begin != begin && "not a partial ordering");
        begin = new_begin;
    }
}

Il partitionne la séquence de manière à ce que tous les éléments qui ne sont pas plus grands qu'un autre élément soient déplacés vers l'avant. Il prend ensuite tous les éléments restants et les partitionne de la même manière, jusqu'à ce qu'il n'y ait plus d'éléments à partitionner. Sa complexité est de O(n²) comparaisons et O(n) permutations.

Nous devons ensuite corriger le bogue dans la fonction de comparaison :

bool CompareItems(SItem const& item1, SItem const& item2)
{
    if (item1.type == C && item2.type == A) return true;
    if (item1.type == A && item2.type == B) return true;
    return false;
}

Démonstration en direct

À titre de référence, une version instable utiliserait partition au lieu de stable_partition .

Answer 3

Ce que vous voulez, c'est une sorte de topologie stable. Votre DAG est que Cs pointe sur As pointe sur Bs. Voir https://stackoverflow.com/a/11236027/585411 pour obtenir une description d'un algorithme raisonnablement efficace pour mettre en œuvre le tri topologique qui est le plus bas dans l'ordre lexicographique (dans votre liste originale). Dans votre cas, le résultat serait le suivant :

C1, F, G, C2, A1, A2, A3, H, A4, B

Cette façon de voir les choses permet de généraliser les différents types de règles que vous pourriez avoir, plutôt que d'utiliser des cas particuliers pour le fonctionnement de cet exemple. Tant qu'elles ne s'additionnent pas pour former une trajectoire circulaire, votre algorithme fonctionnera toujours.

Answer 4

Si je comprends bien l'algorithme que vous souhaitez utiliser, il est probablement plus facile de le diviser manuellement en trois listes, puis de le recouper.

void slide_bs_and_cs( std::list<SItem>& all ) {
    // Don't touch if no A's found:
    if ( std::find(all.begin(), all.end(),
        [](const SItem& item) { return item->type == A; }) == all.end() )
        return;

    std::list<SItem> bs;
    std::list<SItem> cs;
    auto first_a = all.end();
    auto after_last_a = all.end();
    for ( auto it = all.begin(); it != all.end();
          /*advanced in loop*/ ) {
        auto next = it;
        ++next;
        if ( (*it)->type == A ) {
            after_last_a = next;
            if ( first_a == all.end() )
                first_a = it;
        } else if ( (*it)->type == B ) {
            bs.splice( bs.end(), it );
        } else if ( (*it)->type == C ) {
            cs.splice( cs.end(), it );
        }
        it = next;
    }
    all.splice( first_a, cs );
    all.splice( after_last_a, bs );
}

Answer 5

Le problème d'un ordre faible non strict est que l'ordre n'est pas suffisant pour définir la liste triée. Avec l'entrée A1, B, C1, A2, A3, F, G, C2, H, A4 vous avez proposé la sortie C1 C2 A1 A2 A3 F G H A4 B . Mais en fait, B venait avant H dans la liste originale et vient maintenant après, ce qui n'est pas conforme à un tri stable. Si l'on voulait conserver B < H, on obtiendrait la liste suivante :

C1 C2 A1 A2 A3 F G A4 B H

mais ici c'est le A4 < H qui a été cassé.

Pour construire un tri stable, il faut définir un ordre faible strict. Pour obtenir la liste que vous proposez, cet ordre pourrait être utilisé :

• C vient avant A
• B vient après A
• toutes les autres lettres sont équivalentes à A

Dans ce cas, la fonction de comparaison devient :

bool CompareItems(SItem const& item1, SItem const& item2) 
{
    if (item1.type == 'C' && item2.type != 'C')
        return true;

    if (item1.type != 'B' && item2.type == 'B')
        return true;

    return false;
}

Vous pouvez également essayer de spécifier un algorithme qui accepte un ordre strict non faible, mais vous devrez spécifier ce qui se passe lorsque vous avez cette liste originale. X Y Z , Z < X , X,Y et Y,Z non comparable : voulez-vous Z X Y , Z Y X o Y Z X ? En fait, cela dépend si Y doit être traité comme équivalent à X ou Z ou... Et de se demander ce qui pourrait se passer dans des cas d'utilisation plus complexes...