Pokaż wyniki od 1 do 4 z 4
  1. #1
    Obserwator
    Dołączył
    January 07
    Postów
    493
    Siła Reputacji
    0


    Twoja ocena: Yes No

    Wariacja bez powtórzeń

    Tym razem ja proszę o pomoc
    Niestety nie mam przez przynajmniej tydzień dostępu do notatek ze studiów, a google też zbyt pomocne nie jest w tym przypadku. Szukam algorytmu (C++/PASCAL/pseudo-kod) na generowanie zbiorów wariacji bez powtórzeń. Żeby uniknąć nieporozumień nazewnictwa, śpieszę z przykładem:
    dla zbioru {a,b,c} potrzebowałbym wyniki {a},{b},{c},{ab},{ac},{ba},{bc},{ca},{cb},{abc},{a cb}.. itd...
    Czyli dowolny rozmiar zbioru, elementy niepowtarzalne..

    Znalazłem na razie algorytm na kombinację, ale tam kolejność nie ma znaczenia - generuje tylko {ab}, a {ba} już - matematycznie rzecz biorąc - nie istnieje.
    W tej chwili desperacko będę próbował *permutować* (czyli każde możliwe ułożenie) po wszystkich *kombinacjach* i --prawdopodobnie-- da to wariację, ale program JUŻ jest wystarczająco zamieszany i szczerze chyba zaczynam tracić nad nim kontrolę :/

    Więc jeśli ktoś ma gdzieś z notatek, albo namiar na dobry URL z algorytmem, to byłbym niezmiernie wdzięczny.

  2. #2
    Obserwator
    Dołączył
    February 08
    Postów
    3
    Siła Reputacji
    0


    Twoja ocena: Yes No

    Najprościej chyba rekurencyjnie, praktycznie z definicji:
    Kod:
    FUNKCJA przyjmujaca parametry ZBIOR, WYNIK
    dla kazdego z elementow ELEMENT ze zbioru ZBIOR {
        tworzymy nowy zbior NOWY ZBIOR bez elementu ELEMENT: NOWY ZBIOR = ZBIOR - ELEMENT
        dodajemy ten element do tymczasowego wyniku: NOWY WYNIK = WYNIK + ELEMENT
        dodajemy NOWY WYNIK do rozwiazan
        wywolujemy ponownie funkcję dla nowego zmniejszonego zbioru i czastkowego wyniku: FUNKCJA (NOWY ZBIOR, NOWY WYNIK)
    }
    Funkcję wywołuje się podając jako argumenty zadany zbiór i pusty wynik.

    Przykładowa implementacja w C99 dla ciągów tekstowych:

    Kod:
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
    void wbp(char *zbior, char * wynik) {
    int i, n = strlen(zbior);
    char nowyzbior[n], nowywynik[strlen(wynik)+2];
    //dla kazdego z elementow zbioru
      for (i = 0; i < n; i++) {
        //tworzymy nowy zbior bez elementu
        strncpy(nowyzbior, zbior, i)[i] = 0;
        strcat(nowyzbior, &zbior[i+1]);
        //dodajemy usuniety element do tymczasowego wyniku
        strncat(strcpy(nowywynik, wynik), &zbior[i], 1);
        //zwracamy tymczasowy wynik jako jedno z rozwiazan
        printf("%s
    ", nowywynik);
        //wywolujemy ponownie funkcje dla zmniejszonego zbioru i czastkowego wyniku
        wbp(nowyzbior, nowywynik);
      }
    }
    
    int main () {
    char *napis = "abcd";
      wbp(napis, "");
      return 0;
    }

  3. #3
    Obserwator
    Dołączył
    August 08
    Postów
    20
    Siła Reputacji
    0


    Twoja ocena: Yes No

    Tu jest wzór:
    http://pl.wikipedia.org/wiki/Wariacj...C3%B3rze%C5%84

    I Twój post świadczy, że w ogóle nie rozumiesz o czym piszesz, albo nie potrafisz się wysławiać.
    Przykład polakko ma się nijak do problemu. Ale biorąc pod uwagę Twój przykład, nie dziwię się mu, że napisał takie rozwiązanie.

    W wariancji bez powt. potrzebny są 2 (słownie DWIE!) dane które określają ilość wszystkich elementów (n) i wielkość zbioru tych elementów (k).
    I dopiero znając te 2 dane jesteśmy w stanie utworzyć kombinację tych elementów.

    Jest to bardzo prosty algorytm...
    Tu są rozwiązania (zaznaczam, że nie moje :P )
    http://forum.idg.pl/lofiversion/index.php/t85902.html

  4. #4
    Obserwator
    Dołączył
    February 08
    Postów
    3
    Siła Reputacji
    0


    Twoja ocena: Yes No

    No to przecież rrybakowi chodziło dokładnie o wariacje bez powtórzeń, tyle że o wszystkie - czyli dla wszystkich k: od 1 do N (dla zbioru N elementowego). Mój algorytm generuje dokładnie to, chociaż nie po kolei - wyniki dla różnych k są przemieszane, ale w sumie rozwiązania są wszystkie. Można ten algorytm łatwo przerobić na przyjmowanie k do funkcji jako parametr - wystarczy wtedy uznawać tylko te wyniki, których długość jest równa k (i można od razu powracać wtedy z rekurencyjnie wywołanej funkcji żeby nie mnożyć bytów)...

    Kod:
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    
    void wbp(char *zbior, char * wynik, int j) {
    int i, n = strlen(zbior);
    char nowyzbior[n], nowywynik[strlen(wynik)+2];
    //dla kazdego z elementow zbioru
    for (i = 0; i < n; i++) {
      //tworzymy nowy zbior bez elementu
      strncpy(nowyzbior, zbior, i)[i] = 0;
      strcat(nowyzbior, &zbior[i+1]);
      //dodajemy usuniety element do tymczasowego wyniku
      strncat(strcpy(nowywynik, wynik), &zbior[i], 1);
      //jesli odpowiednia dlugosc wyniku to zwracamy jako jedno z rozwiazan
      if (strlen(nowywynik) == j)
        printf("%s\n", nowywynik);
      else
      //wywolujemy ponownie funkcje dla zmniejszonego zbioru i czastkowego wyniku
      wbp(nowyzbior, nowywynik, j);
    }
    }
    
    int main () {
    char *napis = "abcd";
    wbp(napis, "", 1);
    printf("\n");
    wbp(napis, "", 2);
    printf("\n");
    wbp(napis, "", 3);
    printf("\n");
    wbp(napis, "", 4);
    return 0;
    }

Informacje o temacie

Users Browsing this Thread

Aktualnie 1 użytkownik(ów) przegląda ten temat. (0 zarejestrowany(ch) oraz 1 gości)

Zakładki

Zakładki

Uprawnienia

  • Nie możesz zakładać nowych tematów
  • Nie możesz pisać wiadomości
  • Nie możesz dodawać załączników
  • Nie możesz edytować swoich postów
  •  

Jak czytać DI?

Powered by  
ATMAN EcoSerwer