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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 34, средняя оценка - 4.65
Iworb
анимешник++
93 / 60 / 2
Регистрация: 03.11.2009
Сообщений: 413
#1

Сгенерировать все сочетания длины k из чисел 0,1,2,...n-1 - C++

30.03.2011, 22:04. Просмотров 4803. Ответов 9

В функцию передаем n и k, она возвращает матрицу размерами C(n,k) строк на k столбцов
К примеру n = 4, k = 2 (числа 0 1 2 3)
Функция должна вернуть:
Код
01
02
03
12
13
23
Помогите пожалуйста, кто знает комбинаторику.

Добавлено через 24 минуты
(C(n,k) я считаю программно, поэтому описывать не надо)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.03.2011, 22:04
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Сгенерировать все сочетания длины k из чисел 0,1,2,...n-1 (C++):

В заданном диапазоне чисел найти все сочетания цифр без повторений - C++
Доброго времени суток! Помогите исправить код программы.Вот задание: Для заданных m и n найти все сочетания по m из чисел 1,2,...,n, без...

вычислить все сочетания из N элементов по M - C++
на С нужно реализовать алгоритм вычисления всех возможных сочетаний из N элементов по M. подскажите пожалуста, как это сделать

Сгенерировать 10 чисел в интервале от 1 до 50 и посчитать, сколько среди них чисел > 15 - C++
Написать программу, которая генерирует 10 целых случайных чисел в интервале от 1 до 50. Вывести их на экран и посчитать, сколько среди них...

STL: найти все максимальные цепочки подряд идущих положительных чисел с указанием длины каждой цепочки - C++
Создать массив длины N (число N вводится с клавиатуры). Заполнить массив рандомно. Найти все максимальные цепочки подряд идущих...

Преобразовать строку , заменив все сочетания “авс” на ”ghn” - C++
Постановка задачи: Задать символьную строку, состоящую из слов. Слова разделены группой пробелов. Выполнить обработку по варианту....

В файле заменить все слова максимальной длины на слова минимальной длины - C++
Нужно в считанном из файла тексте заменить все слова максимальной длины на слова минимальной длины, а результат записать в новый файл....

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
iama
1250 / 975 / 49
Регистрация: 30.07.2010
Сообщений: 5,297
30.03.2011, 22:18 #2
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
#include <iostream>
#include <string>
#include <math.h>
 
using namespace std;
using std::string;
 
int main()
{
  int n, k, i, p, c, q, l;
  string s;
 
  cin >> k >> n;
 
  l = pow(n, k);
 
  for (i = 0; i < l; i++){
    p = i; s = ""; c = 0;
 
    while (pow(n, c) <= p) c++;
 
    for (q = 0; q < c; q++) {
      s += (char) (p % n + 48);
      p /= n;
    }
 
    if (s.length() < k) for (p = 0; p < k - s.length(); p++) cout << "0";
 
    for (p = 0; p < s.length(); p++) cout << s[s.length() - p - 1];
 
    cout << endl;
  }
 
  return 0;
}
вроде, так, а пример ваш, вроде, неточен, если я ничего не путаю
Iworb
анимешник++
93 / 60 / 2
Регистрация: 03.11.2009
Сообщений: 413
30.03.2011, 22:39  [ТС] #3
нет, вы немного не поняли. Вы делаете все перестановки, мне же нужны все сочетания (т.е. одно и тоже число нельзя использовать 2 раза - нету 00 и 11). Если в Вашей программе это убрать, тогда вроде то что нужно.
Кому интересно - есть готовый код на перле - http://codepad.org/zFGF5Cy1#output
iama
1250 / 975 / 49
Регистрация: 30.07.2010
Сообщений: 5,297
30.03.2011, 22:48 #4
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
#include <iostream>
#include <string>
#include <math.h>
 
using namespace std;
using std::string;
 
int main()
{
  int n, k, i, p, c, q, l; bool get_out;
  string s, t;
 
  cin >> k >> n;
 
  l = pow(n, k);
 
  for (i = 0; i < l; i++){
    p = i; s = ""; c = 0;
 
    while (pow(n, c) <= p) c++;
 
    for (q = 0; q < c; q++) {
      s += (char) (p % n + 48);
      p /= n;
    }
 
    if (s.length() < k) for (p = 0; p < k - s.length(); p++) cout << "0";
 
    get_out = false;
    for (q = 0; q < c; q++) {
      t = "";
      for (p = 0; p < s.length(); p++) t += (char) (p + 48);
      if (t == s) get_out = true;
    }
 
    if (get_out) continue;
 
    for (p = 0; p < s.length(); p++) cout << s[s.length() - p - 1];
 
    cout << endl;
    
  }
 
  return 0;
}
Iworb
анимешник++
93 / 60 / 2
Регистрация: 03.11.2009
Сообщений: 413
30.03.2011, 23:17  [ТС] #5
Вот что программа выдала в результате:
Код
3
6
000
001
002
003
004
005
0011
012
013
014
015
020
021
022
023
024
025
030
031
Для продолжения нажмите любую клавишу . . .
До истины далековато... да и одно число из 4х цифр

