Wariacja bez powtórzeń

[RRybak]

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.

[polakko]

Najprościej chyba rekurencyjnie, praktycznie z definicji:

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:

#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;
}

[szopa123]

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

[polakko]

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)...

#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;
}