с++ Перебор всех возможных подмножеств множества целых чисел

[Modlika17]

всем привет))))
пожалуйста, помогите решить задачку!!!!! очень нужно, срочно!!!
программа перебора всех возможных подмножеств множества целых чисел,т.е.
если с клавиатуры вводим, например 3, то на экране должно быть:
123
12
23
13
3
2
1
пустое множество не обязательно)))
заранее спасибо!!!!!!

[Sazary]

Не понял, по какому принципу строится подмножество (кстати, самого множества я что-то тоже не вижу).

Я правильно понял, что если ввести N, то нужно вывести все комбинации из N цифр, где каждая цифра может быть от 1 до N?
------------
В общем, предоставляйте свои наработки.

[Modlika17]

Да, если ввести N, то нужно вывести все комбинации, их будет 2^N. где каждая цифра может быть от 1 до N.

[Sazary]

Как вариант:

#include <iostream>
#include <conio.h>
#include <string.h>
using namespace std;

void fun(int N, int k, string tekS)
{
if(k==N)
 {
  cout<<tekS<<endl;
  return;
 }
for(int i=k+1;i<=N;i++)
  fun(N,i,tekS+(char)(i+48));

if(tekS=="")
 for(int i=N-1;i>=1;i--)
  cout<<i<<endl;
return;
}

int main()
{
int N;
cout<<"Enter N: ";
cin>>N;
fun(N,0,"");

getch();
return 0;
}

[Modlika17]

Спасибо, конечно)))))
Но эта прога не все подмножества выводит.
И объясните пожалуйста алгоритм этой проги, для чего там tekS????

[Sazary]

Спасибо, конечно)))))
Но эта прога не все подмножества выводит.

Пожалуйста. Если вы говорите, что выводит не все подмножества, то приведите пример правильной работы.
Для вашего предыдущего примера работает как надо.

для чего там tekS????

При каждом рекурсивном вызове функции формируется строка (подмножество), которая выводится в конце.

Кажется, там все и так ясно:

void fun(int N, int k, string tekS)
{
if(k==N)  // если сформировали подмножество...
 {
  cout<<tekS<<endl;  // выводим его
  return;               // и выходим
 }
for(int i=k+1;i<=N;i++)   
  fun(N,i,tekS+(char)(i+48)); // подбираем следующую цифру для подмножества

if(tekS=="")    // когда все вывели, нужно еще вывести оставшиеся варианты
 for(int i=N-1;i>=1;i--)
  cout<<i<<endl;
return;
}

[Modlika17]

Sazary, вы то сами прогу проверяли?????
Например, если с клавиатуры ввели 3, то ваша прога не выводит подмножество {1,2}.

[Sazary]

Я всегда проверяю свои программы.
Но да, не заметил, извиняюсь.
Тогда вот так:

#include <iostream>
#include <conio.h>
#include <string.h>
using namespace std;

void fun(int N, int m, int tek, int k, string tekS)
{
 if(tek>=m)
  {
   cout<<tekS<<endl;
   return;
  }
 for(int i=k+1; i<=N; i++)
  fun(N,m,tek+1,i,tekS+(char)(i+48));

}

int main()
{
int N;
cout<<"Enter N: ";
cin>>N;
for(int i=1;i<=N;i++)
 fun(N,i,0,0,"");

getch();
return 0;
}

Поясняю аргументы функции:

void fun(int N, int m, int tek, int k, string tekS)

N - собственно, N
m - длина подмножества. Изменяется от 1 до N
tek - номер текущего элемента подмножества. Изменяется от 1 до m
k - значение предыдущего элемента
tekS - строка, в которую пишутся элементы подмножества

[Modlika17]

Sazary, спасибо ОГРОМНОЕ!!!
А вы можете мне объяснить почему у меня не работает библиотека conio.h, выдает ошибку в этом месте, и там где getch()-тоже ошибку выдает . Для чего вообще нужна эта библиотека??????

[Sazary]

Modlika17, А какую ошибку-то?

В данной программе conio требуется только для getch(), который в данном случае нужен только для задержки перед выходом.

Можете заменить его на

cin.get()

Так даже лучше будет - меньше лишнего.