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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.67
olea
5 / 5 / 1
Регистрация: 30.01.2012
Сообщений: 153
01.12.2013, 21:18     Генерация комбинаций из n по m #1
Здравствуйте!
Написала функцию для генерации комбинаций. Подскажите в чем ошибка, выдает не все варианты.

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;
    }
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.12.2013, 21:18     Генерация комбинаций из n по m
Посмотрите здесь:

C++ Помогите с выводом комбинаций
Функция количества комбинаций C++
C++ Перебор комбинаций
Перебор комбинаций C++
Количество различных комбинаций C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
olea
5 / 5 / 1
Регистрация: 30.01.2012
Сообщений: 153
02.12.2013, 14:00  [ТС]     Генерация комбинаций из n по m #21
Например, есть числа 1234
Мне нужно получить все возможные комбинации из 4 по 3, не учитывая перестановки
Результат:
123
124
234
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
02.12.2013, 14:24     Генерация комбинаций из n по m #22
Все правильно! olea и MrGluck тебе подсказывали в правильном направлении. А ninja2 стал подсказывать неверный путь! Вместо оптимального алгоритма он решил выехать на всём готовом, при этом перебирая вообще перестановки, а не сочетания, т.е. делая лишнюю работу, только он не учел, что такие "сочетания" повторяться будут!
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
02.12.2013, 14:30     Генерация комбинаций из n по m #23
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
А ninja2 стал подсказывать неверный путь!
Прежде всего нужно смотреть на реальную задачу, важна там скорость или нет, а в реальной задаче я думаю скорость не важна, так что можно и моим алгоритмом пользоваться или можно делать перестановку до половины возможных вариантов. Тут еще нужно экспериментировать чей алгоритм будет быстрее работать. Бывает что для одних чисел работает быстрее, а уже когда числа становятся большие то может так получиться что мой алгоритм будет быстрее. После определенного промежутка чисел может работать в разы медленнее, так что нужно смотреть на реальную решаемую задачу и выбирать алгоритм исходя из нее!!!
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
02.12.2013, 16:10     Генерация комбинаций из n по m #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;
}
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
02.12.2013, 19:01     Генерация комбинаций из n по m #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;
}
olea
5 / 5 / 1
Регистрация: 30.01.2012
Сообщений: 153
03.12.2013, 13:50  [ТС]     Генерация комбинаций из n по m #26
спасибо всем за помощь. воспользовалась алгоритмом MrGluck -а. Проверяла работу алгоритма Kuzia domovenok - работает, остальные не проверяла. еще раз спасибо. А если не секрет, какой стаж программирования у вас?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.12.2013, 17:01     Генерация комбинаций из n по m
Еще ссылки по теме:

Вычисление числа комбинаций C++
Алгоритм генерации всех комбинаций C++
C++ Вычислить количество возможных комбинаций

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

Или воспользуйтесь поиском по форуму:
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4927 / 2670 / 243
Регистрация: 29.11.2010
Сообщений: 7,429
03.12.2013, 17:01     Генерация комбинаций из n по m #27
3.5 года (С++)
Yandex
Объявления
03.12.2013, 17:01     Генерация комбинаций из n по m
Ответ Создать тему
Опции темы

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