[C++] Wypisywanie wszystkich możliwych kombinacji

Jachu · Post autor: **Jachu** » 31 gru 2009, o 21:39

Czy ktoś wie jak napisać program, który wypisuje mi wszystkie kombinacje/ustawienai poszczególnych znaków.

Chodzi o coś takiego że mam mieć wyraz 10 literowy. I na każdym miejscu maja stać konkretne liter (podane z klawiatury). Na każdym miejscu 2, a więc np.
pierwsze miejsce: a, b
drugie miejsce e,f
itd.

Powinno mi wyjść 1024 "wyrazy" oczywiście większość z nich będzie zlepkiem nic nieznaczących liter wyłuskać z tego wyrazy umiem, ale nie wiem jak zrobić te wszystkie kombinacje.

Próbowałem pisać to w pętlach, ale chyba się nie da, a wypisywać wszystkie kombinacje ręcznie to bym chyba wcześniej się zestarzał.

Post autor: **Dasio11** » 31 gru 2009, o 22:52

Można by spróbować z takim czymś:

Kod: Zaznacz cały

char a[10], b[10];
int i, j, l=0;

for(i=0; i<10; i++)
  {
  printf("Podaj litery dla %d-ego miejsca: ", i+1);
  scanf("%c %c", &a[i], &b[i]);
  }
  

for(i=0; i<1024; i++)
  {
  for(j=512; j>0; j/=2)
    {
    if(i & j) cout << a[l]; else cout << b[l];  
    l++;
    }
  l=0;
  cout << endl;
  }

Zapuściłem i działa, ale nie robiłem większych testów...

Jachu · Post autor: **Jachu** » 1 sty 2010, o 16:42

Dzięki, nie spodziewałem się że to może być taki krótki kod. Co prawda tez go nie do końca przetestowałem bo muszę wpisać to do pliku bo w tym oknie dev-a jest tylko kilka ostatnich linijek.

No tak szczerze mówiąc to nie bardzo rozumiem sam ten kod.
Możesz mi powiedzieć co robi ta instrukcja:

Kod: Zaznacz cały

if(i & j) cout << a[l]; else cout << b[l];

Chodzi mi o ten warunek ( w necie znalazłem ze to koniunkcja bitowa ), ale jak to działa to nie moge rozgryźć. (jak wyjdą mi same 0 to znaczy ze fałsz, a jak będzie jakaś jedynka to prawda, czy to złe rozumowanie) ?

No i jak by wyglądał ten program dla 3 lub 4 liter na każdej pozycji ?

Zrobiłem pełna listę do pliku i wychodzi coś takiego (na początku jest ok potem przez pewien czas są wyrazy 1 i 8 literowe, a potem znowu ok... co może być nie tak ?)

a234567890
a23456789i
a2345678h0
a2345678hi
a234567g90
a234567g9i
a234567gh0
a234567ghi
a23456f890
a23456f89i
a23456f8h0
a23456f8hi
a23456fg90
a23456fg9i
a23456fgh0
a23456fghi
a2345e7890
a2345e789i
a2345e78h0
a2345e78hi
(...)
a
34567890
a
3456789i
a
345678h0
a
345678hi
a
34567g90
a
34567g9i
a
34567gh0
a
34567ghi
a
3456f890
a
3456f89i
a
3456f8h0
a
3456f8hi
a
3456fg90
a
3456fg9i
a
3456fgh0
(...)
1234567890
123456789i
12345678h0
12345678hi
1234567g90
1234567g9i
1234567gh0
1234567ghi
123456f890
123456f89i
123456f8h0
123456f8hi
123456fg90
123456fg9i
123456fgh0
123456fghi
12345e7890
12345e789i
12345e78h0
12345e78hi
12345e7g90
12345e7g9i
12345e7gh0
12345e7ghi

szatkus · Post autor: **szatkus** » 1 sty 2010, o 16:53

Działają tak jak w logice.
\(\displaystyle{ (1100)_{2} \& (0110)_{2} = (0100)_{2}}\)
Czyli jedynka wychodzi tylko na pozycji, gdzie jedynka jest w obu liczbach, w innym wypadku 0.

