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

Комбинаторика на С++ - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.87
gorus95
5 / 5 / 1
Регистрация: 22.12.2012
Сообщений: 145
22.04.2013, 20:48     Комбинаторика на С++ #1
Нужно составить программу, или скорее функцию, которая для заданного натурального числа k выводит все возможные произведения k чисел с числами от 1 до n, где каждое следующее число больше предыдущего.

Понимаю что объяснение не очень, попробую показать на примере:
допустим наше n = 4, тогда у нас есть числа 1, 2, 3, 4.

при k = 1 программа должна выдать 1, 2, 3, 4
пусть k = 2, тогда программа должна выдать 12, 13, 14, 23, 24, 34
если например k = 3 тогда 123, 124, 234
если k = n тогда будет одна комбинация из всех чисел n, то есть в нашем случае 1234

помогите сделать программу которая для любого натурального n и k даст такие перестановки (желательно без использования algorithm, vector и т.д.)
уже третий час сижу, что-то не получается...
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.04.2013, 20:48     Комбинаторика на С++
Посмотрите здесь:

комбинаторика C++
Комбинаторика C++
комбинаторика в программировании C++
C++ Комбинаторика и переборные алгоритмы
C++ Комбинаторика
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Olivеr
 Аватар для Olivеr
411 / 407 / 13
Регистрация: 06.10.2011
Сообщений: 830
22.04.2013, 20:49     Комбинаторика на С++ #2
Вам нужны не перестановки, а сочетания из n по k (без повторений)
gorus95
5 / 5 / 1
Регистрация: 22.12.2012
Сообщений: 145
22.04.2013, 20:55  [ТС]     Комбинаторика на С++ #3
Olivеr, не знал как правильно сказать...
можете помочь?
Байт
 Аватар для Байт
13985 / 8816 / 1229
Регистрация: 24.12.2010
Сообщений: 15,972
22.04.2013, 20:57     Комбинаторика на С++ #4
Найти все возможные перестановки цифр
gorus95
5 / 5 / 1
Регистрация: 22.12.2012
Сообщений: 145
22.04.2013, 21:01  [ТС]     Комбинаторика на С++ #5
Байт, спасибо. но мне нужно без повторений, и чтоб каждая следующая цифра была больше предыдущей.
никак не получается написать
Байт
 Аватар для Байт
13985 / 8816 / 1229
Регистрация: 24.12.2010
Сообщений: 15,972
22.04.2013, 21:08     Комбинаторика на С++ #6
gorus95, Извиняюсь, там были перестановки, а у вас - сочетания. Тоже было где-то, сам участвовал ...
Но могу посоветовать такую книжонку - Липский В. "Комбинаторика для программистов". Наверное, сегодня есть что-то и посвежее.
Но вообще-то задача классическая. Поищите.
gorus95
5 / 5 / 1
Регистрация: 22.12.2012
Сообщений: 145
22.04.2013, 21:10  [ТС]     Комбинаторика на С++ #7
Байт, пытаюсь найти, но ничего пока нету, уже немало ищу
если найдете, буду благодарен
Байт
 Аватар для Байт
13985 / 8816 / 1229
Регистрация: 24.12.2010
Сообщений: 15,972
22.04.2013, 21:16     Комбинаторика на С++ #8
Это раз
http://e-maxx.ru/algo/generating_combinations
Два
http://www.prog.org.ru/topic_744_0.html
Три
http://forum.sources.ru/index.php?showtopic=330364
(кстати, из Липского)

Добавлено через 51 секунду
http://lmgtfy.com/?q=%D1%81%D0%BE%D1...86%D0%B8%D1%8F
Buckstabue
 Аватар для Buckstabue
