Форум программистов, компьютерный форум 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++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
02.12.2013, 00:22     Генерация комбинаций из n по m #2
Цитата Сообщение от olea Посмотреть сообщение
Написала функцию для генерации комбинаций.
А что за комбинации?
max_besheniy
25 / 25 / 1
Регистрация: 21.11.2013
Сообщений: 208
02.12.2013, 00:26     Генерация комбинаций из n по m #3
Если речь о c(n,m), то вот работающий код
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
using namespace std;
int c(int x, int y)
{
    if (x == y || y == 0) return 1;
    else if (y > x) return 0;
    else return c(x - 1, y - 1) + c(x - 1, y);
}
int main()
{
    int n, m;
    cin >> n >> m;
    cout << c(n, m) << endl;
    system("pause");
}
Kuzia domovenok
 Аватар для Kuzia domovenok
1882 / 1737 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
02.12.2013, 00:36     Генерация комбинаций из n по m #4
max_besheniy, ему нужно не число комбинаций, а сами комбинации!!!
например m=2 n=3
комбинации
1 2
1 3
2 3
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
02.12.2013, 00:47     Генерация комбинаций из n по m #5
Kuzia domovenok, а чо три комбинации когда всего два числа?
Комбинации каких данных ему нужны?
Ты похоже от фанаря написал!?
max_besheniy
25 / 25 / 1
Регистрация: 21.11.2013
Сообщений: 208
02.12.2013, 00:50     Генерация комбинаций из n по m #6
Все правильно, из 3 чисел можно составить 3 сочетания по 2 числа
olea
5 / 5 / 1
Регистрация: 30.01.2012
Сообщений: 153
02.12.2013, 00:51  [ТС]     Генерация комбинаций из n по m #7
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
max_besheniy, ему нужно не число комбинаций, а сами комбинации!!!
например m=2 n=3
комбинации
1 2
1 3
2 3
Да, именно так
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4920 / 2663 / 243
Регистрация: 29.11.2010
Сообщений: 7,405
02.12.2013, 01:00     Генерация комбинаций из n по m #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
#include <iostream>
#include <clocale>
 
using namespace std;
 
int main()
{
    setlocale(LC_ALL, "");
    const int N = 6, M = 3; // N - размер множества, M - искомого подмножества
    int A[N];         // имеем множество A {1, ... N}
    for (int i = 0; i < N; i++)
        A[i] = i + 1; // заполняем множество
    int a[N] = {0};   // надо ли включать элемент множества
    int counter = 0;  // счетчик
    while (a[0] != 2) // пока не прошли все элементы
    {
        int size = 0;  // размер подмножества
        for (int i = 0; i < N; i++)
            if(a[i])   // если нужно печатать
                size++;
        if (size == M) // если размер равен искомому - выводим на экран
        {
            for (int i = 0; i < N; i++) // выводим подмножество
                if(a[i]) // если нужно печатать
                    cout << A[i] << ' ';
            cout << endl;
            counter++; // увеличиваем счетчик на один
        }
 
        a[N-1]++; // увеличиваем последний разряд
        for (int i = N - 1; i > 0; i--) // если нужен сдвиг
            if(a[i] == 2) // увеличиваем след. разряд
            {
                a[i-1]++;
                a[i] = 0;
            }
    }
    cout << "Всего подмножеств заданной длины: " << counter << endl;
    return 0;
}
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
02.12.2013, 01:02     Генерация комбинаций из n по m #9
Просто для m=2 и n=3 нужно перебирать как для 3 чисел, только выводить первые два числа, а третье число нет.
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4920 / 2663 / 243
Регистрация: 29.11.2010
Сообщений: 7,405
02.12.2013, 01:05     Генерация комбинаций из n по m #10
Цитата Сообщение от ninja2 Посмотреть сообщение
Просто для m=2 и n=3 нужно перебирать как для 3 чисел, только выводить первые два числа, а третье число нет.
получатся дубляжи.
правильно задача звучит так:
Вывести все подмножеств длины m заданного множества n [1, N]
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
02.12.2013, 01:18     Генерация комбинаций из n по m #11
Цитата Сообщение от MrGluck Посмотреть сообщение
правильно задача звучит так:
Вывести все подмножеств длины m заданного множества n [1, N]
Нет там написано все комбинации, а всех комбинаций будет не 3 а 6 для m=2 и n=3, от мой код как раз все возможные комбинации и перебирает:
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
#include <iostream>     // std::cout
#include <algorithm>    // std::next_permutation, std::sort
#include <vector>
using namespace::std;
 
