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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.67
olea
5 / 5 / 1
Регистрация: 30.01.2012
Сообщений: 153
#1

Генерация комбинаций из n по m - C++

01.12.2013, 21:18. Просмотров 1334. Ответов 26
Метки нет (Все метки)

Здравствуйте!
Написала функцию для генерации комбинаций. Подскажите в чем ошибка, выдает не все варианты.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int Generare(int Key[], int m, bool &ind){
    int i,j;
    bool gasit;
    i =m;
    gasit = false;
while ((i >= 1) && (not gasit)){
        if (Key[i] < (n-m+i)) {
            gasit = true;
        }
        i--;
    }
    if (gasit) {
        Key[i] = Key[i] + 1;
        for (j = i+1; j <=m; ++j){
            Key[j] = Key[j-1] +1;
        }
        ind = true; 
    }
    else {
        ind = false;
    }
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.12.2013, 21:18
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Генерация комбинаций из n по m (C++):

Перебор комбинаций - C++
Здравствуйте! Возникла такая задача. Дан одномерный массив из N цифр,нужно составить все возможные комбинации чисел из этих цифр(числа...

Подсчет Комбинаций - C++
решите, пожалуйста, эту задачку, заранее спасибо Постановка задачи Вы должны точно вычислить значение C(N, K) для заданного N а K....

Перебор комбинаций - C++
Доброго времени суток. Нашел в сети картинку - генератор речей. 4 столбика по 6 фраз в каждом. При переборе слева направо получается...

Вычисление числа комбинаций - C++
Вопрос, конечно элементарный но сам запутался. Какое количество комбинаций можно получить из трех чисел. Вообщем похоже на бинарный код. ...

Количество различных комбинаций - C++
Добра всем. Задача: есть &quot;слово&quot; нужно написать программу, которая подсчитала бы количество комбинаций букв этого слова, т.е. лсово, лосво...

Функция количества комбинаций - C++
Есть ли функция на C++ которая возвращает количество комбинаций для заданного числа элементов в excel это функция ЧИСЛКОМБ(число;...

26
ya_noob
_
201 / 145 / 9
Регистрация: 08.10.2011
Сообщений: 432
02.12.2013, 12:28 #16
olea, уточните, что вам надо: сочетания (MrGluck) или размещения (ninja2), а то возникла спорная ситуация.
0
MrGluck
Модератор
Эксперт CЭксперт С++
7279 / 4440 / 650
Регистрация: 29.11.2010
Сообщений: 12,022
02.12.2013, 12:53 #17
ya_noob, задача одна, просто ninja2 решает её через размещения с отсечением (и то, далее надо инфу собирать, сортировать, дубли отсеивать...)
Цитата Сообщение от ninja2 Посмотреть сообщение
а нужна простота
нет там простоты
1
ya_noob
_
201 / 145 / 9
Регистрация: 08.10.2011
Сообщений: 432
02.12.2013, 13:06 #18
Цитата Сообщение от olea Посмотреть сообщение
Генерация комбинаций из n по m
MrGluck, я вот например не понимаю что нужно ТСу: сочетания или размещения. что такое комбинации?
Цитата Сообщение от MrGluck Посмотреть сообщение
просто ninja2 решает её через размещения
мне кажется ninja изначально думал про размещения, но потом почему-то засомневался:
Цитата Сообщение от ninja2 Посмотреть сообщение
Ну ладно да там уже имея все варианты их просто можно отсортировать и получить те которые нужны.
и начал городить ерунду.
Мораль: стой на своем до конца!
0
MrGluck
Модератор
Эксперт CЭксперт С++
7279 / 4440 / 650
Регистрация: 29.11.2010
Сообщений: 12,022
02.12.2013, 13:13 #19
ya_noob, это был бы вопрос если бы не Генерация комбинаций из n по m
0
ya_noob
_
201 / 145 / 9
Регистрация: 08.10.2011
Сообщений: 432
02.12.2013, 13:55 #20
MrGluck, может быть вы и правы, но я буду сомневаться пока ТС явно не напишет сочетания или размещения
0
olea
5 / 5 / 1
Регистрация: 30.01.2012
Сообщений: 153
02.12.2013, 14:00  [ТС] #21
Например, есть числа 1234
Мне нужно получить все возможные комбинации из 4 по 3, не учитывая перестановки
Результат:
123
124
234
0
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,926
Записей в блоге: 1
02.12.2013, 14:24 #22
Все правильно! olea и MrGluck тебе подсказывали в правильном направлении. А ninja2 стал подсказывать неверный путь! Вместо оптимального алгоритма он решил выехать на всём готовом, при этом перебирая вообще перестановки, а не сочетания, т.е. делая лишнюю работу, только он не учел, что такие "сочетания" повторяться будут!
0
ninja2
231 / 187 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
02.12.2013, 14:30 #23
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
А ninja2 стал подсказывать неверный путь!
Прежде всего нужно смотреть на реальную задачу, важна там скорость или нет, а в реальной задаче я думаю скорость не важна, так что можно и моим алгоритмом пользоваться или можно делать перестановку до половины возможных вариантов. Тут еще нужно экспериментировать чей алгоритм будет быстрее работать. Бывает что для одних чисел работает быстрее, а уже когда числа становятся большие то может так получиться что мой алгоритм будет быстрее. После определенного промежутка чисел может работать в разы медленнее, так что нужно смотреть на реальную решаемую задачу и выбирать алгоритм исходя из нее!!!
0
Kuzia domovenok
1891 / 1746 / 118
Регистрация: 25.03.2012
Сообщений: 5,926
Записей в блоге: 1
02.12.2013, 16:10 #24
ninja2, не помню, уже говорилось ли, что в твоём варианте сочетания будут повторяться? Например, при n=5 k=3, ты сгенерируешь
1 2 3 (4 5 выкинул)
и
1 2 3 (5 4 выкинул)

Добавлено через 1 час 14 минут
Вот, кстати, мой вариант:
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
#include <iostream>
#include <vector>
#include <algorithm> // for copy
#include <iterator> // for ostream_iterator
using namespace std;
bool GetNext(vector<int>& combo, int N){
    int k=combo.size();
    int i=k-1;
    int j;
    while(combo.at(i)+k-i>N) 
        if(--i<0) return false;
    combo.at(i)++;
    for (j=i+1; j<k; j++) combo.at(j)=combo.at(j-1)+1;
    return true;
}
int main() {
    int n, k;
    cout<<"Input n, k: ";
    //cin>>n>>k;
    n=7; k=5;
    vector<int> result;
    for (int i=0; i<k; i++)
        result.push_back(i);
    do{
        copy(result.begin(), result.end(), ostream_iterator<int>(cout, ", "));
        cout<<endl;
    }while(GetNext(result, n));
    return 0;
}
1
ya_noob
_
201 / 145 / 9
Регистрация: 08.10.2011
Сообщений: 432
02.12.2013, 19:01 #25
Цитата Сообщение от olea Посмотреть сообщение
не учитывая перестановки
с этого и надо было начинать
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>
#include <algorithm>
#include <iterator>
#include <vector>
using namespace std;
 
vector< int > stor;
 
void just_do_it( int n, int m )
{
    if ( !m )
    {
        copy( stor.begin(), stor.end(), ostream_iterator< int >( cout, " " ) );
        cout << endl;
        return;
    }
    for ( int i = n; i > 0; --i )
    {
        stor.push_back( i );
        just_do_it( i - 1, m - 1 );
        stor.pop_back();
    }
}
 
int main()
{
    int n, m;
 
    cin >> n >> m;
    just_do_it( n, m );
 
    return 0;
}
1
olea
5 / 5 / 1
Регистрация: 30.01.2012
Сообщений: 153
03.12.2013, 13:50  [ТС] #26
спасибо всем за помощь. воспользовалась алгоритмом MrGluck -а. Проверяла работу алгоритма Kuzia domovenok - работает, остальные не проверяла. еще раз спасибо. А если не секрет, какой стаж программирования у вас?
0
MrGluck
Модератор
Эксперт CЭксперт С++
7279 / 4440 / 650
Регистрация: 29.11.2010
Сообщений: 12,022
03.12.2013, 17:01 #27
3.5 года (С++)
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.12.2013, 17:01
Привет! Вот еще темы с ответами:

Перебор комбинаций с исключениями - C++
Здраствуйте!Хочу попробовать сделать задачу:есть число n которое указывает количество цифр и есть число k которое указывает количество...

Помогите с выводом комбинаций - C++
Вот есть код для вывода комбинаций символов. Но он почему то ничего не выводит на экран. В чём может быть проблема? #include&lt;stdio.h&gt; ...

Генератор комбинаций с повторениями - C++
Вот код он выводит все комбинации с повторениями от 1 до 3 и можно увеличить до 9. Беда в том что он начинаем генерировать с 1 const int...

Разработать программу расчета комбинаций - C++
Помогите пожалуйста. Всю суть я постарался изложить на картинке П.5.18. Правил Запрещено размещать задания и решения в виде картинок...


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

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

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