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

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

01.12.2013, 21:18. Показов 9309. Ответов 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
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
01.12.2013, 21:18
Ответы с готовыми решениями:

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

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

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

26
 Аватар для ninja2
979 / 196 / 33
Регистрация: 26.09.2012
Сообщений: 2,041
02.12.2013, 00:22
Цитата Сообщение от olea Посмотреть сообщение
Написала функцию для генерации комбинаций.
А что за комбинации?
0
25 / 25 / 5
Регистрация: 21.11.2013
Сообщений: 208
02.12.2013, 00:26
Если речь о 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
 Аватар для Kuzia domovenok
4268 / 3327 / 926
Регистрация: 25.03.2012
Сообщений: 12,531
Записей в блоге: 1
02.12.2013, 00:36
max_besheniy, ему нужно не число комбинаций, а сами комбинации!!!
например m=2 n=3
комбинации
1 2
1 3
2 3
1
 Аватар для ninja2
979 / 196 / 33
Регистрация: 26.09.2012
Сообщений: 2,041
02.12.2013, 00:47
Kuzia domovenok, а чо три комбинации когда всего два числа?
Комбинации каких данных ему нужны?
Ты похоже от фанаря написал!?
0
25 / 25 / 5
Регистрация: 21.11.2013
Сообщений: 208
02.12.2013, 00:50
Все правильно, из 3 чисел можно составить 3 сочетания по 2 числа
0
5 / 5 / 2
Регистрация: 30.01.2012
Сообщений: 153
02.12.2013, 00:51  [ТС]
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
max_besheniy, ему нужно не число комбинаций, а сами комбинации!!!
например m=2 n=3
комбинации
1 2
1 3
2 3
Да, именно так
0
Форумчанин
Эксперт CЭксперт С++
 Аватар для MrGluck
8216 / 5047 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
02.12.2013, 01:00
Нахождение подмножеств заданной длины
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
 Аватар для ninja2
979 / 196 / 33
Регистрация: 26.09.2012
Сообщений: 2,041
02.12.2013, 01:02
Просто для m=2 и n=3 нужно перебирать как для 3 чисел, только выводить первые два числа, а третье число нет.
0
Форумчанин
Эксперт CЭксперт С++
 Аватар для MrGluck
8216 / 5047 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
02.12.2013, 01:05
Цитата Сообщение от ninja2 Посмотреть сообщение
Просто для m=2 и n=3 нужно перебирать как для 3 чисел, только выводить первые два числа, а третье число нет.
получатся дубляжи.
правильно задача звучит так:
Вывести все подмножеств длины m заданного множества n [1, N]
0
 Аватар для ninja2
979 / 196 / 33
Регистрация: 26.09.2012
Сообщений: 2,041
02.12.2013, 01:18
Цитата Сообщение от 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Эксперт С++
 Аватар для MrGluck
8216 / 5047 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
02.12.2013, 01:27
Цитата Сообщение от ninja2 Посмотреть сообщение
Добавлено через 7 минут
MrGluck, Ну ладно да там уже имея все варианты их просто можно отсортировать и получить те которые нужны.
итого неоптимальный алгоритм решения задачи для нахождения подмножеств через усечение перестановок.
Когда изначально требуется совсем другое. Можно и правое ухо левой рукой почесать через затылок. Только надо ли?
1
5 / 5 / 2
Регистрация: 30.01.2012
Сообщений: 153
02.12.2013, 04:48  [ТС]
MrGluck, спасибо. скажите, а модифицировать мой алгоритм возможно?
0
Форумчанин
Эксперт CЭксперт С++
 Аватар для MrGluck
8216 / 5047 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
02.12.2013, 06:52
Если честно - мне лень в него вникать, по моему у меня самое простое решение.
1
 Аватар для ninja2
979 / 196 / 33
Регистрация: 26.09.2012
Сообщений: 2,041
02.12.2013, 11:51
olea, И вообще если скорость не важна, а нужна простота, то попробуй мой алгоритм доработать!!!
0
_
317 / 151 / 27
Регистрация: 08.10.2011
Сообщений: 432
02.12.2013, 12:28
olea, уточните, что вам надо: сочетания (MrGluck) или размещения (ninja2), а то возникла спорная ситуация.
0
Форумчанин
Эксперт CЭксперт С++
 Аватар для MrGluck
8216 / 5047 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
02.12.2013, 12:53
ya_noob, задача одна, просто ninja2 решает её через размещения с отсечением (и то, далее надо инфу собирать, сортировать, дубли отсеивать...)
Цитата Сообщение от ninja2 Посмотреть сообщение
а нужна простота
нет там простоты
1
_
317 / 151 / 27
Регистрация: 08.10.2011
Сообщений: 432
02.12.2013, 13:06
Цитата Сообщение от olea Посмотреть сообщение
Генерация комбинаций из n по m
MrGluck, я вот например не понимаю что нужно ТСу: сочетания или размещения. что такое комбинации?
Цитата Сообщение от MrGluck Посмотреть сообщение
просто ninja2 решает её через размещения
мне кажется ninja изначально думал про размещения, но потом почему-то засомневался:
Цитата Сообщение от ninja2 Посмотреть сообщение
Ну ладно да там уже имея все варианты их просто можно отсортировать и получить те которые нужны.
и начал городить ерунду.
Мораль: стой на своем до конца!
0
Форумчанин
Эксперт CЭксперт С++
 Аватар для MrGluck
8216 / 5047 / 1437
Регистрация: 29.11.2010
Сообщений: 13,453
02.12.2013, 13:13
ya_noob, это был бы вопрос если бы не Генерация комбинаций из n по m
0
_
317 / 151 / 27
Регистрация: 08.10.2011
Сообщений: 432
02.12.2013, 13:55
MrGluck, может быть вы и правы, но я буду сомневаться пока ТС явно не напишет сочетания или размещения
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
02.12.2013, 13:55
Помогаю со студенческими работами здесь

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

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Новые блоги и статьи
Модель микоризы: классовый агентный подход
anaschu 02.01.2026
Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .
Учёным и волонтёрам проекта «Einstein@home» удалось обнаружить четыре гамма-лучевых пульсара в джете Млечного Пути
Programma_Boinc 01.01.2026
Учёным и волонтёрам проекта «Einstein@home» удалось обнаружить четыре гамма-лучевых пульсара в джете Млечного Пути Сочетание глобально распределённой вычислительной мощности и инновационных. . .
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост.
Programma_Boinc 28.12.2025
Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / **********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / **********/ gallery/ bKBkQFf Пост отсюда. . .
Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США.
Programma_Boinc 26.12.2025
Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка.
Programma_Boinc 23.12.2025
Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
Как объединить две одинаковые БД Access с разными данными
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru