Zadanie na wypisywanie wszystkich podzbiorów wg algorytmu

Question

Mam problem z napisaniem programu na wypisywanie wszystkich podzbiorów danego zbioru

algorytm to Algorytm wypisujący ¸ wszystkie podzbiory zbioru {1, . . . , n}: • Pierwszy podzbiór: ∅. • by uzyska´c następny po A podzbiór: Wskazujemy na najwięszy element nie należący ¸ do A, czyli a = max{i ∈/ A} Jeżeli ˙ takiego a nie ma, to koniec algorytmu, zbiór A jest ostatnim podzbiorem. W przeciwnym przypadku dodajemy a do A i usuwamy z A wszystkie elementy większe od a

Mam tylko tyle
 

int nalezy(int tab[], int size, int elem)
{
    int i = 0;
    int x = 0;

    for(i; i < size; i++)
    {
        if(elem == tab[i])
        {
            x++;
            break; }}

 return x;
}

i w mainie ma być pętla

if(należy) dodaj element; usuń element; wypisz podzbór;

Comments

Podaj przykładowe wejście i wyście, oraz polecenie możesz poprawić by było jakoś sformatowane, bo osobiście go nie rozumiem.

Answer 1

W celu wyświetlenia wszystkich podzbiorów danego zbioru, możesz zastosować algorytm licznika bitowego.

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

void listAllSubsets( const vector<int>& set )
{
    cout << "subset 1 " << " = { }" << endl;
	for( int i {1} ; i < pow(2,set.size()) ; ++i )
	{
	    cout << "subset "<< i+1 << " = { ";
		for( int j {0} ; j<set.size() ; ++j )
		{
			if( i&(1<<j) )
			{
			    cout << set[j];
			    if( i>>(j+1) ) cout << " , ";
			}
		}
		cout << " }" << endl;
	}
}

int main()
{
    listAllSubsets( {1,2,3,4} );
    return 0;
}

 

Comments

https://en.cppreference.com/w/cpp/algorithm/includes