• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

wszystkie możliwe kombinacje liter C++ (poprawa kodu i inne sposoby)

+1 głos
217 wizyt
pytanie zadane 13 września w C i C++ przez Jakub 0 Gaduła (3,800 p.)

Hej, napisałem prosty program dokonujący kombinacji na literach ,po prostu wpisze wszystkie możliwe ich ułożenia dzięki czemu powstaną też sensowne wyrazy . Program jest bardzo ograniczony i wypisuje tylko 4 literowe wyrazy z użyciem wielkich liter. Oczywiście potrafię to rozwinąć o większe możliwości ale zanim to zrobię muszę zadbać nieco o kod :) Oto on:

#include "stdafx.h" //Napisane w VS

using namespace std;

const int n = 25;

int main()
{
	char numbers[n]; //jakas tablica liter (tylko te duze dla uproszczenia)
	
	for (int i = 0; i < n; i++) //nadawanie im wartosci z tablicy asci
		numbers[i] = i + 65;

	for (int i = 0; i < n; i++) //wypisujemy po cztery litery (dla wiekszej ilosci to by byla zmora)
		for (int j = 0; j < n; j++)
			for (int k = 0; k < n; k++)
				for (int e = 0; e < n; e++) {
					cout << numbers[i] << " " << numbers[j] << " " << numbers[k] << " " << numbers[e] << endl; //wypisywanie danej kombinacji

					if (numbers[i] == 'J' &&numbers[j] == 'U' &&numbers[k] == 'D' &&numbers[e] == 'A') { //dla eksperymentu zatrzymaj sie kidy znajdziez taki wyraz 
						_getch();
					}
				}
	return 0;
}

Problem jest głównie w zagnieżdżonych w sobie pętlach (tyle ile ich jest tyle jest liter w wyrazie) . Oczywiście teraz wyraz jest tylko 4 literowy ale np dla "losowania" całych zdań (tak też zamierzam zrobić) bedzie trzeba użyć przykładowo 20 pętli ,to trochę mało fajne i czytelne :/ . Czy można to jakoś ominąć ,albo może inaczej: Czytelnie ułóżyć ten kod, użyć innego algorytmu ,jak tak to jakiego? . Z góry dziękuje za pomoc i pozdrawiam :)

1
komentarz 13 września przez Knayder Nałogowiec (26,050 p.)
Nie wiem jak ty sobie wyobrażasz losowanie cały zdań!?
Jest 26 liter w alfabecie, a więc przy 20 znakowym zdaniu, takie losowanie to
26^20 przejść pętli.
1.9928149e+28
19928149000000000000000000000.
Tyle raz musi przejść pętla.

Tak na oko policzyłem: Jest to około
3.475546e+17 lat.
347554600000000000 lat

To jest 26329894 razy więcej niż istnieje wszechświat :)

Powodzenia :D
komentarz 13 września przez Jakub 0 Gaduła (3,800 p.)
edycja 13 września przez Jakub 0
No... przesadziłem ,ale tam 7 literowe frekwencje powinny przejść ,to mi liczyło ok 3 min (dokładnie nie wiem bo nie liczyłem ) . Cóż teraz pomyślałem ze to rośnie dość szybko bo o ile moja matma się nie myli to wychodzi n^2 . Ale na kwantowym kompie by przeszło :)

* po za tym nie zależy mi tak bardzo by działanie programu zostało ukończone przed moją śmiercią ... :D ,po prostu będę miał radość że to działa (i że kod jako tako wygląda)
1
komentarz 13 września przez Hipcio Nałogowiec (46,520 p.)

Jakub takie zagnieźdzone pętle idzie uprościć do dwóch pętli (albo nawet jednej) - patrz link. Ewentualnie mógłbyś to też zrobić za pomocą rekurencji.

komentarz 13 września przez Jakub 0 Gaduła (3,800 p.)
dzięki ,z rekurencją mogą być kłopoty ale spróbuje ...

