Problema de algoritmica - generare combinatii de nume

O problema de algoritmica de la job

Posted by anghelvalentin on September 12, 2019

La noul job mi s-a dat un task interesant, care mi-a luat ceva sa il rezolv. Tin minte si acum ca eram in facultate si ziceam cu alti colegi ca algoritmii aia pe care ii invatam nu o sa-i folosim niciodata. Ehee, ce prostii vorbeam.

Problema suna in felul urmator, trebuie sa generam pentru o persoana toate combinatiile sale de nume pentru a putea fi tiparite pe cardul de credit. Toate combinatiile trebuie sa include numele de familie al titularului. Intrucat cardul are o dimensiune fizica limitata, nu se accepta variantele care au mai mult de 20 de caractere.

Deci daca pe mine ma cheama Anghel Valentin Gabriel, variantele acceptate sunt:

  • Anghel Valentin
  • Valentin Anghel
  • Anghel Gabriel
  • Gabriel Anghel

Combinatia Anghel Valentin Gabriel nu este acceptata, deoarece are mai mult de 20 de caractere.

Cand ai o astfel de problema, primul gand ar trebui sa iti zboare la combinari si recursivitate. Noi trebuie sa combinam prenumele clientului, de aceea, putem avea combinari de 1..n, unde n este numarul de prenume pe care le are.

Deci avem o functie care este apelata de n ori.

for (int i = 1; i <= _firstNames.Length; i++)
{
   CompositionNames(string.Empty, i);
}

For-ul de mai sus poate fi explicat astfel: vrem combinatiile de i prenume.

Functia ce este apelata va fi cea recursiva si va functiona in felul urmator: conditia de oprire a recursivitatii este in momentul in care se apeleaza cu counter de 0 (adica combinari luate cate 0). Pe urma parcurgem vectorul de prenume si luam prenumele adaugate ceva in formarea combinarii (pentru primul apel de functie este empty). Daca stringul ce formeaza combinarea deja contine prenumele, nu l mai adaugam in string. In final apelam din nou functia cu stringul rezultat momentan si cu o combinare mai putin.

   private void CompositionNames(string result, int counter)
        {
            if (counter == 0)
                return;


            for (int j = 0; j < _firstNames.Length; j++)
            {
                StringBuilder stringBuilder = new StringBuilder(result);
                if (!result.Contains(string.Format("{0} ", _firstNames[j])))
                {
                    stringBuilder.Append(string.Format("{0} ", _firstNames[j]));
                }

                if (counter == 1)
                {
                    string finalName = stringBuilder.ToString().Trim();
                    if (!_firstNameCombinations.Contains(finalName))
                    {
                        _firstNameCombinations.Add(finalName);
                    }
                }
                CompositionNames(stringBuilder.ToString(), counter - 1);
            }
        }

Codul sursa