linqを使用したトポロジーソート
https://stackoverflow.com/questions/1982592
-
22-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
あるアイテムのリストがあります 部分順序関係, 、 私。 e、リストはaを考慮することができます 部分的に注文されたセット. 。このリストと同じようにこのリストを並べ替えたい 質問. 。そこに正しく答えたように、これはとして知られています トポロジーソート.
問題を解決するための合理的に単純な既知のアルゴリズムがあります。 LINQのような実装が必要です。
私はすでに使用しようとしました OrderBy 拡張方法ですが、トポロジーソートを作成できないと確信しています。問題は、 IComparer<TKey> インターフェイスは部分的な順序を表すことができません。これは、 Compare メソッドは基本的に3種類の値を返すことができます： ゼロ, ネガティブ, 、 と ポジティブ, 、 意味 は同じ, より少ない, 、 と Is-freater-then, 、 それぞれ。作業ソリューションは、戻る方法があった場合にのみ可能です 無関係です.
私の偏った視点から、私が探している答えは IPartialOrderComparer<T> インターフェイスとこのような拡張メソッド：
public static IOrderedEnumerable<TSource> OrderBy<TSource, TKey>(
this IEnumerable<TSource> source,
Func<TSource, TKey> keySelector,
IPartialOrderComparer<TKey> comparer
);
これはどのように実装されますか？どうしますか IPartialOrderComparer<T> インターフェイスはどのように見えますか？別のアプローチをお勧めしますか？私はそれを見たいと思っています。部分的な順序を表すより良い方法があるかもしれませんが、私は知りません。
解決
同じicomparerインターフェイスを使用することをお勧めしますが、0を関連していないと解釈するように拡張メソッドを作成します。部分的な順序では、要素AとBが順序と等しい場合、それらが無関係である場合、それらの順序は重要ではありません。
これは、均等で奇妙な整数の部分的な順序を実行する例です。
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());
}
}
}
結果：4、8、3、5、7、10
他のヒント
これは私の最適化され、改装されたバージョンです temickの答え.
私が行った1つの変更は、実際に置き換えることでした リスト 論理リストに譲る値の残された値。このために、同じサイズの2つのサイズ配列があります。すべての値があり、他の値には各値が生成されたかどうかを示すフラグが含まれています。このようにして、私は本当のものをサイズ変更しなければならないコストを避けます List<Key>.
もう1つの変更は、すべてのキーを反復開始時に1回だけ読んでいることです。私が今思い出せない理由のために（多分それは私の本能だったかもしれません）、私は電話をかけるという考えが好きではありません keySelector 数回機能します。
最後のタッチは、パラメーター検証と、暗黙のキー比較を使用する追加の過負荷でした。コードが十分に読みやすいことを願っています。見てみな。
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--;
}
}
まあ、この処理方法が最良の方法であるかどうかはわかりませんが、私は間違っている可能性があります。
トポロジーソートを処理する典型的な方法は、グラフを使用することであり、各反復に対して、インバウンド接続のないすべてのノードを削除し、それらのノードからアウトバウンドのすべての接続を同時に削除します。削除されたノードは、反復の出力です。これ以上ノードを削除できなくなるまで繰り返します。
ただし、そもそもこれらの接続を取得するには、メソッドが必要になります。
- 「これの前に」と言うことができる方法（これら2つの情報はない」とも言える方法（比較）
- すべての組み合わせを反復し、比較が注文を返すすべての組み合わせの接続を作成します。
言い換えれば、この方法はおそらく次のように定義されます。
public Int32? Compare(TKey a, TKey b) { ... }
そして、戻ります null 2つのキーに対する決定的な答えがない場合。
私が考えている問題は、「すべての組み合わせ」部分です。おそらくこれを処理するより良い方法があるかもしれませんが、私はそれを見ていません。
私は信じている ラッセV.カールセンの答え 正しい軌道に乗っていますが、私は比較方法（またはその問題のための別のインターフェイスを隠すのが好きではありません IComparable<T>).
代わりに、私はむしろこのようなものを見たいです：
public interface IPartialOrderComparer<T> : IComparer<T>
{
int? InstancesAreComparable(T x, T y);
}
このようにして、あなたはまだの実装を持っています IComparer<T> 必要な他の場所で使用できます IComparer<T>.
ただし、Tのインスタンスの関係を次の方法で戻る値で互いに互いに関係することも必要とします（に類似しています IComparable<T>):
- null-インスタンスは互いに匹敵しません。
- 0-インスタンスは互いに匹敵します。
0 -xは同等のキーですが、yは同等ではありません。
- <0 -yは比較可能なキーですが、xはそうではありません。
もちろん、これの実装を渡すと、 IComparable<T> （そして、Lasse V. Karlsenの答えもこれを解決しないことに注意する必要があります）必要なものは、Tの2つのインスタンスを取り、INTを返す単純な比較方法で表現できないためです。
ソリューションを完了するには、新しいインスタンスパラメーターを受け入れる（既に示されているように）カスタムオーダー（その後、注文、その後も同様に）拡張メソッドを提供する必要があります。実装は次のようになります：
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 IPartialComparer<T> {
int? Compare(T x, T y);
}
Compare 返す必要があります -1 もしも x < y, 0 もしも x = y, 1 もしも y < x と null もしも x と y 同等ではありません。
私たちの目標は、列挙を尊重する部分的な順序で要素の順序を返すことです。つまり、シーケンスを求めます e_1, e_2, e_3, ..., e_n 部分的な順序の要素の i <= j と e_i に匹敵します e_j それから e_i <= e_j. 。深度最初の検索を使用してこれを行います。
深さ最初の検索を使用してトポロジーソートを実装するクラス：
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();
}
}
深さの検索を行う際に訪問されたノードをマークするために必要なヘルパークラス：
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();
}
}
これがアルゴリズムの最良の実装であると私は主張しませんが、それが正しい実装であると信じています。さらに、私は返しませんでした IOrderedEnumerable あなたが要求したように、しかし、私たちがこの時点にいるとそれは簡単に行うことができます。
アルゴリズムは、要素を追加する要素を介して深さ最初に検索することで機能します e 線形順序付け（によって表されます _sorted アルゴリズムで）のすべての前任者をすでに追加した場合 e 注文にすでに追加されています。したがって、各要素に対して e, 、まだ訪問していない場合は、その前身を訪れてから追加してください e. 。したがって、これはアルゴリズムのコアです。
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);
}
}
例として、のサブセットで定義されている部分順序付けを検討してください {1, 2, 3} どこ X < Y もしも X のサブセットです Y. 。これを次のように実装します。
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;
}
}
次に sets のサブセットのリストとして定義されています {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());
これにより、注文が得られます。
{}, {2}, {3}, {2, 3}, {1}, {1, 3}, {1, 2}, {1, 2, 3}
部分的な順序を尊重します。
それはとても楽しかったです。ありがとう。
Eric Mickelsenの答えから始めて、null値を使用してLasse V. Karlsenが言ったように、null値を使用しないことを好むので、私は自分のバージョンを思いつきました。
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));
}
次に、比較用の次のインターフェイスがあります
public interface IPartialEqualityComparer<T>
{
int? Compare(T x, T y);
}
そして、このヘルパークラス
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);
}
}
これにより、使用法を少し美しくすることができます。
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);
});