Добавлено через 25 минут
Попробовал сделать из того кода:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void perl(int n, int k)
{
    std::vector<int> a(k);
    for(int i=0;i<a.size();i++) a[i]=i;
    print(a);
    for(;;)
    {
        int j;
        for(j=0;j<k-1;j++)
            if ( a[j] + 1 < a[j + 1] )
                break;
        if(!(j<k-1))
        {
            if(a[k-1]<n-1)
                j=k-1;
            else
                break;
        }
        a[j]++;
        print(a);
        for(int i=0;i<j-1;i++) a[i]=i;
    }
}
Но выводит не все комбинации...
Mr.X
Эксперт С++
3049 / 1694 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
31.03.2011, 11:45 #6
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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
/////////////////////////////////////////////////////////////////////////////////////////
//В функцию передаем n и k, она возвращает матрицу размерами C(n,k) строк на k столбцов
//К примеру n = 4, k = 2 (числа 0 1 2 3)
//Функция должна вернуть:
//
//01
//02
//03
//12
//13
//23
/////////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <iostream>
#include <vector>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::vector<int>            T_combination;
typedef std::vector<T_combination>  T_combinations;
/////////////////////////////////////////////////////////////////////////////////////////
void  fill_combinations(int  n, int  k, T_combinations&  combinations)
{
    T_combination  combination_cur(k, -1);    
    for(int  ind = 0;;)    
    {         
        while(combination_cur[ind] == n - k + ind)
        {            
            if(--ind < 0) return;
        }        
        
        int  diff = combination_cur[ind] + 1 - ind;
        
        for(;; ++ind)
        {            
            combination_cur[ind] = ind + diff;            
            if(ind == k - 1) break;            
        }
        combinations.push_back(combination_cur);        
    }
}
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    std::cout << "Для вычисления сочетаний C(n, k) введите:"
              << std::endl
              << '\t'
              << "n = ";
 
    int  n = 0;
    std::cin >> n;
 
    std::cout << '\t'
              << "k = ";
 
    int k = 0;
    std::cin >> k;
 
    T_combinations  combinations;
    fill_combinations(n, k, combinations);
    std::cout << std::endl
              << "Все "
              << combinations.size()
              <<" комбинаций C("
              << n
              << ", "
              << k
              << "):"
              << std::endl;
 
    for(T_combinations::const_iterator  comb_it = combinations.begin();
        comb_it != combinations.end(); ++comb_it)
    {
        std::copy(comb_it->begin(), comb_it->end(), 
                  std::ostream_iterator<int>(std::cout, " "));
        std::cout << std::endl;
    }
    std::cout << std::endl;
}
Iworb
анимешник++
93 / 60 / 2
Регистрация: 03.11.2009
Сообщений: 413
31.03.2011, 19:11  [ТС] #7
Mr.X, Спасибо, скажите, а вот это
Код
error C2039: 'ostream_iterator' : is not a member of 'std'
можно сделать по другому как-нибудь? Странно конечно, но ругается, что нет такого - 10я студия.

Добавлено через 17 минут
UPD переделал - простенькую распечатку сделал - теперь всё нормально, спасибо!
Mr.X
Эксперт С++
3049 / 1694 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
31.03.2011, 20:53 #8
Цитата Сообщение от Iworb Посмотреть сообщение
Mr.X, Спасибо, скажите, а вот это
Код
1
error C2039: 'ostream_iterator' : is not a member of 'std'
можно сделать по другому как-нибудь? Странно конечно, но ругается, что нет такого - 10я студия.
Ну, вообще-то надо
C++
1
#include <iterator>
включить. У меня в 2008-й студии и так компилирует, поэтому я не заморачивался.
Байт
Эксперт C
15982 / 10250 / 1536
Регистрация: 24.12.2010
Сообщений: 19,332
29.09.2015, 15:53 #9
Цитата Сообщение от Iworb Посмотреть сообщение
можно сделать по другому как-нибудь?
Комбинаторика на С++
Посмотрите. Может быть подойдет.
SlavaSSU
215 / 160 / 45
Регистрация: 17.07.2012
Сообщений: 587
29.09.2015, 16:51 #10
еще вариант.

C++ (Qt)
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
#include <iostream>
 
using namespace std;
 
bool used[123];
int n, k;
 
void rec(int lst, int cnt) {
    if(cnt == k) {
        for(int i = 0; i < n; i++) {
            if(used[i]) {
                cout << i << ' ';
            }
        }
        cout << endl;
        return;
    }
 
    if(lst + 1 >= n) {
        return;
    }
 
    used[lst + 1] = true;
    rec(lst + 1, cnt + 1);
    used[lst + 1] = false;
    rec(lst + 1, cnt);
    return;
}
 
int main() {
    cin >> n >> k;
    rec(-1, 0);
    return 0;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.09.2015, 16:51
Привет! Вот еще темы с ответами:

Сгенерировать все k -элементные подмножества из N - C++
Дело все в том, что мне надо написать программу, которой на вход давался файл с N целых чисел через пробел, пользователь дает на ввод число...

необходимо каким-то образом пронумеровать все сочетания, никак не могу придумать алгоритм - C++
Мне необходимо каким-то образом пронумеровать все сочетания, никак не могу придумать алгоритм. Например из 10 по 5 = 252, если нумеровать...

Из заданной строки получить новую, заменив в ней все сочетания «abcd» на «abc» - C++
Помогите с задачей, кто знает, как сделать проверку? Т.е. чтобы при вводе цифр, пробелов или пустой строки выводилось сообщение об этом и...

Из заданной строки получить новую, заменив в ней все сочетания «abcd» на «abc» - C++
Из заданной строки получить новую, заменив в ней все сочетания «abcd» на «abc».


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
29.09.2015, 16:51
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru