Generowanie permutacji - dlaczego kod nie działa prawidłowo?

2015-01-29 21:35
0

Czy mógłby ktoś rzucić okiem na kod i napisać dlaczego program nie działa? Sam nie widzę błędu a pewnie dla kogoś ogarniętego w temacie będzie on ewidentny

#include <iostream>
#include <string>
using namespace std;

void generuj_permutacje(string zrodlo,string tworzacy)
{
    if(zrodlo.length() == 0)
    {
        cout<<tworzacy<<endl;
    }
    else
        for(int i = 0; i<zrodlo.length(); i++)
        {
            tworzacy+=zrodlo[i];
            zrodlo.erase(i);
            generuj_permutacje(zrodlo,tworzacy);
        }
}

int main()
{
    string zrodlo = "abcd";
    string tworzacy = "";
    generuj_permutacje(zrodlo,tworzacy);
}

Pozostało 580 znaków

2015-01-30 01:23
0

permutacja to jest wg. mnie dość trudna sprawa, aby się na niej uczyć rekurencji, ale pokażę Ci jak można to zrobić

#include <iostream>
#include <vector>
#include <string>

void permutation(std::string const& word, std::string& result, std::vector<std::string>& results)
{
    if(word.size() == 0) {
        results.push_back(result);
        return;
    }

    for(auto it = std::begin(word) ; it != std::end(word) ; ++it) {
        std::string shortenWord;
        std::copy(std::begin(word), it, std::back_inserter(shortenWord));
        std::copy(it + 1, std::end(word), std::back_inserter(shortenWord));
        result += *it;
        permutation(shortenWord, result, results);
        result.erase(std::end(result) - 1);
    }
}

int main()
{
    std::string word = "ABCD";
    std::string permutationWord = "";
    std::vector<std::string> results;
    permutation(word, permutationWord, results);

    for(auto const& word : results) {
        std::cout << word << std::endl;
    }
}

http://melpon.org/wandbox/permlink/dnoNx0sVX7lCTJvT

Pozostało 580 znaków

2015-01-30 04:46

Albo prostsza w zrozumieniu wersja (zmodyfikowana Twoja wersja):
http://ideone.com/mFSD2k

Twoje bledy:

  • erase standardowo usuwa wszystkie znaki od podanego do konca (podaj dwa parametry jak nie chcesz tego - a nie chcesz)
  • w petli nie mozesz zmieniac aktualnego stanu - operuj na kopiach (alternatywnie mozesz dodac parametr mowiacy o tym, ktore znaki sa juz uzyte)

lepsza wersja permutacji jest taka, ze nie wymaga rekurencji i jest zaimplementowana w bibliotece standardowej. Przyklad z uzyciem w dokumentacji:
http://www.cplusplus.com/reference/algorithm/next_permutation/


░█░█░█░█░█░█░█░█░█░█░█░
edytowany 2x, ostatnio: krwq, 2015-01-30 04:48
no ja nie wiem, czy ta wersja jest prostsza do zrozumienia, kiedy w sumie nie jesteś w stanie trackować nic, bo co iterację masz nowe obiekty, ja wolę wersję z iteratorami, ale i tak 1 raz widzę to na (intach), działąjące - gośćabc 2015-01-30 12:08

Pozostało 580 znaków

2015-01-31 13:33
0

Dziękuje

Pozostało 580 znaków

Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0