175 / 124 / 6
Регистрация: 12.01.2012
Сообщений: 624
22.04.2013, 21:19     Комбинаторика на С++ #9
Сейчас времени нет, но я бы рассматривал n как основание сиситемы счисления, далее бы по умолчанию инициализировал массив из k элементов числами от 1 до n(или как можно ближе к этому). Далее бы увеличивал это число в этой системе счисления на 1, при этом при любом переполнении разряда, ставил бы на то место, где переполняется разряд, значение предыдущего(более левого разряда) + 1. Если перполняется самый первый разряд, то выход. Как-то так. Наверное, не самое эффективное решение... И не знаю работает ли
Ну и при переполнии разряда естественно по мере надобности инкрементировать все последующие более правые разряды
gorus95
5 / 5 / 1
Регистрация: 22.12.2012
Сообщений: 145
22.04.2013, 21:28  [ТС]     Комбинаторика на С++ #10
в общем у меня задача вычислить коэффициенты многочлена, если известны его корни, по формуле Виета
но чтоб это сделать для i-того коэффициента нужно сделать сумму таких перестановок корней
вот беда(
Байт
 Аватар для Байт
13985 / 8816 / 1229
Регистрация: 24.12.2010
Сообщений: 15,972
22.04.2013, 21:29     Комбинаторика на С++ #11
Цитата Сообщение от Buckstabue Посмотреть сообщение
на то место, где переполняется разряд
Вот как это место определить? Но идея здравая. Надо подумать... И не будет ли там слишком много повторов... Сейчас с ходу не соображу...
gorus95
5 / 5 / 1
Регистрация: 22.12.2012
Сообщений: 145
22.04.2013, 21:40  [ТС]     Комбинаторика на С++ #12
наткнулся на идею что может сделать что-то связанное с матрицей, если например записать для k = 2 матрицу

11 12 13 14
21 22 23 24
31 32 33 34
41 42 43 43
тогда те числа которые нам нужны будут в правом верхнем треугольнике матрицы, над главной диагональю
но если будет k = 5 или 10, там будет проблемно... там получается k-мерная матрица, тоже ни к чему(
Olivеr
 Аватар для Olivеr
411 / 407 / 13
Регистрация: 06.10.2011
Сообщений: 830
22.04.2013, 21:45     Комбинаторика на С++ #13
Цитата Сообщение от gorus95 Посмотреть сообщение
если например k = 3 тогда 123, 124, 234
вообще то будет
123
124
134
234

вот мой код. хреновый, конечно, но для понимания подойдет. принцип как написал Buckstabue
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
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
bool increase(vector<int> &vec, const int n)
{
    for (vector<int>::reverse_iterator it = vec.rbegin(); it != vec.rend(); it++)
        if (*it + 1 <= n && find(vec.begin(), vec.end(), *it + 1)==vec.end()  ) {
            ++*it;
            return true;
        }
    return false;
}
 
void print(const vector<int> &vec)
{
    for (size_t i = 0; i != vec.size(); i++)
        cout << vec[i] << " ";
    cout << endl;
}
 
int main()
{
    setlocale(LC_CTYPE, "");
    // сочетания из n по k без повторений
    int n = 5;
    int k = 3;
    vector<int> vec(k);
    for (size_t i = 0; i != n; i++)
        vec[i] = i + 1;
    print(vec);
 
    while (increase(vec, n) )
        print(vec);
 
    return 0;
}
gorus95
5 / 5 / 1
Регистрация: 22.12.2012
Сообщений: 145
22.04.2013, 21:47  [ТС]     Комбинаторика на С++ #14
можно бы сделать через цикл в цикле, но опять же, если k = 5 или 10 то надо будет столько же циклов в цикле..

Добавлено через 1 минуту
Olivеr, сейчас посмотрю
а можно как-то сделать без векторов и алгоритмов?
Olivеr
 Аватар для Olivеr
411 / 407 / 13
Регистрация: 06.10.2011
Сообщений: 830
22.04.2013, 21:48     Комбинаторика на С++ #15
не смотрите, код неправильно работает, щас попробую исправить
Байт
 Аватар для Байт
13985 / 8816 / 1229
Регистрация: 24.12.2010
Сообщений: 15,972
22.04.2013, 21:55     Комбинаторика на С++ #16
Цитата Сообщение от gorus95 Посмотреть сообщение
наткнулся на идею
Идея, конечно, симпатичная, но крайне не эффективная. Вы предлагаете рассматривать все kn комбинаций, выбрасывая из них те, которые не являются сочетаниями, т.е. содержат повторы. Сочетаний-то в самом деле, значительно меньше.
И я толком не понимаю, что вам мешает пройтись по ссылочкам, приведенным в посте #8. Там алгоритмы в несколько строчек.
gorus95
5 / 5 / 1
Регистрация: 22.12.2012
Сообщений: 145
22.04.2013, 22:03  [ТС]     Комбинаторика на С++ #17
Байт, не совсем понимаю как работать с теми алгоритмами, т.к. с <vector> и <algorithm> работать пока не умею
Olivеr
 Аватар для Olivеr
411 / 407 / 13
Регистрация: 06.10.2011
Сообщений: 830
22.04.2013, 22:35     Комбинаторика на С++ #18
gorus95, вот рабочий код
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
41
42
43
44
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
bool increase(vector<int> &vec, const int n)
{
    for (int i = vec.size() - 1; i >= 0; i--)
        if ( vec[i] + 1 <= n && find(vec.begin() + i + 1, vec.end(), vec[i] + 1) == vec.end() ) {
                ++vec[i];
 
            for (int j = i + 1; j < vec.size(); j++)
                vec[j] = vec[j - 1] + 1;
            return true;
        }
    return false;
}
 
void print(const vector<int> &vec)
{
    for (size_t i = 0; i != vec.size(); i++)
        cout << vec[i] << " ";
    cout << endl;
}
 
int main()
{
    setlocale(LC_CTYPE, "");
    // сочетания из n по k без повторений
    int n = 6;
    int k = 4;
    vector<int> vec(k);
    for (size_t i = 0; i != n; i++)
        vec[i] = i + 1;
 
 
    print(vec);
 
    while (increase(vec, n) )
        print(vec);
 
    return 0;
}
gorus95
5 / 5 / 1
Регистрация: 22.12.2012
Сообщений: 145
22.04.2013, 22:39  [ТС]     Комбинаторика на С++ #19
Olivеr, спасибо
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.04.2013, 22:57     Комбинаторика на С++
Еще ссылки по теме:

Комбинаторика C++
C++ Комбинаторика. Сочетания
Покерная комбинаторика C++

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

Или воспользуйтесь поиском по форуму:
Olivеr
 Аватар для Olivеr
411 / 407 / 13
Регистрация: 06.10.2011
Сообщений: 830
22.04.2013, 22:57     Комбинаторика на С++ #20
gorus95, вот Вам без алгоритмов:
Кликните здесь для просмотра всего текста
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
41
42
43
44
#include <iostream>
#include <vector>
 
using namespace std;
 
bool increase(vector<int> &vec, const int n)
{
    for (int i = vec.size() - 1; i >= 0; i--)
        if ( vec[i] + 1 <= n ) {
            if ( i != vec.size() - 1 && vec[i + 1] == vec[i] + 1 )
                continue;
            ++vec[i];
 
            for (int j = i + 1; j < vec.size(); j++)
                vec[j] = vec[j - 1] + 1;
            return true;
        }
    return false;
}
 
void print(const vector<int> &vec)
{
    for (size_t i = 0; i != vec.size(); i++)
        cout << vec[i] << " ";
    cout << endl;
}
 
int main()
{
    setlocale(LC_CTYPE, "");
    // сочетания из n по k без повторений
    int n = 10;
    int k = 8;
    vector<int> vec(k);
    for (size_t i = 0; i != k; i++)
        vec[i] = i + 1;
 
    print(vec);
 
    while (increase(vec, n) )
        print(vec);
 
    return 0;
}
Yandex
Объявления
22.04.2013, 22:57     Комбинаторика на С++
Ответ Создать тему
Опции темы

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