void Generare(int m, int n)
{
    vector<int> myints;
    //заполняем массив
    for(int i=1;i<=n;i++)
        myints.push_back(i);
 
    std::sort (myints.begin(),myints.end());
 
    do 
    {
        for(int i=0;i<m;i++)
            std::cout << myints[i] << ' ';
        cout << '\n';
    } 
    while ( std::next_permutation(myints.begin(),myints.end()) );
}
 
int main () {
  Generare(2,3);
 
  return 0;
}
Добавлено через 7 минут
MrGluck, Ну ладно да там уже имея все варианты их просто можно отсортировать и получить те которые нужны.
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4920 / 2663 / 243
Регистрация: 29.11.2010
Сообщений: 7,405
02.12.2013, 01:27     Генерация комбинаций из n по m #12
Цитата Сообщение от ninja2 Посмотреть сообщение
Добавлено через 7 минут
MrGluck, Ну ладно да там уже имея все варианты их просто можно отсортировать и получить те которые нужны.
итого неоптимальный алгоритм решения задачи для нахождения подмножеств через усечение перестановок.
Когда изначально требуется совсем другое. Можно и правое ухо левой рукой почесать через затылок. Только надо ли?
olea
5 / 5 / 1
Регистрация: 30.01.2012
Сообщений: 153
02.12.2013, 04:48  [ТС]     Генерация комбинаций из n по m #13
MrGluck, спасибо. скажите, а модифицировать мой алгоритм возможно?
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4920 / 2663 / 243
Регистрация: 29.11.2010
Сообщений: 7,405
02.12.2013, 06:52     Генерация комбинаций из n по m #14
Если честно - мне лень в него вникать, по моему у меня самое простое решение.
ninja2
 Аватар для ninja2
230 / 186 / 7
Регистрация: 26.09.2012
Сообщений: 2,018
Завершенные тесты: 1
02.12.2013, 11:51     Генерация комбинаций из n по m #15
olea, И вообще если скорость не важна, а нужна простота, то попробуй мой алгоритм доработать!!!
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
02.12.2013, 12:28     Генерация комбинаций из n по m #16
olea, уточните, что вам надо: сочетания (MrGluck) или размещения (ninja2), а то возникла спорная ситуация.
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4920 / 2663 / 243
Регистрация: 29.11.2010
Сообщений: 7,405
02.12.2013, 12:53     Генерация комбинаций из n по m #17
ya_noob, задача одна, просто ninja2 решает её через размещения с отсечением (и то, далее надо инфу собирать, сортировать, дубли отсеивать...)
Цитата Сообщение от ninja2 Посмотреть сообщение
а нужна простота
нет там простоты
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
02.12.2013, 13:06     Генерация комбинаций из n по m #18
Цитата Сообщение от olea Посмотреть сообщение
Генерация комбинаций из n по m
MrGluck, я вот например не понимаю что нужно ТСу: сочетания или размещения. что такое комбинации?
Цитата Сообщение от MrGluck Посмотреть сообщение
просто ninja2 решает её через размещения
мне кажется ninja изначально думал про размещения, но потом почему-то засомневался:
Цитата Сообщение от ninja2 Посмотреть сообщение
Ну ладно да там уже имея все варианты их просто можно отсортировать и получить те которые нужны.
и начал городить ерунду.
Мораль: стой на своем до конца!
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4920 / 2663 / 243
Регистрация: 29.11.2010
Сообщений: 7,405
02.12.2013, 13:13     Генерация комбинаций из n по m #19
ya_noob, это был бы вопрос если бы не Генерация комбинаций из n по m
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.12.2013, 13:55     Генерация комбинаций из n по m
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
02.12.2013, 13:55     Генерация комбинаций из n по m #20
MrGluck, может быть вы и правы, но я буду сомневаться пока ТС явно не напишет сочетания или размещения
Yandex
Объявления
02.12.2013, 13:55     Генерация комбинаций из n по m
Ответ Создать тему
Опции темы

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