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

Генерация сочетаний из k элементов по n в лексикографическом порядке - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.70
inham130
0 / 0 / 0
Регистрация: 23.11.2011
Сообщений: 35
09.04.2013, 12:28     Генерация сочетаний из k элементов по n в лексикографическом порядке #1
Помогите пожалуйста понять в чем ошибка
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
#include<iostream>
 
using namespace std;
#define n 6
#define k 4
int x [k];
 
int main()
{
    int i, j;
 
    for(i=0; i<k; i++)
        x[i] = i+1;
 
    while(1)
    {
        for(i=0; i<k; i++)
            cout << x[i];
 
        cout << endl;
        for(i=k-1; i>=0; i--)
        {
            if(x[i] < n-k+i+1)
            {
                x[i]++;
                 for(j=i+1; j<k; j++)
                    x[j] = x[j-1] + 1;
            }
        }
        if(i==1) break;
    }
    return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.04.2013, 12:28     Генерация сочетаний из k элементов по n в лексикографическом порядке
Посмотрите здесь:

Следующая анаграмма строки в лексикографическом порядке C++
C++ Сортировка слов в строке в лексикографическом порядке (по алфавиту)
C++ Алгоритм генерации перестановок в лексикографическом порядке
Сортировка строк двумерного std::vector'а в лексикографическом порядке C++
C++ Упорядочить строки в лексикографическом порядке
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
09.04.2013, 14:43     Генерация сочетаний из k элементов по n в лексикографическом порядке #2
inham130,
Вот мой код :
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
#include <iostream>
#include <cmath>
#include <stack>
#include <algorithm>
#include <limits>
#include <string>
 
using namespace std;
 
int n, m;
stack <int> ans;
 
void brute(int pos, int cnt, int mask){
    if (cnt > m)
        return;
    if (pos == n){
        if (cnt == m)
            ans.push(mask);
        return;
    }
    brute(pos+1, cnt, mask);
    brute(pos+1, cnt+1, mask | (1<<pos));
}
 
int main(){
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "wt", stdout);
    cin >> n >> m;
    brute(0, 0, 0);
    printf("%d\n", ans.size());
    while (!ans.empty()){
        for (int j = 0; j < n; j++){
            if (ans.top() & (1<<j))printf("%d ", j+1);  
        }
        ans.pop();
        printf("\n");
    }
    return 0;
}
inham130
0 / 0 / 0
Регистрация: 23.11.2011
Сообщений: 35
09.04.2013, 17:54  [ТС]     Генерация сочетаний из k элементов по n в лексикографическом порядке #3
Вы не могли бы перевести код на C. У меня с ООП пока что туго.
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
09.04.2013, 18:29     Генерация сочетаний из k элементов по n в лексикографическом порядке #4
inham130, это раздел с++ а не си
BumerangSP
 Аватар для BumerangSP
4283 / 1405 / 121
Регистрация: 16.12.2010
Сообщений: 2,941
Записей в блоге: 3
09.04.2013, 19:47     Генерация сочетаний из k элементов по n в лексикографическом порядке #5
inham130, а где здесь ООП? Контейнер stack что ли? Тем более Ваш код на с++ (dpzm, хотя бы использование iostream).
Yandex
Объявления
09.04.2013, 19:47     Генерация сочетаний из k элементов по n в лексикографическом порядке
Ответ Создать тему
Опции темы

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