4 odpowiedzi

+2 głosów
odpowiedź 13 września przez Hipcio Nałogowiec (46,520 p.)
wybrane 14 września przez Jakub 0
 
Najlepsza

Można np tak:

#include <iostream>
#include <string>

bool next_combination(std::string& word, char first = 'A', char last = 'Z')
{
	size_t i = word.size() - 1;
	for (++word[i]; i > 0 && word[i] >= last + 1; ++word[i])
		word[i--] = first;
	return word.front() != last + 1;
}

int main()
{
	std::string word(4, 'A');
	do {
		for (auto& i : word)
			std::cout << i << " ";
		
		std::cout << '\n';

		if (word == "ABEL") std::cin.get();

	} while (next_combination(word, 'A', 'Z'));
}
2
komentarz 13 września przez Ehlert VIP (105,150 p.)
String ok, ale nie rozumiem czemu inty przez referencję.
komentarz 14 września przez Jakub 0 Gaduła (3,800 p.)
Nie zbyt rozumiem jak działa funkcja next_combination . Będę wdzięczny za pomoc
1
komentarz 14 września przez Hipcio Nałogowiec (46,520 p.)
edycja 14 września przez Hipcio

#Ehlert dzięki za uwagi :)

#Jakub 0 Spróbuję trochę wytłumaczyć/zmącić (niepotrzebne skreślić)

- iteracja, która litera

word[i] - litera, wartość

Pętla przez większość przypadków dla testu 4 literowego od a-z wykona się tylko zero razy. Przed pętlą zmienia się litera. Jeżeli zaś przekroczy dozwolony zakres to pętla będzie zmieniać iteracje. Obsłuży przeskoczenie do kolejnej litery. Jeżeli zaś litera z "frontu" jest tym znakiem po 'Z' to znaczy, że już nie ma kombinacji i jesteśmy za daleko. Wcześniej w komentarzu wysłałem Ci link do podobnego przykładu tylko trochę z drugiej strony zrobionego (i trzeba było inty na chary zamieniać i vector na string). Ogólnie podobna zasada tylko więcej kodu i słabsza jakość :D

Ogólnie jak coś tłumaczę to nikt nie rozumie więc jak nie zrozumiesz to się nie przejmuj xd

Dla np next_combination(word, 'A', 'C') i dwuliterowego wyrazu startowego "AA" działanie funkcji wygląda następująco:

  1. Do funkcji wpada wyraz "AA". Iterator i wskazuje na ostatnią literę. Następuje instrukcja ++word[i] (ta w pierwszej komendzie pętli - chociaż mogłaby być przed nią) - czyli zwiększenie ostatniej litery (ascii i te sprawy wiesz o co chodzi). Mamy wyraz "AB". Pętla nie wykonuje się, bo warunek word[i] >= last + 1 jest nieprawdą. Litera word[i] jest z zakresu od A do C włącznie. Pętla nie wykonuje się. Funkcja zwraca true.
  2. Do funkcji wpada wyraz "AB". Powtarza się wyższa sytuacja.
  3. Do funkcji wpada wyraz "AC". Następuje ++word[i]. Mamy więc wyraz "AD". Spełnia to warunek word[i] >= last + 1 ('D'>='C'+1). Pętla zaczyna działanie. Czyli mamy literę spoza dozwolonego zakresu. Litera word[i] zamieniana jest na literę 'A' (first). Mamy wyraz "AA". Następnie iterator jest przestawiany o 1 w lewą stronę. Pętla wykonuje się dalej. Przechodzimy do 3 wyrażenia pętli - ++word[i]. Teraz zmieniana zostaje przedostatnia litera (ta na którą wskazuje iterator). Otrzymujemy wyraz "BA". Jako, że warunek i > 0 przestał być prawdą to pętla kończy się. Funkcja zwraca true.
  4. Patrz punkt 1 (BB)
  5. Patrz punkt 1 (BC)
  6. Patrz punkt 3 (CA)
  7. ...
  8. Gdy w funkcji przed returnem zmienna word ma wartość DA. Frontowa (przednia) litera jest spoza zakresu więc funkcja zwraca false. Pętla do ... while w mainie kończy swoje działanie.

 Podobnie dzieje się dla przypadków więcej niż 2-literowych. Wtedy pętla odpowiednio przeskakuje o kilka miejsc.

