Генерация всех возможных подмножеств на Bornald C++ 3. 1

[Lei fang]

Здравствуйте!!!

Люди! Помогите мне, пожалуйста! Я учусь на программиста и мне дали задание "Сгенерировать все возможные подмножества данного n-элементного множества. Результат записать в файл." Отправить данные в файл не сложно, а вот как сгенерировать эти подмножества я что-то не понимаю. Думаю, что должен быть один массив, который нужно просматривать в цикле и если такой комбинации элементов еще не было, то записывать ее в файл. Однако я не представляю себе как должен выглядеть такой алгоритм более подробно. В этом вся и проблема. Кто-нибудь помогите!

[Eugie]

См. forum/viewtopic.php?t=721

[Lei fang]

Спасибо. Чесно говоря я тоже не совсем понимаю изложенный там алгоритм.
Во первых: Что такое сигнатура и зачем она там нужна?
Если есть множество из 4 элементов (1, 2, 3, 4), то подмножествами будут (если, конечно, перестановки не считаются подмножествами)
(0)
(1)
(2)
(3)
(4)
(1, 2)
(1, 3)
(1, 4)
(2, 3)
(2, 4)
(3, 4)
Зачем нужны 0 и 1?

>>объявляешь переменную типа unsigned long и в последовательно ее инкрементируешь от 0 до 2^N-1.
Что значит инкрементируешь? И что такое 2^N-1?

Помогите!!! Надо сдать до сессии...

[Lei fang]

Совсем забыл про
(1, 2, 3)
(2, 3, 4)

[WinMain]

Здесь используется прямой аналог с двоичной системой исчисления, т.е. из массива, состоящего только из нулей и единиц, и имеющего N элементов, можно сформировать количество разных комбинаций, равное 2 в степени N (сокращённо 2^N). Далее понятие сигнатуры можно определить как: 1- принадлежит подмножеству, 0- не принадлежит. Так из множества, в котором всего 10 элементов, можно составить 1024 разных варианта подмножеств, включая пустое множество и полное исходное множество.

[Lei fang]

Хорошо. Спасибо. Уже хоть что-то стало понятно (хотя и не достаточно).

Пожалуйста, помогите составить алгоритм.

Что именно делать дальше?

1. Создаю динамический массив из n элементов (пусть будет 4)
2. Заполняю массив (p={1, 2, 3, 4}
3. ???
.
.
.

Извините за непонятливость...

[Eugie]

Проще самому написать

Код: Выделить всё

#include "stdafx.h"
#include <iostream>
#include <cmath>

using namespace std;

void main()
{
    int p[] = {1, 2, 3, 4};
    int n = sizeof(p)/sizeof(int);
    int m = (int)pow(2,n);

    for (int i=0; i<m; ++i)
    {
      bool sep=false;
      cout << "{";
      for (int d=0; d<n; ++d)
      {
        if ((1<<d)&i)
        {
            cout << (sep ? ", " : "") << p[d];
            sep = true;
        }
      }
      cout << "}\n";
    }
}

[Lei fang]

Спасибо за Вашу доброту, Eugie.

Хм... Это... А Вы написали эту программу точно на Bornald C++ 3. 1?

Просто, я попытался ее компилировать, а там 10 ошибок! Эти 3 библиотеки не открываются (Хотя если написать #include <iostream.h>, то она откроется, а с другими такое не выходит).

Да еще компилятор не знает большенства операторов. Я, конечно, слышал, что тот bc_31, на котором мы пишем программы, покотцан, но чтоб так...

В общем, если я правильно понял, как тут вставлять картинки, то скриншот здесь:


и, если нужен локальный путь, то:

[img]http://D:\Documents%20and%20Settings\User\Мои%20документы\bc%203.%201.%20jpg[/img]

Всем спасибо за помощь!!!

Мне уже помогли написать эту программу с помощью рекурсии.

Вот исходник, если кому-нибудь он понадобится, то он к Вашим услугам:

Код: Выделить всё

#include<conio.h>
#include<stdio.h>
#include<stdlib.h>

int n, m, *p, *q;
FILE *fp;

void Print()
{
	for(int i=0; i<m; i++){fprintf(fp, "%i ", q[p[i]]);}
	fprintf(fp, "\n");
}

int generator(int number, int nomer)
{
	if(number>n)return 0;

	for (int i=number; i<=n; i++)
	{
		p[nomer]=i;
		if(nomer==m){Print(); return 0;}
		p[nomer]=generator(i+1, nomer+1);
	}
	return 0;
}


main()
{
	clrscr();

	printf("‚ўҐ¤ЁвҐ Є®«ЁзҐбвў® н«Ґ¬Ґ­в®ў ў ¬­®¦Ґб⢥	");
	scanf("%d", &n);

	p=(int *)malloc(n*sizeof(int));
	q=(int *)malloc(n*sizeof(int));

	fp=fopen("C:\\Lang\\File.txt", "w");

	for(int i=0; i<n; i++)
	{
		printf("‚ўҐ¤ЁвҐ н«Ґ¬Ґ­в ­®¬Ґа %d	 ", i+1);
		scanf("%d", q+i);
	}

	for(i=1; i<=n; i++){m=i; generator(0, 0);}

	fclose(fp);
	getch();
	return 0;
}

Всем спасибо за помощь!!!

[Lei fang]

Как-то странно тут картинки вставляются...

[Eugie]

Lei fang, то был VC++ 6.0