Podmnožiny v C++

Popis

V závěrečné fázi Berlekampova-Henselova algoritmu pro faktorizaci celočíselných polynomů je třeba nakombinovat zdvižené faktory do skutečných dělitelů polynomu v Z[x]. Jestliže implementujete Zassenhausovu metodu kombinace faktorů v C++ bude se vám hodit funkce next_subset, pomocí níž můžete snadno projít všechny podmnožiny dané velikosti. Tato funkce funguje na stejném principu jako next_permutation v STL; najdete ji v souboru subsets.h. Zároveň zde najdete funkci ith_subset, která slouží k efektivnímu výpočtu lexikograficky i-té k-prvkové podmnožiny množiny {0, 1, …, n − 1}. Pokud potřebujete pracovat s hodně velkou hodnotou i, je k dispozici také verze mpz_ith_subset, která spolupracuje s knihovnou GNU MP.

Funkce `next_subset`

bool next_subset(BidirectionalIterator first, BidirectionalIterator last, Size n)

Předpokladem je, že interval [first, last) obsahuje vzestupně setříděnou k-prvkovou podmnožinu prvků z {0, 1, …, n − 1} bez opakování, kde k = last − first. Interval [first, last) se přepíše na lexikograficky nejbližší následující k-prvkovou podmnožinu množiny {0, 1, …, n − 1} a funkce vrátí true. Jestlize však taková podmnožina neexistuje, funkce vrátí false.

Složitost: Nejvýše k porovnání a nejvýše k přiřazení.

Funkce `ith_subset`

bool ith_subset(OutputIterator first, Size n, Size k, T i)

bool mpz_ith_subset(OutputIterator first, unsigned long int n, unsigned long int k, mpz_t i)

Funkce zapíše do intervalu [first, first + k) lexikograficky i-tou (počítáno od 0) vzestupně setříděnou k-prvkovou podmnožinu množiny {0, 1, …, n − 1} a vrátí true. Jestliže taková podmnožina neexistuje, funkce neudělá nic a vrátí false.

Složitost: Nejvýše n + k operací násobení a nejvýše n + k operací dělení.

Funkce `bin_coef`

T bin_coef(T n, T k)

void mpz_bin_coef(mpz_t result, unsigned long int n, unsigned long int k)

Funkce spočítá kombinační číslo n nad k.

Složitost: Nejvýše min(k, n − k) operací násobení a nejvýše min(k, n − k) operací dělení.

Ke stažení

subsets.h

Příklad použití

Tento program vypíše všechny k-prvkové podmnožiny množiny {0, 1, …, n − 1}. Podmnožina je reprezentovaná jako vzestupně setříděný vector<int>.

#include <iostream>

#include <vector>

#include "subsets.h"



using namespace std;



int main(int argc, char * argv[]){

    int n = 5;

    int k = 3;



    // Vektor subset inicializujeme na lexikograficky minimalni k-prvkovou

    // podmnozinu mnoziny {0, 1, ..., n-1}, tj. v = {0, 1, ..., k-1}.

    vector<int> subset(k);

    for(int i = 0; i < k; ++i)

        subset[i] = i;



    do{

        for(size_t i = 0; i < subset.size(); ++i)

            cout << subset[i] << " ";

        cout << endl;

    } while(next_subset(subset.begin(), subset.end(), n));



    return 0;

}

Výstup programu: