Question

I ai une liste des éléments qui ont une relation , i. e, la liste peut être considéré comme un partiellement ordonné . Je veux trier cette liste de la même manière que dans cette question . Comme il a répondu correctement, ceci est connu comme tri topologique .

Il y a un algorithme connu assez simple pour résoudre le problème. Je veux une mise en œuvre comme LINQ de celui-ci.

Je l'ai déjà essayé d'utiliser la méthode d'extension OrderBy, mais je suis tout à fait sûr que ce n'est pas en mesure de faire le tri topologique. Le problème est que l'interface IComparer<TKey> ne peut pas représenter un ordre partiel. Cela se produit parce que la méthode de Compare peut revenir essentiellement trois types de valeurs: zéro , négatif et positif , ce qui signifie sont-égaux , est-less-than et est-plus-alors , respectivement. Une solution de travail ne serait possible que s'il y avait un moyen de revenir sont sans rapport avec-.

De mon point de vue biaisé, la réponse que je suis à la recherche pourrait être composé par une interface IPartialOrderComparer<T> et une méthode d'extension comme ceci: 

public static IOrderedEnumerable<TSource> OrderBy<TSource, TKey>(
    this IEnumerable<TSource> source,
    Func<TSource, TKey> keySelector,
    IPartialOrderComparer<TKey> comparer
);

Comment cela serait mis en œuvre? Comment fonctionne l'interface IPartialOrderComparer<T> ressemblerait? Recommanderiez-vous une approche différente? Je suis impatient de le voir. Peut-être il y a une plus belle façon de représenter l'ordre partiel, je ne sais pas.

Était-ce utile?

La solution

Je suggère d'utiliser la même interface IComparer, mais l'écriture de la méthode d'extension de manière à interpréter 0 comme non liés. Dans un ordre partiel, si les éléments a et b sont égaux leur ordre n'a pas d'importance, si elles ne sont pas liés comme sage -. Avez-vous seulement pour les commander par rapport aux éléments avec lesquels ils ont défini les relations

Voici un exemple qui fait un ordre partiel des entiers pairs et impairs: 

namespace PartialOrdering
{
    public static class Enumerable
    {
        public static IEnumerable<TSource> PartialOrderBy<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, IComparer<TKey> comparer)
        {
            List<TSource> list = new List<TSource>(source);
            while (list.Count > 0)
            {
                TSource minimum = default(TSource);
                TKey minimumKey = default(TKey);
                foreach (TSource s in list)
                {
                    TKey k = keySelector(s);
                    minimum = s;
                    minimumKey = k;
                    break;
                }
                foreach (TSource s in list)
                {
                    TKey k = keySelector(s);
                    if (comparer.Compare(k, minimumKey) < 0)
                    {
                        minimum = s;
                        minimumKey = k;
                    }
                }
                yield return minimum;
                list.Remove(minimum);
            }
            yield break;
        }

    }
    public class EvenOddPartialOrdering : IComparer<int>
    {
        public int Compare(int a, int b)
        {
            if (a % 2 != b % 2)
                return 0;
            else if (a < b)
                return -1;
            else if (a > b)
                return 1;
            else return 0; //equal
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            IEnumerable<Int32> integers = new List<int> { 8, 4, 5, 7, 10, 3 };
            integers = integers.PartialOrderBy<Int32, Int32>(new Func<Int32, Int32>(delegate(int i) { return i; }), new EvenOddPartialOrdering());
        }
    }
}

Résultat: 4, 8, 3, 5, 7, 10

Autres conseils

Ceci est ma version optimisée et remis à neuf de tehMick s réponse.

Un changement que je fait a été de remplacer la vraie liste des valeurs gauche pour obtenir une liste logique. Pour cela, j'ai deux tableaux de taille de la même taille. On a toutes les valeurs, et les autres contient des drapeaux indiquant si chaque valeur a été donné. De cette façon, j'évite le coût d'avoir à redimensionner une réelle List<Key>.

