Laden...

[Gelöst] Mehrere Listen zusammenfassen, ohne Duplikate und mit Beibehaltung der Reihenfolge

Erstellt von jannemann13 vor 7 Jahren Letzter Beitrag vor 7 Jahren 2.950 Views
jannemann13 Themenstarter:in
69 Beiträge seit 2009
vor 7 Jahren
[Gelöst] Mehrere Listen zusammenfassen, ohne Duplikate und mit Beibehaltung der Reihenfolge

Hallo,

ich habe hier ein Problem, das einfach klingt, aber an dem ich mir grad ein wenig die Zähne ausbeisse 😃 Ich möchte mehrere Listen zu einer Gesamtliste zusammenfassen, aber so, dass kein Eintrag doppelt vorkommt und die Reihenfolge der Einträge aus den Einzellisten erhalten bleibt. Hier ein Beispiel:

List<List<char>> lists = new List<List<char>> {
	new List<char> { 's', 'a' },
	new List<char> { 'a', 'm' },
	new List<char> { 'm', 'p' },
	new List<char> { 'p', 'l', 'e' },
	new List<char> { 's', 'e' },
	new List<char> { 'p', 'e' }
	new List<char> { 'm' }
};

Das Ergebnis soll die Sequenz { 's', 'a', 'm', 'p', 'l', 'e' } sein. In diesem Beispiel gibt es keine "widersprüchlichen" Angaben wie etwa { 'e', 's' }, das kann aber in meiner Anwendung durchaus vorkommen. In dem Fall würde ich das gerne feststellen und abbrechen, weil dann keine eindeutige Reihenfolge definiert ist.

Mir fehlt hier der Ansatz, wie ich die Reihenfolge der Einträge untereinander vergleichen, in die Ergebnislliste übernehmen und dabei noch Fehler feststellen kann. Gibt es hierfür eine einfache Methode oder hat jemand einen Tipp für mich?

Vielen Dank schonmal!

16.807 Beiträge seit 2008
vor 7 Jahren

Schau Dir das HashSet an.

Jeder Eintrag kann hier nur einmalig existieren. Steht auch in der Doku 😉
Die Reihenfolge ergibt sich aus dem Add. Da muss nichts verglichen werden.

jannemann13 Themenstarter:in
69 Beiträge seit 2009
vor 7 Jahren

Hallo Abt,

danke für die schnelle Antwort. Ich habe das Beispiel konstruiert und dabei die Listen intuitiv so sortiert, dass es mit einfachem Hinzufügen funktionieren würde, sorry. Die Listen können aber auch "später" noch neue Einträge enthalten, die in der Ergebnisliste weiter vorne liegen müssen:

List<List<char>> lists = new List<List<char>> {
	new List<char> { 'a', 'm' },
	new List<char> { 'm', 'p' },
	new List<char> { 'p', 'l', 'e' },
	new List<char> { 's', 'e' },
	new List<char> { 'p', 'e' },
	new List<char> { 's', 'a' },
};

So bekomme ich erst bei der 4. Einzelliste die Information, dass vor dem 'e' noch ein 's' einsortiert werden muss, dann wäre ich an der Stelle bei einem Zwischenstand { 'a', 'm', 'p', 'l', 's', 'e' }.

Dann in der 6. Liste erfahre ich, dass das 's' sogar noch vor dem 'a' liegen muss und käme dann erst auf das Endergebnis { 's', 'a', 'm', 'p', 'l', 'e' }.

Ich hoffe, das ich das verständlich erklärt habe 😃

(edit: Typos)

742 Beiträge seit 2005
vor 7 Jahren

HashSet ist nicht sortiert.

Aus der Doku

A HashSet<T> collection is not sorted and cannot contain duplicate elements. If order or element duplication is more important than performance for your application, consider using the List<T> class together with the Sort method.

Ordered dictionary dürfte funktionieren.

https://msdn.microsoft.com/en-us/library/system.collections.specialized.ordereddictionary(v=vs.110).aspx

16.807 Beiträge seit 2008
vor 7 Jahren

Das HashSet habe ich genannt, da es Dir ja in erster Linie mal auch um die eindeutigen Elemente geht. Und das würde auch super funktionieren, wenn die Sublisten genau in der entsprechenden Reihenfolge sind.
Sind sie das nicht, dann hat malignate recht, dass das nicht passt.

Da führen viele Wege nach Rom.

742 Beiträge seit 2005
vor 7 Jahren

Ich meinte eher, dass die Reihenfolge nicht erhalten bleibt. Zumindest wenn es über ein internes Array realisiert wird. OrderedDictionary sollte die Reihenfolge erhalten, SortedDictionary sortiert nach dem Key (bzw. dem Comparer).

jannemann13 Themenstarter:in
69 Beiträge seit 2009
vor 7 Jahren

Hallo Abt,
hallo malignate,

es ging mir nicht primär um die Struktur, in der ich die Ergebnisliste ablegen kann; dafür ist List<T> meiner Meinung nach ausreichend, wenn ich während der Befüllung sicherstelle, dass ich keine doppelten Einträge aufnehme.

