Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > [c++] сгенерировать подмножества

Автор: 14SatanA88 19.8.2011, 21:10

Доброго времени суток, уважаемые форумчане.

Задача:Сгенерировать все k-элементные подмножества множества A из N чисел, A={1, 2, ..., N}. Пример: N=3, k=2, подмножества {1,2}, {1,3}, {2,3}

Решение:
Воспользуемся следующим алгоритмом генерации сочетаний по k элементов из множества A: В массиве B будут находиться индексы используемых на данном шаге элементов из A (общее их число k). В качестве начальной конфигурацией возьмем следующую: B[j]=j, j=1,...,k. Ищем B[j] с максимальным индексом j такое, что B[j]<n+j-k, увеличиваем это B[j] на 1, а для всех m>j полагаем B[m]=B[m-1]+1 (B[j] растут с ростом j, и мы ищем и увеличиваем на 1 такое B[j] с максимальным номером j, чтобы при заполнении возрастающими значениями элементов массива B[m], m>j, последний элемент B[k] не превосходил бы n). Если такого B[j] не существует, то генерация сочетаний для данного k закончена.

Нужно закодить в плюсах

Я пару раз пробовал, у меня какая-то ересь получается типа этого:

Код


int main()
{
    int i,n,k;
   int b[99];

   cout<<"Enter n (length of array): "; cin>>n;
   cout<<"Enter k (length of subarray): "; cin>>k;

   for (int i = 0; i < k; i++) b[i] = i+1;

   for (int m = 0; m < pow(2,n); m++)
   {
    i = n;
    while (!(b[i] < n-k+i)) i--;
    b[i]++;
    for (int j = i+1; j <= n; j++) b[j] = b[j-1]++;
    for (int j = 0; j < k; j++) cout<<b[j];
    cout<<endl;
   }

    getch();
   return 0;
}

Автор: volatile 20.8.2011, 01:36

Цитата(14SatanA88 @ 19.8.2011, 21:10

)

Нужно закодить в плюсах

Код


#include <iostream>
#include <vector>

class combination
{
public:
   combination ( int n, int k ) : N ( n ), K ( k ), arr ( k ) 
   {
      for ( int i = 0; i < K; ++ i )
         arr [ i ] = i;
   }
   bool next ()
   {
      int i = K - 1;
      while ( arr [ i ] + K - i >= N )
         if ( -- i < 0 ) return 0;
      int num = arr [ i ];
      for ( ; i < K; ++ i )
          arr [ i ] = ++ num;
      return 1;
   }
   friend std::ostream& operator << ( std::ostream & out, const combination & comb );
private:
   const int N;
   const int K;
   std::vector <int> arr;
};

std::ostream & operator << ( std::ostream & out, const combination & comb )
{
   for ( int i = 0; i < comb.K; ++ i )
      out << comb.arr [ i ] + 1 << " "; // здесь +1 для того чтобы счет начинался с 1. Если нужно с нуля, то +1 убрать.
   out << std::endl;
   return out;
}

void print_all_combination ( int n, int k )
{
    std::cout << "Combinations " << k << " of " << n << std::endl;
    combination comb ( n, k );
    do
       std::cout << comb;
    while ( comb.next () );
}

Пример использования:
http://liveworkspace.org/code/307bab6bcc914f2ed26c54b499636e53

Автор: 14SatanA88 20.8.2011, 12:09

volatile, спасибо, конечно, а без классов никак?
если можно попроще, буду рад.

Автор: 14SatanA88 20.8.2011, 19:05

все, что я пока смог написать

Код


#include <iostream>
#include <conio>
#include <math>

int main()
{
    int i,n,k,x = 0;
   int b[99];

   cout<<"Enter n (length of array): "; cin>>n;
   cout<<"Enter k (length of subarray): "; cin>>k;

   for (int i = 0; i < k; i++) b[i] = i+1;
   for (int j = 0; j < k; j++) cout<<b[j];
   cout<<endl;

    for (int i = k-1; i >= 0; i--)
   {
       do
    {
          b[i]++;
         for (int j = 0; j < k; j++) cout<<b[j];
            cout<<endl;
    } while (b[i] != n-x);
      x++;
   }

    getch();
   return 0;
}

но этот код дает не весь результат, а лишь часть.

помогите довести его до полной дееспособности.

Автор: 14SatanA88 20.8.2011, 20:07

все, вопрос решен
получилось с использованием рекурсивной функции

если кому интересен код

Код


#include <iostream>
#include <conio>

int b[99];

void f(int n, int k, int i)
{
    if (i == k)
   {
    for (int j = 0; j < k; j++) cout<<b[j];
      cout<<endl;
   }
   else
   {
    for (b[i] = (i > 0 ? b[i-1] + 1 : 1); b[i] <= n; b[i]++)
      f(n,k,i+1);
   }
}

int main()
{
    int i,n,k;

   cout<<"Enter n (length of array): "; cin>>n;
   cout<<"Enter k (length of subarray): "; cin>>k;

   f(n,k,0);

    getch();
   return 0;
}

Автор: wester 21.8.2011, 17:33

14SatanA88,

Цитата

а без классов никак?

зачем тогда писать на плюсах ? легко и просто можно переписать на Си

Автор: 14SatanA88 23.8.2011, 17:26

Цитата(wester @ 21.8.2011, 17:33

)

зачем тогда писать на плюсах ? легко и просто можно переписать на Си

я немного путаю )