Un autre changement est que je lis toutes les clés qu'une seule fois au début de l'itération. Pour des raisons que je ne me souviens pas maintenant (peut-être c'était juste mon instinct) Je n'aime pas l'idée d'appeler la fonction keySelector plusieurs fois.

Les dernières touches était la validation des paramètres, et une surcharge supplémentaire qui utilise un comparateur de clé implicite. J'espère que le code est assez lisible. Check it out. 

public static IEnumerable<TSource> PartialOrderBy<TSource, TKey>(
    this IEnumerable<TSource> source,
    Func<TSource, TKey> keySelector)
{
    return PartialOrderBy(source, keySelector, null);
}

public static IEnumerable<TSource> PartialOrderBy<TSource, TKey>(
    this IEnumerable<TSource> source,
    Func<TSource, TKey> keySelector,
    IComparer<TKey> comparer)
{
    if (source == null) throw new ArgumentNullException("source");
    if (keySelector == null) throw new ArgumentNullException("keySelector");
    if (comparer == null) comparer = (IComparer<TKey>)Comparer<TKey>.Default;

    return PartialOrderByIterator(source, keySelector, comparer);
}

private static IEnumerable<TSource> PartialOrderByIterator<TSource, TKey>(
    IEnumerable<TSource> source,
    Func<TSource, TKey> keySelector,
    IComparer<TKey> comparer)
{
    var values = source.ToArray();
    var keys = values.Select(keySelector).ToArray();
    int count = values.Length;
    var notYieldedIndexes = System.Linq.Enumerable.Range(0, count).ToArray();
    int valuesToGo = count;

    while (valuesToGo > 0)
    {
        //Start with first value not yielded yet
        int minIndex = notYieldedIndexes.First( i => i >= 0);

        //Find minimum value amongst the values not yielded yet
        for (int i=0; i<count; i++)
        if (notYieldedIndexes[i] >= 0)
        if (comparer.Compare(keys[i], keys[minIndex]) < 0) {
            minIndex = i;
        }

        //Yield minimum value and mark it as yielded
        yield return values[minIndex];
        notYieldedIndexes[minIndex] = -1;
        valuesToGo--;
    }
}

Eh bien, je ne suis pas sûr que cette façon de manipuler est la meilleure façon, mais je peux me tromper.

La façon typique de gérer le tri topologique est à l'aide d'un graphique, et pour chaque itération supprimer tous les noeuds qui ne disposent pas d'une connexion entrante et de supprimer simultanément toutes les connexions sortantes de ces nœuds. Les noeuds sont retirés de la sortie de l'itération. Répétez jusqu'à ce que vous ne pouvez pas supprimer des nœuds plus.

Cependant, afin d'obtenir ces connexions en premier lieu, avec votre méthode, vous devez:

  1. Une méthode (votre comparateur) qui pourrait dire « ceci avant que » mais aussi « pas d'information pour ces deux »
  2. itérer toutes les combinaisons, la création de connexions pour toutes les combinaisons que le comparateur retourne une commande pour.

En d'autres termes, la méthode serait probablement définie comme ceci: 

public Int32? Compare(TKey a, TKey b) { ... }

puis revenir null quand il n'a pas de réponse concluante pour deux clés.

Le problème que je pense à la partie est « itérer toutes les combinaisons ». Peut-être qu'il ya une meilleure façon de gérer cela, mais je ne suis pas le voir.

Je crois que Lasse V. réponse Karlsen est sur la bonne voie , mais je n'aime pas se cacher de la méthode de comparaison (ou une interface distincte pour cette question qui ne s'étend pas de IComparable<T>).

Au lieu de cela, je préfère voir quelque chose comme ceci: 

public interface IPartialOrderComparer<T> : IComparer<T>
{
    int? InstancesAreComparable(T x, T y);
}

De cette façon, vous avez encore une implémentation de IComparer<T> qui peut être utilisé dans d'autres endroits qui nécessitent IComparer<T>.

Cependant, il vous faut aussi indiquer la relation entre les instances de T à l'autre avec la valeur de retour de la façon suivante (similaire à IComparable<T>):

  • null - cas ne sont pas comparables entre eux
    • .
  • 0 -. Les cas sont comparables entre eux
  •   

    0 - x est une clé comparable, mais y est pas

    .
  • <0 -. Y est une clé comparable, mais x est pas

Bien sûr, vous ne serez pas ordre partiel lors du passage d'une mise en œuvre de ce à quoi que ce soit qui attend un IComparable<T> (et il convient de noter que Lasse V. La réponse de Karlsen ne résout pas non plus) que ce que vous avez besoin peut » t être représenté dans un simple méthode de comparaison qui prend deux instances de T et retourne un int.

