Форум программистов, компьютерный форум CyberForum.ru

Сгенерировать все k -элементные подмножества из N - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.92
Rosman
 Аватар для Rosman
0 / 0 / 0
Регистрация: 18.12.2012
Сообщений: 4
26.05.2013, 15:53     Сгенерировать все k -элементные подмножества из N #1
Дело все в том, что мне надо написать программу, которой на вход давался файл с N целых чисел через пробел, пользователь дает на ввод число k
надо сгенерировать все k -элементные подмножества из N и вывести их на экран

у меня проблема с вводом-выводом. хотелось чтобы все числа из файла были в одном массиве и узнать его длину(т.е N)
сама функция в виде алгоритма есть, но пока в коде не реализована.

Алгоритм 1) берем 1 элем, потом след(т.е 2) и т.д. до k это первое подмножество потом вместо k будем брать k+1 и до N
2) вместо k-1 берем k т.е. изменяем предпоследний элемент и снова последний прогоняем до N и т.д.


Заранее спасибо всем откликнувшимся.

Добавлено через 8 минут
Что - то наваял,...
переменыые в функциях и коде пока не совмещены, так что тут немного каламбур...

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <fstream>
#include <conio.h>
#include <string>
#include <cmath>
using namespace std;
 
 
int fact(int k){
int r=1;
while(k!=1)
 r *= k--;
return r;
}
 
/*void func(int N, int k)
{
 
 
 
}*/
 
int main()
{int N,k,v;
 char NOW[50];
   cout<<"Enter k: ";
  cin>>k;
   ifstream fin ("input.txt");
   FILE *f;
   f = fopen("input.txt","r");
   int c,n=0;
  
    while (!feof(f))
      {;
          c=fgetc(f);
         n++;
       }
   cout<< n<<endl;
   int *A= new int[n] ;
     
  for (int i =1; i <= n; i++ )
  {fin >> A[i];
  }
 
 
 for (int i =1; i <= n; i++ ) 
  cout<<A[i]<<endl;
 
 /* v = fact(N)/(fact(k)*fact(N-k));
  int *B = new int[k];
  for (int i = 1; i <= N; i++)
   { 
     A[i]=i;
   }
 
 
 
  cout << v;*/
   
  getch();
  return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.05.2013, 15:53     Сгенерировать все k -элементные подмножества из N
Посмотрите здесь:

C++ Напечатать все подмножества множества {1...k}
Сгенерировать все сочетания длины k из чисел 0,1,2,...n-1 C++
C++ на плоскости задано множество точек. Найти все подмножества точек, лежащих на одной прямой.
Как можно получить все подмножества множества? C++
C++ С числовой множества A мощности n выбрать все подмножества, сумма элементов каждого из которых лежит в пределах от a до b
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Olivеr
 Аватар для Olivеr
411 / 407 / 13
Регистрация: 06.10.2011
Сообщений: 830
26.05.2013, 16:17     Сгенерировать все k -элементные подмножества из N #2
Цитата Сообщение от Rosman Посмотреть сообщение
надо сгенерировать все k -элементные подмножества из N и вывести их на экран
сочетания без повторений?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <iostream>
#include <fstream>
#include <vector>
 
using namespace std;
 
//сочетания без повторений. взял с другой моей программы. переделывать под этот случай не стал потому, что лень.
//что бы выдавало индексы надо передавать n - 1
bool increase(vector<size_t> &vec, const size_t n)
{
    for (int i = vec.size() - 1; i >= 0; i--)
        if ( vec[i] + 1 <= n ) {
            if ( i != vec.size() - 1 && vec[i + 1] == vec[i] + 1 )
                continue;
            ++vec[i];
 
            for (int j = i + 1; j < vec.size(); j++)
                vec[j] = vec[j - 1] + 1;
            return true;
        }
    return false;
}
 
void to_file(ofstream &os, const vector<int> &data, const vector<size_t> &idx)
{
    for (auto &x : idx)
        os << data[x] << ' ';
    os << endl;
}
 
int main()
{
    ifstream input("input.txt");
    if (!input.good()) return -1;
    int x;
    vector<int> vals;
    while ( input >> x )
        vals.push_back( move(x) );
    input.close();
 
    const size_t n = vals.size() - 1;
    const size_t k = 5;
    if ( n + 1 < k) return -1;
 
    ofstream output("output.txt");
    vector<size_t> comb(k);
 
    for (auto i = 0; i != k; i++)
        comb[i] = i;
 
    to_file(output, vals, comb);
 
    while (increase(comb, n) )
        to_file(output, vals, comb);
 
    output.close();
    return 0;
}
Rosman
 Аватар для Rosman
0 / 0 / 0
Регистрация: 18.12.2012
Сообщений: 4
26.05.2013, 17:13  [ТС]     Сгенерировать все k -элементные подмножества из N #3
Спасибо большое,

Добавлено через 5 минут
только он выводит ошибки :
2.cpp(26): error C2143: синтаксическая ошибка: отсутствие "," перед ":"
2.cpp(26): error C2530: x: ссылки должны быть инициализированы
2.cpp(26): error C3531: x: символ, тип которого содержит спецификатор "auto" должен иметь инициализатор
Olivеr
 Аватар для Olivеr
411 / 407 / 13
Регистрация: 06.10.2011
Сообщений: 830
27.05.2013, 00:48     Сгенерировать все k -элементные подмножества из N #4
Включите C++11

Добавлено через 1 минуту
или поправьте на
C++
1
2
3
4
5
6
void to_file(ofstream &os, const vector<int> &data, const vector<size_t> &idx)
{
    for (size_t i = 0; i != idx.size(); i++)
        os << data[ idx[i] ] << ' ';
    os << endl;
}
и
C++
1
2
    for (int i = 0; i != k; i++)
        comb[i] = i;
Саша Чернышев
0 / 0 / 0
Регистрация: 07.06.2015
Сообщений: 1
07.06.2015, 23:05     Сгенерировать все k -элементные подмножества из N #5
У меня visual studio 2012 и данная программа не даёт никакого результата, в чём может быть причина?

Добавлено через 1 минуту
Цитата Сообщение от Olivеr Посмотреть сообщение
Включите C++11

Добавлено через 1 минуту
или поправьте на
C++
1
2
3
4
5
6
void to_file(ofstream &os, const vector<int> &data, const vector<size_t> &idx)
{
    for (size_t i = 0; i != idx.size(); i++)
        os << data[ idx[i] ] << ' ';
    os << endl;
}
и
C++
1
2
    for (int i = 0; i != k; i++)
        comb[i] = i;
У меня visual studio 2012 и данная программа не даёт никакого результата, в чём может быть причина?
Yandex
Объявления
07.06.2015, 23:05     Сгенерировать все k -элементные подмножества из N
Ответ Создать тему
Опции темы

Текущее время: 00:15. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru