Elektroda.pl
Elektroda.pl
X
Proszę, dodaj wyjątek www.elektroda.pl do Adblock.
Dzięki temu, że oglądasz reklamy, wspierasz portal i użytkowników.

Generowanie i-tej kombinacji bez powtórzeń [C++]

kadu 06 Sty 2010 19:38 13629 12
  • #1 06 Sty 2010 19:38
    kadu
    Poziom 10  

    Ktoś wiedziałby może (nawet w pseudokodzie byłoby pomocne) jak wygenerować od razu i-tą kombinację bez powtórzeń k-liczb ze zbioru n-elementowego? np.
    k=2; n=5
    i 5-ta kombinacja to:
    12
    13
    14
    15
    23 <- 5-ta kombinacja!

    Kod na generowanie kombinacji mam, ale generuje pokolei, a ja chciałbym wygenerować od razu np. 5-ta kombinację. Wiem, że można by wrzucić mój kod na kombinacje do jakiejś funkcji (tak jak na dole) i zliczać aż wystąpi liczba "i" (np. 5), ale w przypadku większych zbiorów ta metoda zajmuje dużo czasu. Potencjalny kod na kombinacje:

    Code:
    vector<int> zwroc_kombinacje(unsigned int numer_kombinacji, unsigned int n, unsigned int k)
    
    {
    int i=0,p=0,licznik=0;
    vector<int> kombinacje(k+1);
    for(i=1;i<=k;i++)
       kombinacje[i]=i;
    if(k!=n)
        p=k;
    else
        p=1;
    while((p>=1)&&(licznik!=numer_kombinacji))
    {
        if(kombinacje[k]==n)
            p--;
        else
            p=k;
        if(p>=1)
            for(i=k;i>=p;i--)
                kombinacje[i]=kombinacje[p]+i-p+1;
       licznik++;
    }
    kombinacje.erase(kombinacje.begin()+0);
    if(licznik==numer_kombinacji)
       return kombinacje;
    else
    {
       cout<<"Za duzy numerek"<<endl;
       kombinacje.clear();
       return kombinacje;
    }
    }

    Da radę jakimś innym szybszym sposobem?

    0 12
  • Pomocny post
    #2 06 Sty 2010 21:22
    BoskiDialer
    Poziom 34  

    Nie chce mi się pisać kodu, ale najłatwiej: bierzesz tablicę n elementów i wypełniasz ją wszystkimi liczbami. Reszta z dzielenia numer_kombinacji przez n daje numer elementu do wyciągnięcia w danym momencie. Wybrany element usuwa się poprzez nadpisanie go elementem n-1, numer_kombinacji zastępuje się częścią całkowitą z dzielenia przez n. Przy następnym przebiegu wybiera się jeden element z n-1, potem jeden z n-2 itd. W zależności od sposobu usuwania (nadpisywanie ostatnim, przesuwanie), kolejnością wypisywania (normalne, od końca) numer_kombinacji będzie w różny sposób się przekładał na właściwą kombinację, często będzie zupełnie losowy, jednak na pewno będzie jednoznaczny.

    Nie znając C++ (tylko C), opierając się o twój kod napisałem coś takiego:

    Code:
    vector<int> zwroc_kombinacje(unsigned int numer_kombinacji, unsigned int n, unsigned int k)
    
    {
       vector<int> kmb(n);
       vector<int> wynik(k);
       unsigned int i;

       for(i=0; i<n; i++)
          kmb[i] = i;
       for(i=0; i<k; i++, n--)
       {
          unsigned int q = numer_kombinacji % n;
          numer_kombinacji = numer_kombinacji / n;

          // wybranie elementu
          wynik[i] = kmb[q];
          
          // usunięcie elementu
          kmb[q] = kmb[n-1];
       }
       
       if(numer_kombinacji > 0)
          printf("za duzy numer kombinacji");

       return wynik;
    }


    -- edit:
    Wprowadziłem korektę ze względu na kolejność jakiej oczekujesz:
    Code:
    #include <stdio.h>
    
    #include <vector>

    using namespace std;

    vector<int> zwroc_kombinacje(unsigned int numer_kombinacji, unsigned int n, unsigned int k)
    {
       numer_kombinacji--;
       
       vector<int> kmb(n);
       vector<int> wynik(k);
       vector<int> reszty(k);
       unsigned int i;

       // wypełnienie liczbami
       for(i=0; i<n; i++)
          kmb[i] = i;
       // podzielenie numer_kombinacji
       for(i=0; i<k; i++)
       {
          unsigned int q = numer_kombinacji % ((n-k+1) + i);
          numer_kombinacji = numer_kombinacji / ((n-k+1) + i);




          reszty[(k-1)-i] = q;
       }
       if(numer_kombinacji > 0)
          printf("zly numer kombinacji");
          
       // wygenerowanie kombinacji dla normalnej kolejności
       for(i=0; i<k; i++)
       {
          unsigned int q = reszty[i];

          // wybranie elementu - obrobienie go
          wynik[i] = kmb[q] + 1;
          // usunięcie elementu przez przesuwanie
          unsigned int y;
          for(y=q; y<n-1-i; y++)
             kmb[y] = kmb[y+1];
       }

       return wynik;
    }

    int main(void)
    {
       int q;
       for(q=0; q<22; q++)
       {
          printf("%d: ", q);
          vector<int> res = zwroc_kombinacje(q, 5, 2);
          int i;
          for(i=0; i<2; i++)
             printf("%d ", res[i]);
          printf("\n");
       }
       return 0;

    }

    Wygenerowane kombinacje:
    Cytat:
    0: zly numer kombinacji4 5
    1: 1 2
    2: 1 3
    3: 1 4
    4: 1 5
    5: 2 1
    6: 2 3
    7: 2 4
    8: 2 5
    9: 3 1
    10: 3 2
    11: 3 4
    12: 3 5
    13: 4 1
    14: 4 2
    15: 4 3
    16: 4 5
    17: 5 1
    18: 5 2
    19: 5 3
    20: 5 4
    21: zly numer kombinacji1 2

    0
  • #4 06 Sty 2010 23:46
    kadu
    Poziom 10  

    Jak takie coś zwraca:

    Code:
    0: zly numer kombinacji4 5 
    
    1: 1 2
    2: 1 3
    3: 1 4
    4: 1 5
    5: 2 1
    6: 2 3
    7: 2 4
    8: 2 5
    9: 3 1
    10: 3 2
    11: 3 4
    12: 3 5
    13: 4 1
    14: 4 2
    15: 4 3
    16: 4 5
    17: 5 1
    18: 5 2
    19: 5 3
    20: 5 4
    21: zly numer kombinacji1 2

    to źle bo to ma być kombinacja bez powtórzeń w stylu
    12
    13
    14
    15
    23
    24
    25
    34
    35
    45
    Ale pokombinuję, bo pewnie w Twoim kodzie warunek gdzieś wystarczy dać if kombinacja[1]<kombinacja[0] to pomiń.

    0
  • #5 07 Sty 2010 00:37
    BoskiDialer
    Poziom 34  

    Z dużą dawką wyobraźni można pociąć pulę na pewne nierówne części: np pierwszy blok będzie zawierał wszystkie kombinacje mające liczbę "1" na początku - ile tych kombinacji jest można policzyć. Jeśli numer kombinacji jest w tym przedziale to wiadomo, że ma być jedynka. W przeciwnym przypadku pomniejsza się numer kombinacji, porzuca ową jedynkę i rozpatruje kolejne liczby. W ten sposób dopasuje się kolejne liczby. Jeśli jakaś liczba spasuje, to rekurencyjnie powstały blok dzielimy na mniejsze. Będzie to wyglądać jakoś tak (kod na szczęście nie wykorzystuje rekurencji):

    Code:
    #include <stdio.h>
    
    #include <vector>

    using namespace std;

    unsigned int newton_sym(int n, int k)
    {
       if(n < 0 || k < 0 || k > n)
          return 0;
       // wersja prowizoryczna
       static unsigned long int siltab[21] = {
          1ULL,1ULL,2ULL,6ULL,24ULL,120ULL,720ULL,5040ULL,40320ULL,362880ULL,3628800ULL,39916800ULL,479001600ULL,
          6227020800ULL,87178291200ULL,1307674368000ULL,20922789888000ULL,355687428096000ULL, 6402373705728000ULL,
          121645100408832000ULL, 2432902008176640000ULL
       };
       return siltab[n] / (siltab[k] * siltab[n-k]);
    }

    vector<int> zwroc_kombinacje(unsigned int numer_kombinacji, unsigned int n, unsigned int k)
    {
       numer_kombinacji--;
       vector<int> wynik(k);

       int i, p;
       for(i=0,p=0; p<k && i<n; i++)
       {
          // wstawienie liczby i na danej pozycji daje pewną ilość kombinacji - jeśli numer_kombinacji jest mniejszy od ich ilości to
          //  realizacja tej kombinacji, w przeciwnym przypadku pominięcie całego bloku kombinacji zawierających liczbę i
          //  n-i-1: ilość liczb możliwych do przydzielenia
          //  k-p-1: ilość liczb które trzeba przydzielić
          unsigned int ns = newton_sym(n-i-1, k-p-1);
          if(numer_kombinacji < ns)
          {
             // to jest ta kombinacja
             wynik[p++] = i + 1;
          } else
          {
             // to nie jest ta kombinacja - pominięcie wszystkich przypadków z liczbą i na pozycji p
             numer_kombinacji -= ns;
          }
       }
       return wynik;
    }

    int main(void)
    {
       int q;
       for(q=0; q<12; q++)
       {
          printf("%d: ", q);
          vector<int> res = zwroc_kombinacje(q, 5, 2);
          int i;
          for(i=0; i<2; i++)
             printf("%d ", res[i]);
          printf("\n");
       }
       return 0;
    }


    wynik:
    Cytat:
    0: 0 0
    1: 1 2
    2: 1 3
    3: 1 4
    4: 1 5
    5: 2 3
    6: 2 4
    7: 2 5
    8: 3 4
    9: 3 5
    10: 4 5
    11: 0 0

    0
  • #6 07 Sty 2010 02:41
    kadu
    Poziom 10  

    czyli jednak mój kod lepszy, bo nie da rady inaczej i-tej kombinacji BEZ POWTÓRZEŃ wygenerować, tylko musi ta pętla while i-liczbę razy się wygenerować zanim osiągnie się żądaną i-tą kombinację.

    0
  • #7 07 Sty 2010 13:27
    BoskiDialer
    Poziom 34  

    No to przecież mój ostatni kod generuje kombinacje już bez powtórzeń bez potrzeby generowania wszystkich poprzednich kombinacji: czas działania algorytmu to O(k) przy założeniu, że symbol newtona jest liczony w czasie stałym.

    Teraz mam więcej czasu aby napisać w jaki sposób mój kod działa:
    Jeśli należy wybrać rosnący podciąg k elementów pewnego zbioru n elementów, na pewno wiadomo, że takich kombinacji jest n po k, jednak we wszystkich kombinacjach rozpatrując pierwszy element wynikowy są dwie możliwości:
    - będzie "jedynka" - wtedy resztę należy uzupełnić wybierając k-1 elementów (mniej o wybraną już jedynkę) ze zbioru n-1 (jedynka już wybrana): łącznie (n-1 po k-1)
    - druga możliwość to bez tej jedynki, wtedy trzeba uzupełnić dobierając k elementów ze zbioru n-1 (jedynka już odrzucona): łącznie (n-1 po k)
    Widać że sumuje się do n po k z własności symbolu newtona. Jednak mając numer kombinacji można założyć, że pierwszych (n-1 po k-1) kombinacji zawiera tą jedynkę, wszystkie następne już nie: stąd jeśli numer kombinacji jest mniejszy od (n-1 po k-1), to wstawia się jedynkę a dalszą część ciągu uzupełnia się rekurencyjnie ale zaczynając od następnego znaku. Jeśli jednak numer kombinacji jest większy lub równy (przy numeracji od 1: większy), to odrzucamy jedynkę. Aby numer kombinacji nadawał się do dalszych testów trzeba go pomniejszyć o (n-1 po k-1) (tyle było przypadków z jedynką które pominięto), całość uzupełnia się rekurencyjnie pomijając jedynkę czyli zaczynając od następnego znaku.
    Mój kod realizuje ten algorytm w pętli, przy czym jeśli pod koniec p jest mniejsze od k, to numer kombinacji jest niepoprawny.

    Pomijając linie w których są same zera (niepoprawny numer kombinacji), to reszta zgadza się z tym czego oczekujesz.

    0
  • #8 09 Sty 2010 20:02
    kadu
    Poziom 10  

    Niestety idea oparta o silnię nie jest najlepszym sposobem na generowanie kombinacji. Związane jest to z tym, że liczy się tu iloczyny, wobec czego często te iloczyny mogą wynosi więcej niż 4 miliardy (unsigned int maksymalnie ma ok 4,4 mld) i rozwiązanie się sypie. Przykładowo w moim pierwszym kodzie można liczyć kombinacje dla k równego tysiąc i n równego z 10 tys.

    Poza tym co do generowania i-tej kombinacji to w moim kodzie można ustalić warunek, że numer kombinacji maksymalnie może wynosić 4 mld, wobec czego można poddawać pod analizę zbiory dochodzące do 10 tys. elementów, bo można łatwo warunek wprowadzić, by program złego wyniku nie podał, w Twoim kodzie pewnie ciężko byłoby wprowadzić ograniczenie że np. chcę 2 miliardową kombinację złożoną z 400 elementów ze zbioru tysiąc elementowego. Pewnie źle kod wyliczy taką kombinację, bo żeby ją wyliczyć to potrzebuje obliczyć silnię 1000 po 400, więc tu pośredni wynik źle obliczy, w konsekwencji będzie zła kombinacja. Więc odpada rozwiązanie oparte o liczenie silni.

    0
  • #9 09 Sty 2010 22:46
    BoskiDialer
    Poziom 34  

    Sposobów wybrania 400 elementów ze zbioru 1000 elementów jest powiedzmy około 4,96 * 10^290 - ani twój algorytm w ogóle, ani mój w postaci aktualnej nie będzie działać poprawnie, bo po prostu numery kombinacji nie będą się mieścić w zmiennej typu unsigned int. Moje rozwiązanie w aktualnej postaci jest dobre do bardzo małych liczb, jednak używając biblioteki liczb dowolnej długości można to przepisać tak, aby działało dla dowolnych rozmiarów danych - liczenie symbolu newtona można wtedy rozwiązać w dość przyziemnym czasie - około O(n) [zakładając, że dowolna operacja na liczbie dowolnej długości jest stała, co nie jest do końca prawdą]. Cały algorytm będzie wtedy działać w czasie O(n*k) - jest to zdecydowanie mniej, niż O((n po k)) gdzie n=1000 a k=400. Mój algorytm zakończy się w kilka chwil, kiedy twój po prostu będzie liczyć 2^965 kolejnych kombinacji co jest po prostu nierealne. Uwierz, liczenie silni jest tutaj najmniejszym problemem - wyliczając jeden symbol newtona można dokonać cięcia ogromnej części puli rozwiązań, kiedy Twój algorytm próbuje wyznaczyć wszystkie te rozwiązania tylko po to, aby wiedzieć ile ich było.

    Mój kod używając unsigned int działał by do trochę większych liczb gdybym w prowizorycznej wersji funkcji do liczenia symbolu newtona użył tablicy silni o elementach typu unsigned long long (o czym zapomniałem). Jakkolwiek mój kod prezentuje bardzo dobry algorytm, twoim zadaniem jest tylko połączyć go z biblioteką dużych liczb i będziesz miał to czego potrzebujesz. Argument że algorytm jest zły bo się wysypuje ze względu na ograniczenia rozmiaru zmiennych nie jest argumentem - błąd dotyczy konkretnej implementacji, jednak sam zarys algorytmu nie zawiera żadnego błędu.

    0
  • #10 10 Sty 2010 01:16
    kadu
    Poziom 10  

    Primo nikt nie bedzie łączył z biblioteką wielkich liczb, bo ten algorytm to część większego projektu, w którym zmienne większych rozmiarów nie są potrzebne.
    Secundo mój program działa nawet dla n=1000 i k=400 z tym, że nie da się uzyskać kombinacji o numerze większym niż 2 czy 4 miliardy, ale nie potrzebuje tego, bo maksymalny numer będzie ograniczony, tylko chodzi o to by móc uzyskac jakiś numer z kombinacji, której liczba możliwości przekracza 4 miliardy, czego Twój (tzn. nie Twój a algorytm combinadic) nie potrafi. Właśnie liczenie silni jest największym problemem. Nie da się zastosowac unsigned long long int, bo na komputerach starszych generacji (pentium I, II) się wysypie. Trzeba myśleć szeroko, a nie mieć klapki na oczach:) Po co komu taki algorytm co dla małego zakresu liczb działa.:) Temat można zamknąć:)

    0
  • #11 10 Sty 2010 01:33
    BoskiDialer
    Poziom 34  

    Czemu w pierwszym poście nie napisałeś ograniczeń na rozwiązanie jak n, k, architektura, ilość interesujących kombinacji (ileś początkowych)? Jaki jest sens generować kombinacje dla n=1000 i k=400 jeśli maksymalny numer będzie ograniczony? Jeśli maksymalny numer będzie ograniczony, to początkowych 390 lub coś koło tego liczb będzie praktycznie ustalonych i równych kolejno 1, 2, 3.. 390 - wtedy wystarczy wygenerować końcówkę przy n=610 k=10 lub jeszcze mniej. Symbol Newtona można zapisać w postaci dwóch pętli, pierwsza mnożyła by od k+1 do n, druga dzieliła przez 1 do n-k (lub jeśli n-k > k, to mnożenie od n-k+1 do n a dzielenie od 1 do k). Można też dzielenie wciągnąć do pierwszej pętli aby wykonywało się zaraz jak reszta z dzielenia wynosi 0 - aby wynik pośredni nie był za duży: samą silnię można tak rozbić w liczeniu SN, że wyniki pośrednie będą się mieścić w zakresie. Zastosowanie unsigned long long nie powinno stanowić problemu nawet na starszych komputerach.

    -- edit

    kadu napisał:
    Po co komu taki algorytm co dla małego zakresu liczb działa

    Słuszna uwaga, po co algorytm działający dla n=1000 i k=400, jeśli nie da się wygenerować wszystkich kombinacji.
    Swoją drogą testując mój kod używając gmp, wygenerowanie dla n=10000 k=400 kombinacji numer 1, 1000000^10, ^20, ^30... ^120 razem zajęło 23 sekundy.

    0
  • #12 03 Cze 2012 14:17
    kryst_12
    Poziom 1  

    A oto mój własny kod który umożliwia wygenerowanie od razu bez przechodzenia do kolejnej kombinacji na podstawie numeru :

    Kod: cpp
    Zaloguj się, aby zobaczyć kod


    A ten kod wygeneruje po kolei każda kombinację z tablicy poprzedniej - za to działa szybko

    Kod: cpp
    Zaloguj się, aby zobaczyć kod

    0
  • #13 04 Cze 2012 06:55
    Xitami
    Poziom 29  

    symbol Newtona wystarczy policzyć tylko jeden raz, wersja totolotkowa w PARI/GP:

    Code:
    f(c,z,b,n,k)={
    
            if(z<b,
                    print1(c" ");
                    if(n,
                            f(c+1, z  , b*k    \n, n-1, k-1 ));
            , \\ else
                    if(n,
                            f(c+1, z-b, b*(n-k)\n, n-1, k   ));
            );
    }
     
    f(1,                                     0, 48*47\2*46\3*45\4*44\5, 48, 5) \\ pierwsza
    f(1, random(49*48\2*47\3*46\4*45\5*44\6)+1, 48*47\2*46\3*45\4*44\5, 48, 5) \\ losowa
    f(1, 49*48\2*47\3*46\4*45\5*44\6-1,         48*47\2*46\3*45\4*44\5, 48, 5) \\ ostatnia


    Ale ładniej bez rekurencji
    Code:
    ko(n,k,z)={
    
            n--; k--;
            my(b=binomial(n,k),c=1);
            while(k+1>0,
                    if(z<b,
                            print1(c" "); c++;
                            if(n>0,               
                                    b=b*k/n
                            ,
                                    b=1
                            );
                            n--; k--;
                    ,
                            c++;
                            z=z-b;
                            b=b*(n-k)/n;         
                            n--;
                    );
            );
    }

    for(i=0,12,ko(10000,400,1000000^(i*10)-1))

    troszkę ponad sekundę

    0