Finden von Duplikaten bei Strings, die nicht nur direkt identisch sind (A1Q1 ist auch gleich Q1A1)

Hallo Community,
wieder einmal stehe ich vor einem Problem wo ich mir Hilfe erhoffe. Folgender Fall liegt vor, ich habe eine riesige Liste von strings jetzt versuche ich die strings die aus den selben Zeichen bestehen wie ein anderer string der bereits in der Liste vorhanden ist zu entfernen.

Dabei habe ich folgendes erfolgreich programmiert:

int zähler, zähler2 = 0;
                for (int i = 0; i < liste.Count; i++)//hier werden die Ursprung Strings gesplittet in einzelne chars
                {
                    for (int j = 0; j <= liste[i].Length - 1; j++)
                    {
                        list_c.Add(liste[i][j]);//abspeicherung der einzelnen Zeichen
                    }
                }

                for (int i = 0; i < liste.Count; i++) //Schleife die alle Strings druchläuft
                {
                    for (int j = 0; j <= liste[i].Length - 1; j++)//Schleife die die passenden Chars durchläuft
                    {
                        if (liste[i].Contains(list_c[j]))//Wenn der String das Zeichen enthält Zähler hoch
                        {
                            zähler++; 
                            zähler2++;
                        }
                        else // ansonsten Zähler runter
                        {
                            zähler--;
                        }
                    }
                    if (zähler2 != liste[0].Length)//Der Zähler muss ungleich sein, was nur  dann der Fall ist wenn ein Zeichen nicht im String vorgekommen ist.
                    {
                        if (zähler == liste[i].Length + liste[i - 1].Length)//Erklärt sich durch den ersten Else-Zweig
                        {
                            liste3.Add(liste[i]); //Liste mit zu löschenden Strings
                            zähler = liste[i].Length;//Zurücksetzen des Zählers
                        }
                        else
                        {
                            zähler = liste[i].Length;//Zurücksetzen des Zählers
                        }
                    }
                    else//Ausnahmefall für den ersten Durchlauf siehe if-Abfrage liste[i-1]
                    {
                    }
                }

hiermit habe ich nun die Möglichkeit für** nur den ersten** zerlegten string die Liste zu untersuchen ob die selben Zeichen in beliebiger Reihenfolge so nochmal vorkommen.
Wie ich selber weiss ist das keine schöne Lösung, das merkt man spätestens dann wenn man versucht zu implementieren das die Liste nicht nur mit der ersten Zerlegung sondern mit allen Zerlegungen in list_c die string Liste untersuchen soll.
Denn das ist so nicht möglich, das habe ich hinreichend versucht. Auch schlugen Versuche die Untersuchung mit strings zu machen fehl.

Es muss doch irgendwie eine schöne Lösung für mein Problem geben oder 🤔

Ich würde den ersten String nehmen und in ein char-Array zerlegen. Dann durch das Array gehen und die einträge in ein Dictionary speichern bzw. hochzählen.
Dann durch jeden Eintrag gehen und mit Regex überprüfen, ob der Character genauso oft im zweiten String vorkommt, wie im Dictionary gespeichert.

Hi,

eine relativ kurze, wenn vielleicht auch nicht die performanteste Variante wäre wie folgt:

var list = new List<string>();
list.Add("abc");
list.Add("cba");
list.Add("xyzxyz");
list.Add("zxxabc");
list.Add("zyc");
list.Add("zyxxx");

var rmList = new List<int>();

// Nur die unterschiedlichen Zeichen aufsteigend sortiert in einem neuen Objekt halten, sortieren und gruppieren
// Jede Groupe mit Count > 1 enthält Duplikate. Die Indizes der Originalliste werden dann vermerkt
foreach(var itm in list.Select((s, i) => new { Item = new string(s.Distinct().OrderBy(c => c).ToArray()), Index = i }).GroupBy(f => f.Item).Where(g => g.Count() > 1))
	rmList.AddRange(itm.Skip(1).Select(f => f.Index));

// Duplikate aus Liste löschen
for (int i = rmList.Count - 1; i >= 0 ; i--)
	list.RemoveAt(rmList[i]);