Pour terminer la solution, vous devez fournir une coutume OrderBy (ainsi que ThenBy, OrderByDescending et ThenByDescending ainsi) méthode d'extension qui acceptera le nouveau paramètre d'instance (comme vous l'avez déjà indiqué). La mise en œuvre ressemblerait à quelque chose comme ceci: 

public static IOrderedEnumerable<TSource> OrderBy<TSource, TKey>(      
    this IEnumerable<TSource> source,      
    Func<TSource, TKey> keySelector,      
    IPartialOrderComparer<TKey> comparer)
{
    return Enumerable.OrderBy(source, keySelector,
        new PartialOrderComparer(comparer);
}

internal class PartialOrderComparer<T> : IComparer<T>
{
    internal PartialOrderComparer(IPartialOrderComparer<T> 
        partialOrderComparer)
    {
        this.partialOrderComparer = partialOrderComparer;
    }

    private readonly IPartialOrderComparer<T> partialOrderComparer;

    public int Compare(T x, T y)
    {
        // See if the items are comparable.
        int? comparable = partialOrderComparable.
            InstancesAreComparable(x, y);

        // If they are not comparable (null), then return
        // 0, they are equal and it doesn't matter
        // what order they are returned in.
        // Remember that this only to determine the
        // values in relation to each other, so it's
        // ok to say they are equal.
        if (comparable == null) return 0;

        // If the value is 0, they are comparable, return
        // the result of that.
        if (comparable.Value == 0) return partialOrderComparer.Compare(x, y);

        // One or the other is uncomparable.
        // Return the negative of the value.
        // If comparable is negative, then y is comparable
        // and x is not.  Therefore, x should be greater than y (think
        // of it in terms of coming later in the list after
        // the ordered elements).
        return -comparable.Value;            
    }
}

interface pour définir la relation d'ordre partiel: 

interface IPartialComparer<T> {
    int? Compare(T x, T y);
}

Compare doit retourner -1 si x < y, 0 si x = y, 1 si y < x et null si x et y ne sont pas comparables.

Notre objectif est de retourner un ordre des éléments dans l'ordre partiel qui respecte l'énumération. Autrement dit, nous cherchons une séquence e_1, e_2, e_3, ..., e_n des éléments dans l'ordre partiel tel que si i <= j et e_i est comparable à e_j puis e_i <= e_j. Je vais le faire en utilisant une recherche en profondeur d'abord.

classe qui implémente tri topologique en utilisant la recherche en profondeur d'abord: 

class TopologicalSorter {
    class DepthFirstSearch<TElement, TKey> {
        readonly IEnumerable<TElement> _elements;
        readonly Func<TElement, TKey> _selector;
        readonly IPartialComparer<TKey> _comparer;
        HashSet<TElement> _visited;
        Dictionary<TElement, TKey> _keys;
        List<TElement> _sorted;

        public DepthFirstSearch(
            IEnumerable<TElement> elements,
            Func<TElement, TKey> selector,
            IPartialComparer<TKey> comparer
        ) {
            _elements = elements;
            _selector = selector;
            _comparer = comparer;
            var referenceComparer = new ReferenceEqualityComparer<TElement>();
            _visited = new HashSet<TElement>(referenceComparer);
            _keys = elements.ToDictionary(
                e => e,
                e => _selector(e), 
                referenceComparer
            );
            _sorted = new List<TElement>();
        }

        public IEnumerable<TElement> VisitAll() {
            foreach (var element in _elements) {
                Visit(element);
            }
            return _sorted;
        }

        void Visit(TElement element) {
            if (!_visited.Contains(element)) {
                _visited.Add(element);
                var predecessors = _elements.Where(
                    e => _comparer.Compare(_keys[e], _keys[element]) < 0
                );
                foreach (var e in predecessors) {
                    Visit(e);
                }
                _sorted.Add(element);
            }
        }
    }

    public IEnumerable<TElement> ToplogicalSort<TElement, TKey>(
        IEnumerable<TElement> elements,
        Func<TElement, TKey> selector, IPartialComparer<TKey> comparer
    ) {
        var search = new DepthFirstSearch<TElement, TKey>(
            elements,
            selector,
            comparer
        );
        return search.VisitAll();
    }
}

Classe d'assistance nécessaire pour marquer les noeuds comme visité tout en faisant la recherche en profondeur d'abord: 

class ReferenceEqualityComparer<T> : IEqualityComparer<T> {
    public bool Equals(T x, T y) {
        return Object.ReferenceEquals(x, y);
    }

    public int GetHashCode(T obj) {
        return obj.GetHashCode();
    }
}

Je ne prétends pas que ce soit la meilleure mise en œuvre de l'algorithme, mais je crois qu'il est une mise en œuvre correcte. De plus, je ne suis pas retourné un IOrderedEnumerable comme vous avez demandé, mais qui est facile à faire une fois que nous sommes à ce stade.

L'algorithme fonctionne en faisant une recherche en profondeur d'abord à travers les éléments en ajoutant un e élément à l'ordre linéaire (représenté par _sorted dans l'algorithme) si nous avons déjà ajouté tous les prédécesseurs de e ont déjà été ajoutés à la commande. Par conséquent, pour chaque e élément, si nous n'avons pas encore visité, visitez ses prédécesseurs, puis ajouter e. Ainsi, c'est le coeur de l'algorithme: 

public void Visit(TElement element) {
    // if we haven't already visited the element
    if (!_visited.Contains(element)) {
        // mark it as visited
        _visited.Add(element);
        var predecessors = _elements.Where(
            e => _comparer.Compare(_keys[e], _keys[element]) < 0
        );
        // visit its predecessors
        foreach (var e in predecessors) {
            Visit(e);
        }
        // add it to the ordering
        // at this point we are certain that
        // its predecessors are already in the ordering
        _sorted.Add(element);
    }
}

À titre d'exemple, considérons la commande partielle définie sur des sous-ensembles de {1, 2, 3} où X < Y si X est un sous-ensemble de Y. Je mets en œuvre cela comme suit: 

public class SetComparer : IPartialComparer<HashSet<int>> {
    public int? Compare(HashSet<int> x, HashSet<int> y) {
        bool xSubsety = x.All(i => y.Contains(i));
        bool ySubsetx = y.All(i => x.Contains(i));
        if (xSubsety) {
            if (ySubsetx) {
                return 0;
            }
            return -1;
        }
        if (ySubsetx) {
            return 1;
        }
        return null;
    }
}

Ensuite, avec sets défini comme la liste des sous-ensembles de {1, 2, 3} 

List<HashSet<int>> sets = new List<HashSet<int>>() {
    new HashSet<int>(new List<int>() {}),
    new HashSet<int>(new List<int>() { 1, 2, 3 }),
    new HashSet<int>(new List<int>() { 2 }),
    new HashSet<int>(new List<int>() { 2, 3}),
    new HashSet<int>(new List<int>() { 3 }),
    new HashSet<int>(new List<int>() { 1, 3 }),
    new HashSet<int>(new List<int>() { 1, 2 }),
    new HashSet<int>(new List<int>() { 1 })
};
TopologicalSorter s = new TopologicalSorter();
var sorted = s.ToplogicalSort(sets, set => set, new SetComparer());

Il en résulte l'ordre: 

{}, {2}, {3}, {2, 3}, {1}, {1, 3}, {1, 2}, {1, 2, 3}

qui respecte l'ordre partiel.

C'était beaucoup de plaisir. Merci.

Merci beaucoup à tout le monde, à partir de la réponse d'Eric Mickelsen J'ai venu avec ma version que je préfère utiliser les valeurs NULL pour indiquer aucune relation comme Lasse V. Karlsen dit. 

public static IEnumerable<TSource> PartialOrderBy<TSource>(
        this IEnumerable<TSource> source,            
        IPartialEqualityComparer<TSource> comparer)
    {
        if (source == null) throw new ArgumentNullException("source");
        if (comparer == null) throw new ArgumentNullException("comparer");


        var set = new HashSet<TSource>(source);
        while (!set.IsEmpty())
        {
            TSource minimum = set.First();                

            foreach (TSource s in set)
            {                    
                var comparison = comparer.Compare(s, minimum);
                if (!comparison.HasValue) continue;
                if (comparison.Value <= 0)
                {
                    minimum = s;                        
                }
            }
            yield return minimum;
            set.Remove(minimum);
        }
    }

public static IEnumerable<TSource> PartialOrderBy<TSource>(
       this IEnumerable<TSource> source,
       Func<TSource, TSource, int?> comparer)
    {
        return PartialOrderBy(source, new PartialEqualityComparer<TSource>(comparer));
    }

alors j'ai l'interface suivante pour le comparateur 

public interface IPartialEqualityComparer<T>
{
    int? Compare(T x, T y);
}

et cette classe d'aide 

internal class PartialEqualityComparer<TSource> : IPartialEqualityComparer<TSource>
{
    private Func<TSource, TSource, int?> comparer;

    public PartialEqualityComparer(Func<TSource, TSource, int?> comparer)
    {
        this.comparer = comparer;
    }

    public int? Compare(TSource x, TSource y)
    {
        return comparer(x,y);
    }
}

qui permet d'embellir l'utilisation un peu pour mes tests peuvent se présente comme suit 

 var data = new int[] { 8,7,6,5,4,3,2,1,0 };
 var partiallyOrdered = data.PartialOrderBy((x, y) =>
     {
        if (x % 2 == 0 && y % 2 != 0) return null;
        return x.CompareTo(y);
     });
Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top