Nie wiem jak to ująć.

Hej, mam problem z którym nie potrafię sobie poradzić. Język C# ale to nie ma znaczenia.

Mam listę takich obiektów:

class Wiersz
{
    string KolumnaA;
    string KolumnaB;
}

I mam przetworzyć całą liste tak aby łącznie w KolumnaA i **KolumnaB **była parzysta liczba tych samych wartości (niepotrzebne usunąć).

W sensie jak łącznie w **KolumnaA **są 2 wartości **"lala" **i łącznie w KolumnaB jest 1 wartość "lala", to w wyniku ma zostać łącznie 1 "lala" w KolumnaA i łącznie 1 "lala" w KolumnaB.

Nie jestem pewien czy dobrze rozumiem - ma być po równo w kolumnie A i B?
Nie wiem czy to optymalne rozwiązanie, ale pierwsze co mi przychodzi do głowy to:

Utworzyć listę unikalnych słów występujących w obu kolumnach
Poiterować po tej liście -  dla każdego słowa:
   zliczyć wystąpienia słowa w kolumnie A i B i wziąć mniejszą wartość, 
   zapisać różnicę (np. dif = |CountA-CountB|);
   until dif>0: poiterować po liście obiektów: przy każdym wystąpieniu słowa w kolumnie gdzie było za dużo słów usunąć je i zdekremetować dif

Na tyle na ile rozumiem to co napisales musisz zebrac wartosci z obu kolumn, zliczyc powtarzajace wystapienia czyli jezeli wartosclala wystepuje > 1. A nastepnie tam gdzie jest jej wiecej usuwac nadmiar wartosci. Tylko to usuwanie musisz zrobic na sam koniec iteracji.
Co dla przypadku wartosci w kolumnie A gdy taka wartosc nie wystepuje w B? Usuwasz ja zeby bylo 0 elementow?

Co masz zrobić jeżeli w kolumnie A jest 3 wartości "WTF" zaś w kolumnie B jest 5 wartości "WTF" czyli razem jest parzystailość

_13th_Dragon napisał(a):

Co masz zrobić jeżeli w kolumnie A jest 3 wartości "WTF" zaś w kolumnie B jest 5 wartości "WTF" czyli razem jest parzystailość

Nie doprecyzowal pytania. Z postu mozna wynikac, ze redukcja ma zostac przeprowadzona do 1 wartosci - kiepski przyklad ze zbyt mala roznica elementow.
Jezeli jednak wartosci maja sie zgadzac w rownym przedziale to nalezy z tych 5 usunac az dwie takie same.

Dzięki za zainteresowanie :)

Jeżeli w jednej kolumnie są 3 przypadki, a w drugiej 5, to wtedy po obu powinno być 3. Jeżeli w jednej 0, a w drugiej 1, to w obu 0.

Generalnie optymalizacja nie ma znaczenia, może się to robić najgorszą metodą jaka istnieje.
Przerasta mnie to i w ogóle nie potrafię tego rozwiązać.

Byłbym wdzięczny za pseudokod / opis przykładowego rozwiązania :P

Co robić jeżeli wyszła różna ilość elementów w kolumnach?
Jak się usuwa wiersz, zostaje w nim wartość pusta?

Jeżeli łącznie w **KolumnaA ** są 3 elementy "lala", a w KolumnaB 5 elementów "lala", to trzeba usunąć całe 2 obiekty Wiersz tam gdzie w KolumnaB jest "lala" , aby było po równo.

Jak się usuwa obiekt wiersz to po prostu już nie jest potrzebny.

Złożone to strasznie.
Spróbuje z tym algorytmem co mi podesłał @piotrevic, mówi że powinno działać.

"lala" "wtf"
"lala" "abc"
"one" "lala"
"wtf" "one"
jakie jest poprawne rozwiązanie?

"lala" "wtf"
"one" "lala"
"wtf" "one"

Nawet jeśli usunięcie wiersza zepsuje jakąś parę to nic nie szkodzi. To ma się dziać pokolei. Nie ważne, że jakaś para wcześniej została zepsuta po usunięciu wiersza.

And this?
"lala" "wtf"
"one" "lala"
"lala" "abc"
"wtf" "one"

"lala" "wtf"
"one" "lala"
"wtf" "one"

usunięte: "lala" "abc"

lub:

(nic)

bo ma losowo usuwać wiersze. Może być tak że wszystkie się popsują. I wszystkie się usunie.

1. Czy problem, który chcesz rozwiązać jest oryginalnym problemem, czy taki sobie wymyśliłeś jako etap rozwiązywania innego problemu? (Jakiego?)
2. Jak duża może być lista wejściowa?

1. Oryginalny problem. To jest cały problem, nie jest częścią.
2. Lista wejściowa około kilka tysięcy.

#include <iostream>
#include <vector>
#include <map>
using namespace std;

struct Data { string lf,rt; };

void optimize(vector<Data> &result)
{
   map<string,size_t> maplf,maprt;
   for(Data d:result) ++maplf[d.lf];
   for(Data d:result) ++maprt[d.rt];
   for(bool f=true;f;)
   {
      f=false;
      for(vector<Data>::iterator i=begin(result);i<end(result);++i)
      {
         //cout<<i->lf<<"<=>"<<i->rt<<": "<<maplf[i->lf]<<">"<<maprt[i->lf]<<" || "<<maplf[i->rt]<<"<"<<maprt[i->rt]<<endl;
         if((maplf[i->lf]>maprt[i->lf])||(maplf[i->rt]<maprt[i->rt]))
         {
            //cout<<"remove"<<endl;
            --maplf[i->lf];
            --maprt[i->rt];
            result.erase(i);
            f=true;
            break;
         }
      }
      //if(f) cout<<"more"<<endl;
   }
}

int main()
{
   vector<Data> result=
   {
      {
         {"lala","abc"},
         {"lala","wtf"},
         {"one","lala"},
         {"wtf","one"},
      }
   };
   optimize(result);
   for(const Data d:result) cout<<d.lf<<'\t'<<d.rt<<endl;
 
   return 0;
}