Edit: Oder viel übersichtlicher in zwei Zeilen (ohne temporäre Liste) 😄

foreach(var indexToDelete in list.Select((s, i) => new { Item = new string(s.Distinct().OrderBy(c => c).ToArray()), Index = i }).GroupBy(f => f.Item).Where(g => g.Count() > 1).SelectMany(f => f.Skip(1).Select(x => x.Index)).OrderByDescending(f => f))
	list.RemoveAt(indexToDelete);

Hey falsecode,

Mal ne Verständnisfrage... Du hast ne Liste vom Typ string, welche mit n-Elementen gefüllt ist. Das Problem ist nu, dass Elemente doppelt vorkommen?

Vielen dank euch für eure prompte Hilfe.

@Sarc und Jamikus
Wenn ich ehrlich bin blicke ich nicht durch deinen Code durch. Allerdings kann ich überprüfen ob er theoretisch das richtige macht. Das ist leider nicht der Fall. Da ich wie gesagt den Code nicht wirklich verstehe fällt mir eine Fehleranalyse auch sehr schwer.

Ich umschreibe mal eben den Test den ich deinen Dreizeiler (kompliment) unterzogen habe.

Es handelt sich bei dem String Array um ein Array was ein Texas Holdem Poker Deck mit allen möglichen Händen (2652) entspricht. Es gibt im Poker 13 verschiedene Kartentypen mit je vier Farben. Daraus folgen 52 unterschiedliche Karten. Eine Hand besteht aus zwei Karten, da es keine Karte doppelt gibt resultieren daraus 51 Partner für die erste Karte. Also 52*51 was 2652 Möglichkeiten ergibt. Da man natürlich unter den 2652 Möglichkeiten Kombinationen hat die es schon gab ergibt sich eine Fakultät von 2 (2!). Es bleiben 1326 mögliche Hände.

Lange Rede kurzer Sinn, das Array müsste am Ende 1326 Elemente enthalten, die so aussehen könnten z.B.: "A1Q3" [Karte,Farbe,Karte,Farbe].

Dein Quellcode gibt allerdings 558 Hände aus und lässt somit einiges verschwinden.
Mit dem Debugger komme ich leider nicht weit außer ich schaue mir 2652 Durchläufe an, wenn du nochmal die Nerven hast würde ich also bitten nocheinmal drüber zu schauen. Ich versuche nicht böswillig nach 4c [Hinweis] Wie poste ich richtig? zu handeln, blicke nur halt nicht durch 😁

         Hier mal ein kleines Beispiel um zu zeigen was weg fällt.  
         Wir nehmen mal alle vier Asse, A1, A2, A3, A4.  
         Als erstes nehmen wir alle Möglichkeiten für A1.  
         A1 A2  
         A1 A3  
         A1 A4  
         Die Kombi A1 A1 gibt es natürlich nicht, als nächstes A2  
         A2 A3  
         A2 A4  
         Die anderen Kombis sind schon abgedeckt und zuletzt A3  
         A3 A4  
         Nun sind sämtliche Möglichkeiten ausgenutzt und so ein   
         Ergebnis strebe ich mit meinen Code an.  

lg falsecode

Hallo falsecode,

was hälst du davon alle strings in der Liste alphabetisch zu sortieren. aus "azhfba" wird "aabfhz".

Dann kannst du doppelte einfach rausfiltern. (Beispielsweise mit Hashset.Add. Der sagt einem, ob der String schon drin ist oder nicht)

wenn du nochmal die Nerven hast würde ich also bitten nocheinmal drüber zu schauen. Ich versuche nicht böswillig nach 4c [Hinweis] Wie poste ich richtig? zu handeln, blicke nur halt nicht durch

Abgesehen davon, dass es genau das ist, ob böswillig oder nicht ist egal, ist es nicht unsere Aufgabe, dir Linq beizubringen. Setze dich bitte damit auseinander.

Gruss

Coffeebean

Wenn ich das ganze alphabetisch sortiere zerstöre ich damit erstmal die ganze Logik.
Natürlich könnte man das ganze danach wiederherstellen, ich probiere mal eben aus ob ich damit auf meine 1326 komme.