Jachu · Post autor: **Jachu** » 1 sty 2010, o 17:03

Jak dział koniunkcja to ja wiem, ale jak to się przekłada na ten program już nie.

bo tam mam fi(a & b) i koniec warunku. Czyli co dla jakich wyników jest wykonywane ? Np. co funkcja zrobi jak wyjdzie wynik a & b = 0010 ?

szatkus · Post autor: **szatkus** » 1 sty 2010, o 17:09

Też nie wiem, trochę to zakręcone, ja bym zrobił to rekurencyjnie. Jest bardziej intuicyjne i dla rozsądnych długości wyrazów stos wytrzyma.

Kod: Zaznacz cały

void wyraz(String s, int n, char a, char b)
{
s2 String;
if ( n >0 )
{
s2=s+a;
wyraz(s2, n-1, a, b);
s2=s+b;
wyraz(s2, n-1, a, b);
} else cout << s << endl;
}

Nietestowane, może wymagać poprawy.

abc666 · Post autor: **abc666** » 1 sty 2010, o 18:41

Możesz utworzyć sobie tablice 10-elementową w której będziesz w każdym kroku dodawał jakby pisemnie w danym systemie o podstawie takiej jak liczba znaków na dane miejsce. Do tego dwuwymiarowa tablice ze znakami i np. dla dwóch znaków w
tab[0] masz znaki na pierwsza pozycję, w tab[1] na drugą itd. No i teraz masz tą tablice do dodawania, startujesz z samymi zerami czyli wyświetlasz na każdym miejscu tab[0].

Nasza tablica wygląda tak graficznie
\(\displaystyle{ [0][0][0][0][0][0][0][0][0][0]}\)
Dodajemy jedynkę i mamy
\(\displaystyle{ [1][0][0][0][0][0][0][0][0][0]}\)
wiec na pierwszym miejscu wyświetlamy literę druga, a na reszcie pierwszą, znowu dodajemy i dostajemy
\(\displaystyle{ [2][0][0][0][0][0][0][0][0][0]}\)
ale w naszym systemie oznacza to przekroczenie wiec dostajemy
\(\displaystyle{ [0][1][0][0][0][0][0][0][0][0]}\)
itd.
Przekroczenia można obsłużyć w prościutkiej pętli for, bo zawsze dodajemy tylko jeden. Nasze wyświetlanie kończymy gdy po dodaniu kolejnej jedynki nasza tablica się wyzeruje, lub wcześniej gdy mamy same jedynki (lub większą liczbę w zależności od liczby znaków).

W taki sposób możesz napisać program dla dowolnej liczby znaków na miejsce.

Post autor: **Dasio11** » 1 sty 2010, o 19:08

Chodzi o to, że najpierw liczba "i" przechodząc po wszystkich liczbach o 0 do 1023 przyjmie wszystkie możliwe kombinacje zer i jedynek w swoich 10 ostatnich cyfrach w systemie dwójkowym. Potem puszczamy pętlę z "j"-em, który przechodzi przez takie wartości (w systemie dwójkowym):

1000000000=512
0100000000=256
0010000000=128
...
0000000010=2
0000000001=1

Czyli endując (tak się nazywa operacja \(\displaystyle{ \&}\)) "i" z "j" w drugiej pętli, po prostu sprawdzamy wartość 10-ciu bitów liczby "i" po kolei, przy czym interesuje nas tylko czy wynik endowania jest zerem czy nie. Ponieważ "i" przejdzie przez wszystkie kombinacje ustawień zer i jedynek, to w większej pętli otrzymamy wszystkie możliwe dziesiątki wyników (każdy wynik będzie odpowiadał jednej literze w słowie, czyli 10 wyników to wyraz), z których każdy może być równy 0 lub 1 (litera pierwsza bądź druga). Np. przypuśćmy, że na każdym miejscu tekstu idącego na wyjście ma być "a" lub "b". Dla i=705, otrzymamy taki wynik:

1011000001 =705

więc na wyjście wychodzi

abaabbbbba

Dla możliwych trzech czy czterech liter na pozycji można użyć tablic dwuwymiarowych.
Drugi wymiar będzie pełnił taką funkcję jak w poprzednim kodzie (pozycja litery w słowie, \(\displaystyle{ 1 \le l \le 10}\)), za to pierwszy wymiar będzie mówił, której litery chcemy użyć (\(\displaystyle{ 1 \le k \le 4}\)). Potrzebna też będzie zmiana systemu na czwórkowy, bo na każdym miejscu mogą być cztery litery, tak jak w systemie czwórkowym - cztery cyfry.
Problem tylko jak z-endować coś w systemie czwórkowym... Może wziąć dwójkowy, ale porównywać 2 cyfry za każdym razem?

Jachu · Post autor: **Jachu** » 1 sty 2010, o 20:14

Dzięki wszystkim za odpowiedź, muszę to w wolnej chwili wszystko na spokojnie przeanalizować i może się uda napisać ten program

smiechowiec · Post autor: **smiechowiec** » 1 sty 2010, o 22:57

Można nieco uprościć kod Dasio11

Kod: Zaznacz cały

#include <stdio.h>

#define DLUGOSC 10

char a[DLUGOSC][3];
int i, j, l=0;

int main() {
	
  for(i = 0; i < DLUGOSC; i++)  {
    printf("Podaj 2 litery dla %d-ego miejsca: ", i + 1);
    scanf("%s", a[i]);
  }
  puts("");
 
  for(i = 0; i < DLUGOSC; i++) 
    printf("[%s]", a[i]);
  puts("");

  for (i = 0; i < (1 << DLUGOSC); i++) {
	for (j = 0; j < DLUGOSC; j++ )
	  printf("%c", a[j][(i & (1 << j)) != 0]);
	puts("");
  }
  return 0;
}

Wynik dla DLUGOSC = 3
Podaj 2 litery dla 1-ego miejsca: ab
Podaj 2 litery dla 2-ego miejsca: cd
Podaj 2 litery dla 3-ego miejsca: ef

[ab][cd][ef]
ace
bce
ade
bde
acf
bcf
adf
bdf

D_E_F_F · Post autor: **D_E_F_F** » 20 lut 2012, o 20:19

Witam,
Jak możne zmodyfikować ten program aby podawać pojedyncze znaki np. a, b, c i żeby wypisał wszystkie możliwe kombinacje wyrazu dwu literowego.

aa, ab, ac, ba, bb, bc, ca, cb, cc

Grzesio_ · Post autor: **Grzesio_** » 20 lut 2012, o 21:33

Kod: Zaznacz cały

main() {
        char t[]="abCde";
        int i, k=1, n, x[100], m;
        n=strlen(t);
        m=2; scanf("%d", &m);
        if( m>n ) m=n;
        x[1] = 1;
        while (k) {
                if( k==m ){
                        for( i=1; i <= k; i++ ) 
                                putchar(t[x[i]-1]);
                        puts(""); }
                if ( x[k] == n ) {
                        k--;
                        x[k]++;
                } else {
                        k++;
                        x[k] = x[k-1] + 1;}}
        return 0;}

D_E_F_F · Post autor: **D_E_F_F** » 20 lut 2012, o 21:57

a jakie #include są potrzebne bo wyrzuca błędy w DEV C++-- 20 lut 2012, o 22:04 --Do DEV C++
#include <cstdlib>
#include <iostream>
#include <windows.h>
#include <stdio.h>
i działa

Jak to rozbudować aby mogły byś dłuższe "słowa"

Grzesio_ · Post autor: **Grzesio_** » 22 lut 2012, o 01:57

po pierwsze primo, założę że pytanie skierowane jest do mnie

więc

start | DEV-c++ | uninstal
bo w jakim celu trzymać coś co z założenia jest wadliwe i dawno opuszczone

wyGooglać sobie coś sensowniejszego, np. "codeBlocks"
a wtedy gdy po F9 zapyta o nazwę dopisać po kropce C
bo gdy napiszesz tylko np. "dupa" to będzie to "dupa.c++"
a wtedy nie "h" tylko "c", np. nie <stdio.h> tylko <cstdio>
a samo C jest tolerancyjne, nie zachowuje się jak słabo opłacana księgowa

zauważ, że moja zabawka pyta o m <= n == strlen(t)