komentarz 14 września przez Jakub 0 Gaduła (3,800 p.)
Dzięki ,jeszcze pożądanie nie czytałem bo jestem w szkole ale widać ze sie napracowałeś :) ,daje naj i spróbować ogarnąć
komentarz 14 września przez Jakub 0 Gaduła (3,800 p.)
Noo... Dam naj jak będę w domu bo w telefonie coś sie nie da
komentarz 14 września przez Hipcio Nałogowiec (46,520 p.)
Cieszę się, że pomogłem ;) Moja odpowiedź wygląda teraz śmiesznie na tle tej niżej z 5 łapkami i wariancją bez powtórzeń :D
komentarz 14 września przez Jakub 0 Gaduła (3,800 p.)
Jakoś to rozwiązanie zrozumiałem :) ,kubek kawy i wytężenie mózgu przez 15 min ,w takich chwilach myślę sobie jaki ze mnie kiepski programista ): ... Ty sobie po kolei tworzysz nowe ciekawe rozwiązania a ja mam często problemy z ogarnięcie trywialnych rzeczy .Nie mam pojęcia jak się podciągnąć z algorytmiki - nie jestem pewien czy spoj wystarczy . Dziękuje za pomoc i pozdrawiam serdecznie
1
komentarz 14 września przez Hipcio Nałogowiec (46,520 p.)
Gdy pierwszy raz spotkałem się z generowaniem w taki sposób liter to zrobienie tego bez zagnieżdżonych pętli zajęło mi tydzień. Co w sumie też jakimś zadowalającym wynikiem nie było. Nic straconego by się podszkolić w algorytmach, zdobyć więcej doświadczenia itp ;) Pozdrawiam
+5 głosów
odpowiedź 13 września przez mokrowski Nałogowiec (32,640 p.)

Oczywiście można zawsze być wynalazcą koła... ale... 

#include <iostream>
#include <algorithm>
#include <string>

int main() {
    std::string message = "abrakadabra";
    do {
        std::cout << message << '\n';
    } while(std::next_permutation(message.begin(), message.end()));
}

 

1
komentarz 13 września przez Jakub 0 Gaduła (3,800 p.)
no tak... ale kiedy piszę sam coś takiego to ćwiczę algorytmikę (tak samo jak można stworzyć algorytm obliczający silnie a skorzystać z biblioteki cmath)
2
komentarz 13 września przez mokrowski Nałogowiec (32,640 p.)
edycja 13 września przez mokrowski
Ogólnie... bzdura :-)

Oczywiście każde rozwiązanie ma wady i zalety. Aspekt edukacyjny i produkcyjny/zawodowy. Zerknij jednak jak jest implementowane te std::next_permutation abyś wiedział czy pętle które proponujesz są efektywne czy nie. Podpowiem że nie i literatura zna wiele efektywniejszych algorytmów.

Z tym "ćwiczeniem algorytmów" to nie przesadzaj. Jeśli to ma być wymówka do "zrobię jak umiem a nie zerknę na opracowane efektywne rozwiązania", to nauka będzie... nieefektywna i będzie przypominała aspirującego pisarza który ma pomysł że sam nauczy się pisać dobre książki nie czytając innych bo (o zgrozo) mogą go zainspirować :-)
komentarz 13 września przez Jakub 0 Gaduła (3,800 p.)
zgadzam sie z tobą żeby nie zadowalać sie wyłącznie pierwszym niedopracowanym algorytmem . Właśnie dlatego zadałem to pytanie o treści co mogę tu zmienić i jak to inaczej napisać ...
komentarz 13 września przez Jakub 0 Gaduła (3,800 p.)
Po za tym często  muszę szukać gotowych implementacji i je zrozumieć bo własnych napisać nie umiem bez zobaczenia jakiegoś przykładu
+2 głosów
odpowiedź 13 września przez Ehlert VIP (105,150 p.)

Żeby uniknąć zagnieżdżania i zrobić program który docelowo sprawdzi wszystkie możliwe kombinacje potrzebujesz funkcji, która będzie generować kolejne warianty stringów zawierających odpowiednie znaki.

/**
 * Function returns next string in brute-force queue
 * Returning strings contain only printable chars
 * Examples
 * for " "      return "!"
 * for "~"      return "  "
 * for "~ "     return "~!"
 *
 * @param std::string src
 *
 * @return std::string next string
 */
std::string nextWord(std::string & src)
{
    std::string result = src;
    bool nextChar = true;
    for (auto iter = result.rbegin(); iter != result.rend(); ++iter) {
        if (*iter < 126) {
            (*iter)++;
            nextChar = false;
            break;
        } else {
            (*iter) = 32;
        }
    }
    if (nextChar) {
        result += ' ';
    }
    return result;
}
komentarz 13 września przez Ehlert VIP (105,150 p.)

Bardzo chętnie usłyszę opinię kogoś bardziej ogarniętego z C++ na temat tego rozwiązania cheeky

komentarz 14 września przez Jakub 0 Gaduła (3,800 p.)
Dzięki za pomoc ale tak słabo rozumiem działanie algorytmu . Czy mógł byś wytłumaczyć z grubsza jego  tok działania ? Z góry dziękuje
1
komentarz 14 września przez Ehlert VIP (105,150 p.)

Otwórz sobie tablicę ASCII i przetestuj. Dla ciągu abba zwróci abbb, abbc, abbd i tak dalej aż do ~~~~. Potem zacznie sprawdzanie od pięciu spacji "     ", "    !"  itd. 

+1 głos
odpowiedź 14 września przez mokrowski Nałogowiec (32,640 p.)
A ja proponował bym rozważyć inną drogę "nie kombinatoryczną". Jeśli wyrazy mają być sensowne (i w konsekwencji możliwe do poprawnego wymówienia), to obowiązują inne zasady niż brutalne generowanie zestawień liter. Raczej kombinacje spółgłosek, samogłosek, ich rodzajów. Np. wyraz "żaba" to "spółgłoska, samogłoska, spółgłoska, samogłoska" :-) A to tylko jeden ze wzorców ale "sensowniejszy językowo" niż "ffff" :-)
komentarz 14 września przez Jakub 0 Gaduła (3,800 p.)
dobra rada :) ,spróbuje napisać coś takiego dla ćwiczeń ... Swoją drogą napisałem ten algorytm by uzyskać taki efekt jak w programach do odgadywania haseł ,chociaż wiem że do tego jeszcze daleko :D

Podobne pytania

0 głosów
2 odpowiedzi 285 wizyt
pytanie zadane 19 grudnia 2016 w C i C++ przez Hipcio Nałogowiec (46,520 p.)
0 głosów
1 odpowiedź 136 wizyt
0 głosów
2 odpowiedzi 85 wizyt
pytanie zadane 10 marca w Inne języki przez hoktaur Pasjonat (18,670 p.)
Obowiązuje już zaktualizowany regulamin.

Czy wiesz, że nie musisz już odświeżać strony głównej?

Lista pytań i odpowiedzi aktualizuje się automatycznie!

38,576 zapytań

76,451 odpowiedzi

149,279 komentarzy

18,047 pasjonatów

Przeglądających: 264
Pasjonatów: 26 Gości: 238

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto dwie polecane książki warte uwagi. Pełną listę znajdziesz tutaj.

...