Um die nervösen Moderatoren zu beruhigen, wenn man mir ein Codesnippet als Hilfe anbietet, wird sich der Anbieter bewusst sein das möglicherweise nochmal hinterher gefragt wird.

@Coffebean
Ich hatte nicht nach Linq gefragt, wollte nur meine Optionen abwägen, etwas vorzukauen ist natürlich nicht die Aufgabe von irgendjemanden hier.

Also wenn deine Strings immer so aussehen wie beschrieben (4 Zeichen ala "A1Q2" etc.), dann kannst du dir einen Comparer schreiben, der erkennt, dass "A1Q2" das gleiche ist wie "Q2A1".

So in etwa wie hier:

public class DummyComparer : IEqualityComparer<string>
{
	public bool Equals(string x, string y)
	{
		return x.Equals(y) || (x.Substring(0, 2) == y.Substring(2, 2) && x.Substring(2, 2) == y.Substring(0, 2));
	}

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

Damit kannst du dann einfach über die Distinct-Methode die Duplikate filtern:

var list = new List<string>();
list.Add("A1Q1");
list.Add("A2Q1");
list.Add("Q1A1");
list.Add("Q2A2");
list.Add("Q1A2");

var res = list.Distinct(new DummyComparer()).ToArray();

@Sarc
Fun Fact am Rande der Quellcode geht nicht, ist mir zwar unerklärlich aber lediglich die doppelten Einträge werden entfernt. Es werden zwar als Objekte nur die richtigen returnt aber Distinct verschluckt die Information. Oder ich bin mal wieder zu blöd.

aber lediglich die doppelten Einträge werden entfernt

Ich dachte genau darum ging es dir? Du wolltest doch beispielsweise "Q2A1" aus der Liste nehmen, wenn "A1Q2" bereits vorhanden ist. Ansonsten erklär doch mal genau, was du jetzt möchtest.

Wenn ich das ganze alphabetisch sortiere zerstöre ich damit erstmal die ganze Logik. Welche Logik? A1Q1 ist in deinem Fall ja auch Q1A1. Egal wie herum Du das sortierst. Der "Spieler" kann auf seiner Hand auch jederzeit die Kartenreihenfolge wechseln ohne das sich seine Hand dadurch ändert.
...Natürlich könnte man das ganze danach wiederherstellen... Was überhaupt keinen Sinn ergeben würde (siehe oben).
...Um die nervösen Moderatoren zu beruhigen, wenn man mir ein Codesnippet als Hilfe anbietet... Die Beiträge hier sind als Denkanstoß zu verstehen. Hier zeigt man dir normalerweise nur die Richtung. Den Rest musst Du dir schon selbst erarbeiten. Nur so wirst Du auch verstehen was Du da gerade machst.

Zurück zum Thema.
Ich persönlich wurde deine Liste erst einmal sortieren (wie bereits weiter oben vorgeschlagen) und das ganze dann in ein Hashtable oder eine Sorted List packen.
Da Du ja nur jeweils 2 Karten in Kombination hast bietet sich das an.

Hallo falsecode,

die Sortierung (der Karten innerhalb der Hand) bewirkt eine Normierung, die sicher nicht nur im Bezug auf das Finden von Duplikaten sinnvoll ist.

Möglicherweise gelingt es sogar schon bei der Generierung, die Hände normiert zu erstellen.

Die Sortierung (in Kombination mit einem Hashset) hat zudem gegenüber der Verwendung eines Comparers bei der Erkennung von Duplikaten den Vorteil, dass bei ebendieser nur linearer statt quadratischer Aufwand entsteht, was insbesondere bei großen Listen von entscheidender Bedeutung ist.

Die Eingangsfrage ist zwar ok, aber die Nachfragen kollidieren mit [Hinweis] Wie poste ich richtig? Punkt 1.1.1. Spätestens jetzt ist wirklich alles relevante gesagt. Der Thread ist ohnehin schon lang und würde sich wohl nur noch weiter unnötig in die Länge ziehen, womit keinem geholfen ist, im Gegenteil.

herbivore