Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.68/40: Рейтинг темы: голосов - 40, средняя оценка - 4.68
5 / 5 / 2
Регистрация: 30.01.2012
Сообщений: 153
1

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

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

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

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
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
01.12.2013, 21:18
Ответы с готовыми решениями:

Генерация всевозможных комбинаций
Здравствуйте! Возникла следующая задача: есть таблица, в каждой строчке находится разное число...

Генерация всех комбинаций из символов
У меня есть массив array или строк f,d,d,o,g......... Как получить все комбинации с длиной(3 или...

Генерация всех возможных комбинаций
Доброго времени суток, подскажите идею, нужно чтобы функция составила все возможные комбинации из...

Генерация комбинаций чисел для заданой суммы
Есть массив чисел от 1 до 50. Пользователь вводит сумму и программа выбирает все возможные варианты...

26
979 / 196 / 33
Регистрация: 26.09.2012
Сообщений: 2,041
02.12.2013, 00:22 2
Цитата Сообщение от olea Посмотреть сообщение
Написала функцию для генерации комбинаций.
А что за комбинации?
0
25 / 25 / 5
Регистрация: 21.11.2013
Сообщений: 208
02.12.2013, 00:26 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");
}
0
4064 / 3318 / 924
Регистрация: 25.03.2012
Сообщений: 12,493
Записей в блоге: 1
02.12.2013, 00:36 4
max_besheniy, ему нужно не число комбинаций, а сами комбинации!!!
например m=2 n=3
комбинации
1 2
1 3
2 3
1
979 / 196 / 33
Регистрация: 26.09.2012
Сообщений: 2,041
02.12.2013, 00:47 5
Kuzia domovenok, а чо три комбинации когда всего два числа?
Комбинации каких данных ему нужны?
Ты похоже от фанаря написал!?
0
25 / 25 / 5
Регистрация: 21.11.2013
Сообщений: 208
02.12.2013, 00:50 6
Все правильно, из 3 чисел можно составить 3 сочетания по 2 числа
0
5 / 5 / 2
Регистрация: 30.01.2012
Сообщений: 153
02.12.2013, 00:51  [ТС] 7
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
max_besheniy, ему нужно не число комбинаций, а сами комбинации!!!
например m=2 n=3
комбинации
1 2
1 3
2 3
Да, именно так
0
Форумчанин
Эксперт CЭксперт С++
8215 / 5045 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
02.12.2013, 01:00 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;
}
1
979 / 196 / 33
Регистрация: 26.09.2012
Сообщений: 2,041
02.12.2013, 01:02 9
Просто для m=2 и n=3 нужно перебирать как для 3 чисел, только выводить первые два числа, а третье число нет.
0
Форумчанин
Эксперт CЭксперт С++
8215 / 5045 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
02.12.2013, 01:05 10
Цитата Сообщение от ninja2 Посмотреть сообщение
Просто для m=2 и n=3 нужно перебирать как для 3 чисел, только выводить первые два числа, а третье число нет.
получатся дубляжи.
правильно задача звучит так:
Вывести все подмножеств длины m заданного множества n [1, N]
0
979 / 196 / 33
Регистрация: 26.09.2012
Сообщений: 2,041
02.12.2013, 01:18 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, Ну ладно да там уже имея все варианты их просто можно отсортировать и получить те которые нужны.
0
Форумчанин
Эксперт CЭксперт С++
8215 / 5045 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
02.12.2013, 01:27 12
Цитата Сообщение от ninja2 Посмотреть сообщение
Добавлено через 7 минут
MrGluck, Ну ладно да там уже имея все варианты их просто можно отсортировать и получить те которые нужны.
итого неоптимальный алгоритм решения задачи для нахождения подмножеств через усечение перестановок.
Когда изначально требуется совсем другое. Можно и правое ухо левой рукой почесать через затылок. Только надо ли?
1
5 / 5 / 2
Регистрация: 30.01.2012
Сообщений: 153
02.12.2013, 04:48  [ТС] 13
MrGluck, спасибо. скажите, а модифицировать мой алгоритм возможно?
0
Форумчанин
Эксперт CЭксперт С++
8215 / 5045 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
02.12.2013, 06:52 14
Если честно - мне лень в него вникать, по моему у меня самое простое решение.
1
979 / 196 / 33
Регистрация: 26.09.2012
Сообщений: 2,041
02.12.2013, 11:51 15
olea, И вообще если скорость не важна, а нужна простота, то попробуй мой алгоритм доработать!!!
0
_
317 / 151 / 27
Регистрация: 08.10.2011
Сообщений: 432
02.12.2013, 12:28 16
olea, уточните, что вам надо: сочетания (MrGluck) или размещения (ninja2), а то возникла спорная ситуация.
0
Форумчанин
Эксперт CЭксперт С++
8215 / 5045 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
02.12.2013, 12:53 17
ya_noob, задача одна, просто ninja2 решает её через размещения с отсечением (и то, далее надо инфу собирать, сортировать, дубли отсеивать...)
Цитата Сообщение от ninja2 Посмотреть сообщение
а нужна простота
нет там простоты
1
_
317 / 151 / 27
Регистрация: 08.10.2011
Сообщений: 432
02.12.2013, 13:06 18
Цитата Сообщение от olea Посмотреть сообщение
Генерация комбинаций из n по m
MrGluck, я вот например не понимаю что нужно ТСу: сочетания или размещения. что такое комбинации?
Цитата Сообщение от MrGluck Посмотреть сообщение
просто ninja2 решает её через размещения
мне кажется ninja изначально думал про размещения, но потом почему-то засомневался:
Цитата Сообщение от ninja2 Посмотреть сообщение
Ну ладно да там уже имея все варианты их просто можно отсортировать и получить те которые нужны.
и начал городить ерунду.
Мораль: стой на своем до конца!
0
Форумчанин
Эксперт CЭксперт С++
8215 / 5045 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
02.12.2013, 13:13 19
ya_noob, это был бы вопрос если бы не Генерация комбинаций из n по m
0
_
317 / 151 / 27
Регистрация: 08.10.2011
Сообщений: 432
02.12.2013, 13:55 20
MrGluck, может быть вы и правы, но я буду сомневаться пока ТС явно не напишет сочетания или размещения
0
02.12.2013, 13:55
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
02.12.2013, 13:55
Помогаю со студенческими работами здесь

Генерация всех возможных комбинаций слова путем манипуляций с регистрами букв
Привет всем! Появилась не стандартная задачка написать хитрый алгоритм. Вводим слово для...

Выборка подмножества комбинаций без повторов из множества всех комбинаций перестановок
Собственно вопрос. Существует ли алгоритм нахождения без перебора уникальных комбинаций в...

Найти число таких комбинаций, и сформировать массив из самих этих комбинаций, при которых выполняется условие
Ребята, помогите новичку) задача в следующем - ряд из 8 чисел, скажем условно, w1 w2... w8,...

Генератор комбинаций
Всем доброго дня(утра,вечера,ночи) сразу к делу. пишу прогу(интерфейс во вложении снизу) суть в...


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru