Генерирование подмножеств с заданным количеством элементов - Дискретная математика

[Blackman9999]

Задача: Создать программу для генерирования всех подмножеств с заданным количеством элементов. В контрольной работе привести листинг программы и все сгенерированные подмножества. Количество элементов подмножеств и универсальную множество выбрать согласно варианту.
Вариант №3. K = 4. U = {a, b, k, d, h, f}.

Код выводит 4 элемента множества и повторяет их.Что нужно добавить,чтобы разные буквы выводились с нового ряда,а не повторялось все снова.

#include "stdafx.h"
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
using namespace std;
int main()
{
    setlocale(LC_ALL, "RUS");
    char u[] = { 'a' , 'б', 'в', 'д', 'e', 'f' }; 
    int a = 4, b;
    for (int i = 0; i<a; i++)
        b = powf(2, a);
    for (int i = 0; i<b; i++)
    {
        cout << "{";
        for (int j = 0; j<a; j++)
            
                cout << u[j] << " ";
        cout << "}" << endl;
    }
 
    system("pause");
    return 0;
}

[Blackman9999]

Нашел нужный код,но символы прикрутить никак не могу.

#include <iostream>
using namespace std;
bool NextSet(int *a, int n, int m)
{
  int j = m - 1;
  while (a[j] == n && j >= 0) j--;
  if (j < 0) return false;
  if (a[j] >= n)
    j--;
  a[j]++;
  if (j == m - 1) return true;
  for (int k = j + 1; k < m; k++)
    a[k] = a[j];
  return true;
}
void Print(int *a, int n) 
{
  static int num = 1;
  cout.width(3);
  cout << num++ << ": ";
  for (int i = 0; i < n; i++)
    cout << a[i] << " ";
  cout << endl;
}
int main() 
{
  int n, m, *a;
  cout << "N = ";
  cin >> n;
  cout << "M = ";
  cin >> m;
  int h = n > m ? n : m; // размер массива а выбирается как max(n,m)
  a = new int[h];
  for (int i = 0; i < h; i++)
    a[i] = 1;
  Print(a, m);
  while (NextSet(a, n, m))
    Print(a, m);
  cin.get(); cin.get();
  return 0;
}

[Blackman9999]

ау??

[Serge_Bliznykov]

не уверен, что результат будет тот, что Вам нужно, но формально, ответ на вопрос

Сообщение от Blackman9999

символы прикрутить никак не могу.

вот, "прикрутил" к вашему коду ваши символы:

#include <iostream>
using namespace std;

bool NextSet(int *a, int n, int m)
{
  int j = m - 1;
  while (a[j] == n && j >= 0) j--;
  if (j < 0) return false;
  if (a[j] >= n)
    j--;
  a[j]++;
  if (j == m - 1) return true;
  for (int k = j + 1; k < m; k++)
    a[k] = a[j];
  return true;
}
void Print(int *a, int n, char *u) 
{
  static int num = 1;
  cout.width(3);
  cout << num++ << ": ";
  for (int i = 0; i < n; i++)
    cout << u[a[i]-1] << " ";
  cout << endl;
}
int main() 
{
  char u[] = {'a', 'b', 'k', 'd', 'h', 'f'};
  int n=6, m=4, *a;
  a = new int[n];
  for (int i = 0; i < n; i++)
    a[i] = 1;
  Print(a, m, u);
  while (NextSet(a, n, m))
    Print(a, m, u);
  cin.get(); cin.get();
  return 0;
}

проверить - https://ideone.com/bk3FAv


p.s. кстати, не знаю, что Вам нужно получить в вашем задании,
но это классический алгоритм Нарайаны для получения всевозможных перестановок в лексикографическом порядке.

[Blackman9999]

Спасибо Вам Великий.Особенно,за обозначение алгоритма.А то заданий еще таких хватает,а названий,способов мало знаю.Вот по немного учусь,та и на заочном не сильно нагружают,но и правда,даже список рекоменд.лит-ры не дали.

[Blackman9999]

Тот код отличный,но почитав,я понял,что надо без повторений элементов(как например все А А А А).Вот без повторений,мб кому-то пригодится:

#include "stdafx.h"
#include <iostream>
using namespace std;
void swap(int *a, int i, int j)
{
	int s = a[i];
	a[i] = a[j];
	a[j] = s;
}
bool NextSet(int *a, int n, int m)
{
	int j;
	do  // повторяем пока не будет найдено следующее размещение
	{
		j = n - 1;
		while (j != -1 && a[j] >= a[j + 1]) j--;
		if (j == -1)
			return false; // больше размещений нет
		int k = n - 1;
		while (a[j] >= a[k]) k--;
		swap(a, j, k);
		int l = j + 1, r = n - 1; // сортируем оставшуюся часть последовательности
		while (l < r)
			swap(a, l++, r--);
	} while (j > m - 1);
	return true;
}
void Print(int *a, int n, char *u)  // вывод размещения
{
	static int num = 1; // номер размещения
	cout.width(3); // ширина поля вывода номера размещения
	cout << num++ << ":  ";
	for (int i = 0; i < n; i++)
		cout << u[a[i]-1] << " ";
	cout << endl;
}
int main()
{
	int n=6, m=4, *a;
	char u[] = { 'a', 'b', 'k', 'd', 'h', 'f' };
	a = new int[n];
	for (int i = 0; i < n; i++)
		a[i] = i + 1;
	Print(a, m,u);
	while (NextSet(a, n, m))
		Print(a, m,u);
	cin.get(); cin.get();
	return 0;
}