Elektroda.pl
Elektroda.pl
X

Wyszukiwarki naszych partnerów

Wyszukaj w ofercie 200 tys. produktów TME
Europejski lider sprzedaży techniki i elektroniki.
Proszę, dodaj wyjątek elektroda.pl do Adblock.
Dzięki temu, że oglądasz reklamy, wspierasz portal i użytkowników.

[C ] kombinacje zagnieżdżonej pętli for.

terencjoo 11 Lip 2009 15:37 2311 9
  • #1 11 Lip 2009 15:37
    terencjoo
    Poziom 12  

    A={a,b,c,d}
    B={1,2}
    C={x,y,z}
    D={k}
    E={9,8,7}

    Mam problem, nie umiem napisać zagnieżdzonej pętli for, która by mi generowała kombinacje elementów ze zbiorów np. takich jak wyżej (dla ułatwienia żeby pokazać o co mi chodzi oznaczyłem każdy zbiór innymi znakami, w rzeczywistości w programie same liczby to są). Czyli chodzi mi o to by otrzymać wszystkie możliwe kombinacje elementów ze zbiorów (w tej samej sekwencji nie może być 2 elementów z tego samego zbioru):
    a1xk9
    b1xk9
    c1xk9
    d1xk9
    a2xk9
    b2xk9
    itd.
    i mieć je w tabeli w taki sposób:
    tabela[0]=a
    tabela[1]=1
    tabela[2]=x
    tabela[3]=k
    tabela[4]=9

    tabela[5]=b
    tabela[6]=1
    tabela[7]=x
    tabela[8]=k
    tabela[9]=9

    tabela[10]=c
    tabela[11]=1
    tabela[12]=x
    tabela[13]=k
    tabela[14]=9
    itd.
    czyli co ilość_zbiorów powtarza się inna sekwencja kombinacji.

    Jakby dla kogoś to było łatwe to z góry dzięki. Dla mnie jest to mega kosmos, 2 godziny w plecy. Chyba, że to jest dla każdego mega kosmos i nie mam co się załamywać, że mi nie wychodzi, będę kombinował jeszcze samemu jak mi przejdzie dół, ale wracam tak co chwilę do tego i nic nie wychodzi no bo jak zaimplementować takie dziadostwo. Jakaś pewnie funkcja rekurencyjnie musi być. Na bank musi być referencyjnie jakaś funkcja, załóżmy, że mam w tabeli 2 wymiarowej te elementy czyli tabela ma taką postać dla powyższego przykładu:
    1111
    1100
    1110
    1000
    1110
    gdzie wiersze od 1 do ostatniego to zbiory A-E. I teraz problem sprowadza się do wyboru wszystkich kombinacji liczba_wierszów-elementowych spośród kolumn gdzie występuje 1.

    Post raportowany - regulamin, p. 11.2.
    Poprawiłem temat.
    [Dr.Vee]

  • Pomocny post
    #2 11 Lip 2009 17:25
    Dżyszla
    Poziom 42  

    Możesz też stworzyć swoisty licznik - określasz max wartości na poszczególnych pozycjach, a następnie inkrementujesz najmłodszą, a w przypadku przekroczenia wartości - w pętli zmieniasz starsze.

    Code:

    repeat
       inc(tab[4]);
       for i:=4 downto 0 do
          if tab[i]>max_idx[i] then begin
             if i=0 then exit;
             tab[i]:=0;
             inc(tab[i-1]);
          end else
             break;
    until false;

    Oczywiście zamiast inkremetnowania możesz po prostu podstawiać kolejne dozwolone wartości. No i wynik możesz przepisywać do drugiej tablicy - ta przedstawiona w przykładzie jest wyłącznie licznikiem.

  • Pomocny post
    #3 11 Lip 2009 18:11
    Demoman
    Poziom 17  

    To jest dobry pretekst żeby ruszyć VS po reinstalce systemu ;)

    Jako, że nie chciało mi się robić zagnieżdżania for'ów to wyszło coś takiego:

    Code:

    #include <iostream>

    using namespace std;

    int main()
    {
       int A[]={01,02,03,04};
       int B[]={11,12};
       int C[]={21,22,23};
       int D[]={31};
       int E[]={41,42,43};

       const int ileA = 4;
       const int ileB = 2;
       const int ileC = 3;
       const int ileD = 1;
       const int ileE = 3;

       const int ileKomb = ileA * ileB * ileC * ileD * ileE;

       int tabela[ileKomb * 5];

       for(int i = 0; i < ileKomb; ++i)
       {
          int temp = i;
          int index;

          index = temp % ileE;
          temp /= ileE;
          tabela[5*i + 4] = E[index];

          index = temp % ileD;
          temp /= ileD;
          tabela[5*i + 3] = D[index];

          index = temp % ileC;
          temp /= ileC;
          tabela[5*i + 2] = C[index];

          index = temp % ileB;
          temp /= ileB;
          tabela[5*i + 1] = B[index];

          index = temp % ileA;
          temp /= ileA;
          tabela[5*i + 0] = A[index];

       }

       for(int i = 0; i < ileKomb; ++i)
       {
          cout << tabela[5*i + 0] << " "
             << tabela[5*i + 1] << " "
             << tabela[5*i + 2] << " "
             << tabela[5*i + 3] << " "
             << tabela[5*i + 4] << " " << endl;
       }


       system("pause");
       return 0;
    }


    Co w wyniku daje takie cos:
    Code:

    1 11 21 31 41
    1 11 21 31 42
    1 11 21 31 43
    1 11 22 31 41
    1 11 22 31 42
    1 11 22 31 43
    1 11 23 31 41
    1 11 23 31 42
    1 11 23 31 43
    1 12 21 31 41
    1 12 21 31 42
    1 12 21 31 43
    1 12 22 31 41
    1 12 22 31 42
    1 12 22 31 43
    1 12 23 31 41
    1 12 23 31 42
    1 12 23 31 43
    2 11 21 31 41
    2 11 21 31 42
    2 11 21 31 43
    2 11 22 31 41
    2 11 22 31 42
    ...
    4 12 22 31 43
    4 12 23 31 41
    4 12 23 31 42
    4 12 23 31 43
    Aby kontynuować, naciśnij dowolny klawisz . . .


    O to chodziło? :)

  • #4 11 Lip 2009 19:25
    terencjoo
    Poziom 12  

    Demoman ty jesteś jakimś zawodowym programistą? bo tak to prosto zaprogramowałeś a o to chodziło. Ja kombinowałem z kilkoma pętlami for w sobie i mi nie wychodziło.

  • #5 11 Lip 2009 19:29
    Demoman
    Poziom 17  

    Nie, jeszcze nie jestem.

    Grunt to dobrze przemyśleć problem i potem to zaimplementować.

  • #6 13 Lip 2009 19:56
    terencjoo
    Poziom 12  

    Mam jeszcze jeden inny problem. Tym razem mam dwie tabele 1-wymiarowe np. postaci:
    pudelko[0]=2 -> indeks[0]=3
    pudelko[1]=2 -> indeks[1]=5
    pudelko[2]=2 -> indeks[2]=6
    pudelko[3]=3 -> indeks[3]=0
    pudelko[4]=3 -> indeks[4]=8
    pudelko[5]=5 -> indeks[5]=1
    pudelko[6]=6 -> indeks[6]=4
    pudelko[7]=6 -> indeks[7]=9
    pudelko[8]=10 -> indeks[8]=2

    Tabela po lewej stronie przechowuje mi liczbę, a tabela po prawej stronie przechowuje mi indeks, z którego będę tworzył kombinacje. I teraz muszę dla dowolnej liczby x tworzyć kombinacje x-elementowe z liczb z tabeli indeks, ale w ten sposób, żeby kolejne następujące po sobie kombinacje minimalizowały mi sumę wartości pudelko[i].
    Czyli dla przypadku powyżej dla x=3 kolejność będzie:
    indeks[0]indeks[1]indeks[2] czyli 356 suma=6
    indeks[0]indeks[1]indeks[3] czyli 350 suma=7
    358 suma=7
    560 suma=7
    568 suma=7
    608 suma=7
    351 suma=9
    itd.

    I nie wiem jak zrobić kod dla ogólnego przypadku, bo te tabele jak i ten x mogą być różne. Dane udało mi się posortować i teraz te nieszczęsne kombinacje, na których zawsze co by za problem z nimi był to utykam. Nie masz żadnego pomysłu takiego szybkiego jak by to robić?

  • Pomocny post
    #7 13 Lip 2009 22:09
    Demoman
    Poziom 17  

    Czyli masz jakieś liczby i dla nich masz jakieś takie wagi.
    Liczby mogą się powtarzać, wagi tez?

    Chcesz tworzyć kombinacje x-elementowe bez powtórzeń. To jest inny problem niż ten powyżej.

  • #8 13 Lip 2009 23:40
    terencjoo
    Poziom 12  

    Liczby z tabeli indeks nie mogą się powtarzać (tam mi się mylnęła 8 z 9), wagi (czyli te z tabeli pudelko) mogą się powtarzać (z tym że kombinacji tych wag nie generuje). Ponadto liczby i odpowiadające im wagi są jak widać uporządkowane. Teraz tylko mam problem z algorytmem generowania kombinacji x-elementowych bez powtórzeń w kolejności takiej by minimalizować sumę wag. Może się wydawać to proste, ale byłoby proste gdyby nie było wag.
    Wiem, że jest inny problem niż powyżej, bo inne zagadnienie to jest. Po prostu program pewien robię i różne rzeczy tam mam dziwne i między innymi teraz doszedłem do tej:)

  • Pomocny post
    #9 14 Lip 2009 00:19
    Demoman
    Poziom 17  

    Wyznacz wszystkie kombinacje i zapisz ich sumę wag, a potem posortuj.

    Teraz już chyba mi się nie chce, ale rano może coś pokombinuję ;)

  • #10 14 Lip 2009 00:26
    terencjoo
    Poziom 12  

    aha no rzeczywiście można w dowolnej kolejności wyznaczyć kombinacje i potem sortować, ok dzięki. To już nie pomagaj mi z tym, bo mam algorytm wyznaczania kombinacji tylko nie wiedziałem jak go zmodyfikować żeby względem minimalizacji wag się te kombinacje generowały a tu wystarczy sortowanie wprowadzić i jest.:)

 Szukaj w ofercie
Zamknij 
Wyszukaj w ofercie 200 tys. produktów TME