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

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);
}
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

3

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/

0

Dziękuje

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