Mein Problem ist der Algorithmus bzw. die Methode, wie ich die Liste erstellen kann. Also quasi, wie bekomme ich eine Liste hin, die alle auftretenden Elemente genau einmal enthält und dabei die Regeln jeder Einzelliste befolgt:

  • 'a' kommt vor 'm'
  • 'm' kommt vor 'p'
  • 'p' kommt vor 'l', 'l' kommt vor 'e'
  • 's' kommt vor 'e'
    usw.

Ich poste hier mal den Code, mit dem ich das im Moment zu erreichen versuche, vielleicht könnt ihr mich damit in die richtige Richtung schubsen 😃

List<List<char>> lists = new List<List<char>> {
	new List<char> { 'l', 'e' },
	new List<char> { 's', 'a' },
	new List<char> { 'a', 'm' },
	new List<char> { 'm', 'p' },
	new List<char> { 'p', 'l', 'e' },
	new List<char> { 's', 'e' },
	new List<char> { 'a' },
	new List<char> { 'p' },
	new List<char> { 's' },
	new List<char> { 'p', 'e' },
	new List<char> { 's', 'a' },
};

int currentItemPosition = 0;
int otherItemPosition = 0;
int otherItem = 0;
char item;
List<char> result = new List<char>();

foreach (List<char> list in lists)
{
	for (int currentItem = 0; currentItem < list.Count; currentItem++)
	{
		Console.WriteLine(string.Format("currentList  : {0}", new string(list.ToArray())));
		Console.WriteLine(string.Format("currentItem  : {0}", list[currentItem]));

		if (!result.Contains(list[currentItem]))
			result.Add(list[currentItem]);

		if (currentItem < list.Count - 1)
		{
			otherItem = currentItem + 1;
			otherItemPosition = result.IndexOf(list[otherItem]);
			currentItemPosition = result.IndexOf(list[currentItem]);
			if (otherItemPosition != -1 && currentItemPosition > otherItemPosition)
			{
				for (int offset = currentItemPosition; offset < list.Count; offset++)
				{
					item = result[offset];
					result.RemoveAt(offset);
					result.Insert(otherItemPosition + offset, item);
				}
			}
		}

		Console.WriteLine(string.Format("Zwischenstand: {0}", new string(result.ToArray())));
		Console.ReadLine();
	}
}

Console.WriteLine(string.Format("Endergebnis: {0}", new string(result.ToArray())));
Console.ReadLine();
742 Beiträge seit 2005
vor 7 Jahren

Hätte ich vll. besser lesen sollen.

So wie ich das sehe, brauchst du globale Konfliktfreie Sortierregeln (Also nicht sowas wie "a" vor "b" und "b" vor "a"). Falls sowohl die Listen selbst, als auch die Einträge innerhalb der Listen vorsortiert sind, kannst du das vorgeschlagene OrderDictionary<char, char> verwenden.

Implementiere doch einfach nen IComparer<char> und dann kannst du sowas machen:


var uniqueValues = new HashSet<char>();

foreach (var list in lists) {
    foreach (var value in list) {
         uniqueValues.Add(list);
    }
}

var orderedUnique = uniqueValues.OrderBy(x => x, new MyComparer()).ToList();

Hier dazu ein paar Referenzen:

  1. https://msdn.microsoft.com/en-us/library/bb549422(v=vs.100).aspx (OrderBy)
  2. http://www.mycsharp.de/wbb2/addreply.php?threadid=117402 (IComparer Interface)

Eine andere Möglichkeit ist ein Topologische Sortierung: http://stackoverflow.com/questions/21189222/topological-sort-with-support-for-cyclic-dependencies

Das kann man z.B. verwenden, wenn man in requirejs und co Abhängigkeiten zwischen Javascript Module definiert. Dann ist die Frage, in welcher Reihenfolge man diese im Browser und Node.JS laden muss. In jeder Liste ist dann einfach jedes Element von seinen Nachfolgern abhängig. Wenn du alle Elemente in eine solche Struktur bringt, kannst du es durch eine Topologische Sortierung jagen:

z.B. so



class ItemWithDependencies {
  public char Item {get;set;}
  public HashSet<char> Dependencies {get;set;}
}

Dictionary<char, ItemWithDependencies> items = ...;

foreach (var list of lists)
{
     for (int i = 0; i < list.Count; i++)
     {
         var item = list[i];
         ItemWithDependencies itemWithDependencies = null;

         if (!items.TryGetValue(item out itemWithDependencies)) {
              itemWithDependencies  = new ItemWithDependencies { Item = item };

              items.Add(item, itemWithDependencies);
         }
          
          for (int j = i + 1; j < list.Count; j++) {
              itemWithDependencies.Dependencies.Add(list[j]);
          }
     }
}

SortByTopology(items);

jannemann13 Themenstarter:in
69 Beiträge seit 2009
vor 7 Jahren

Hallo malignate,

vielen Dank, Topologische Sortierung ist genau das Stichwort, das mir fehlte 🙂 Damit komme ich jetzt weiter 👍