Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 21, средняя оценка - 4.67
deadstrike
0 / 0 / 0
Регистрация: 14.05.2012
Сообщений: 28
#1

Реализация комбинаторики - C++

02.08.2012, 21:36. Просмотров 2869. Ответов 26
Метки нет (Все метки)

Задача имеет следующий вид.
Есть набор строка символов неопределенной(заранее) длины.
Нужно из данной строки подсчитать и вывести все варианты возможных комбинаций от одного символа и до length(str).
Подсчитать кол-во вариантов не проблема (http://www.cyberforum.ru/cgi-bin/latex.cgi?\sum_{i=0}^{length}\frac{length!}{i!*(length-i)!}) - проблема в переборе все возможных вариантов.
Прошу помочь с алгоритмом.

Используется C++. (подпись: Кэп)

P.S. приветствуются ссылки на любые статьи сродные данной теме.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.08.2012, 21:36
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Реализация комбинаторики (C++):

Элементы Комбинаторики - C++
Даны натуральные числа a1,...a10. Предположим что имеется 10 монет достоинством a1,...,a10. Обозначим через bk число способов, которыми...

Функция комбинаторики.... - C++
Помогите написать программу, вычисляющую C(n,k)=n!/(k!*(n-k)!), где 1<=N,K,<=500...

Работа с формулами комбинаторики - C++
Совершенно не представляю как это сделать, но нужно очень. Если кому по силам ... :cry: - Разработать класс для работы с формулами...

Реализовать рекурсивно алгоритм комбинаторики - C++
Всем привет! Хотелось бы реализовать рекурсивно следующий алгоритм комбинаторики: Ввод: abcd Вывод: abcd abc d ab cd

написать программу разгадки числового ребуса С++ из раздела комбинаторики - C++
требуется написать программу разгадки ребуса на с++ без использования вложенных циклов пчелка * 7 = жжжжжж это из комбинаторики,...

Реализация - C++
Кто может помочь с одним моментом в курсовике , курсовик сделан почти весь, но там буквально 5-7 строчек кода нужно чтобы всё заработало. ...

26
Avazart
Эксперт С++
7246 / 5418 / 297
Регистрация: 10.12.2010
Сообщений: 24,042
Записей в блоге: 17
04.08.2012, 22:24 #16
Я привел и алгоритм, коментарии в коде...
0
alkagolik
Заблокирован
04.08.2012, 22:40 #17
Цитата Сообщение от Hi4ko Посмотреть сообщение
Никакой математики, чистый перебор.
правильно. Долой логарифмы!
Цитата Сообщение от deadstrike Посмотреть сообщение
alkagolik, Я тебя чуток не понял...
да я как бы тоже не особо тебя понял...
0
Hi4ko
74 / 74 / 4
Регистрация: 21.10.2010
Сообщений: 376
04.08.2012, 23:05 #18
Цитата Сообщение от alkagolik Посмотреть сообщение
правильно. Долой логарифмы!

http://www.cyberforum.ru/cgi-bin/latex.cgi?2^n тоже не логарифм, хоть и быстрее http://www.cyberforum.ru/cgi-bin/latex.cgi?n^3 , согласен)
0
kravam
быдлокодер
1700 / 887 / 45
Регистрация: 04.06.2008
Сообщений: 5,498
05.08.2012, 09:53 #19
Немножко теории. Итак, тебе надо Получить Сочетаний Из N по K Без Возврата И Без Учёта Порядка

Существует специальный класс, вот такой (ниже имя класса и аргументы)
P_s_i_n_p_k_b_v_i_s_u_p (контейнер "hello", пресловутое k ( в нашем случае 1, 2, 3 или 4 ))

Ну всё, Объявляешь объект этого класса и... выводишь. Проще пареной репы
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
#include "kombinatorika.h"
#include <windows.h>
#include <iterator>
 
int main () {
 SetConsoleCP (1251);
 SetConsoleOutputCP (1251);
 
 //Исходный вектор, скропай его сам (можно "hello", но что-то мне подсказывает, 
 //что так будет правильнее)                                                    
 string hello ("helo");
 vector<char> vec (hello.begin(), hello.end());
 
 
 //ВЕктор- результат                                                            
  vector<char> rez; 
 int k= 0;
 
 //В цикле делаем                                                               
 for (int i= 0; i< 4; i++) {
 
  //ОБъявляем объект упомянутого класса                                         
  //АРгумент такие: vector "helo" и число 1 (увеличивается в цикле; потом будет 
  //2 и т. д.)                                                                  
  P_s_i_n_p_k_b_v_i_s_u_p<char, vector> P_s_i_n_p_k_b_v_i_s_u_p_l (vec, i+ 1);
 
  //Пока есть очередное сочетание...                                            
  while (P_s_i_n_p_k_b_v_i_s_u_p_l.och_rez()) {
       rez= P_s_i_n_p_k_b_v_i_s_u_p_l.rez();  
  //   ВЫвододим!                                                               
       copy (rez.begin(), rez.end(), ostream_iterator<char>(cout, ""));
       cout<< endl;
  }
 }
 
 getchar ();
 return 0;
}
                                        //+
                                        //+
                                        //+
                                        //+
                                        //+
Подобным образом реализовано получение всех сочетаний с возвратом, без возврата с учётом порядка и без учёта порядка. Работает с вектором, списком, очередями. Со строками не работает, но есть исходник при желании можно подправить.
0
Avazart
Эксперт С++
7246 / 5418 / 297
Регистрация: 10.12.2010
Сообщений: 24,042
Записей в блоге: 17
05.08.2012, 12:04 #20
alkagolik, думаю при проходе по булеану не делается ли лишних перестановок?
0
alkagolik
Заблокирован
05.08.2012, 15:48 #21
Avazart, это смотря с какой стороны посмотреть. Постановка задачи до сих пор не точная.
Цитата Сообщение от deadstrike Посмотреть сообщение
Нужно из данной строки подсчитать и вывести все варианты возможных комбинаций от одного символа и до length(str)
что значит все варианты для входной строки "aaa"? Если смотреть по номиналу то "все варианты" представлены тремя способами "aaa", "aa", "a", а если по порядку размещений, то все гораздо сложнее. "Всех вариантов" строки "aaa" будет 3! * 1+ 2! * 3 + 1! * 3 + 0! * 1 = 16 включая пустое подмножество.
Я предположил второй вариант.
1
Avazart
Эксперт С++
7246 / 5418 / 297
Регистрация: 10.12.2010
Сообщений: 24,042
Записей в блоге: 17
05.08.2012, 15:57 #22
Я не про это...

Немогу понять что затратне?
Делать перестаноки с каждым элемнетом булеана (как вы предложили), или укарачивать полученое множество !length перестановок и удалять повторения (как делал я) ?
0
b_kasenov47
14 / 14 / 1
Регистрация: 28.07.2012
Сообщений: 57
06.08.2012, 11:56 #23
Вроде так:
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
#include <iostream>
#include <string>
#include <algorithm>
 
using namespace std;
 
string s;
 
int len; // dlina stroki
 
string get_by_mask(int n) //funkciya dlya polucheniya stroki po maske
{
    string ans;
    for (int i = 0; i < len; i++)
        if ((n & (1 << i)) > 0)
            ans += s[i];
    return ans;
}
 
int main()
{
    cin >> s;
    len = s.length();
    for (int i = 0; i < (1 << len); i++)
        {
            string str = get_by_mask(i);
            sort(str.begin(), str.end());
            do
                {
                    cout << str << endl;
                }
            while (next_permutation(str.begin(), str.end()));
        }
    return 0;
}
Добавлено через 1 минуту
При этом длина строки должна быть не больше 32. Если надо больше - ставим long long

Добавлено через 48 секунд
При этом длина строки должна быть не больше 32. Если надо больше - ставим long long
0
alkagolik
Заблокирован
06.08.2012, 18:01 #24
Цитата Сообщение от kravam Посмотреть сообщение
P_s_i_n_p_k_b_v_i_s_u_p
мужественный ты мужик ,интересно как ты обозвал свои dll.
Цитата Сообщение от Avazart Посмотреть сообщение
Немогу понять что затратне?
ничего не могу сказать, я твой код не смотрел. Тем более что я как таковой алгоритм не предлагал, а лишь разжевал задачу на подзадачи. Найти булеан (все сочетания из n по k от k = n и до k = 0) тоже разными методами можно.
0
deadstrike
0 / 0 / 0
Регистрация: 14.05.2012
Сообщений: 28
06.08.2012, 19:49  [ТС] #25
Цитата Сообщение от alkagolik Посмотреть сообщение
Avazart, это смотря с какой стороны посмотреть. Постановка задачи до сих пор не точная.
Цитата Сообщение от deadstrike Посмотреть сообщение
Нужно из данной строки подсчитать и вывести все варианты возможных комбинаций от одного символа и до length(str)
что значит все варианты для входной строки "aaa"? Если смотреть по номиналу то "все варианты" представлены тремя способами "aaa", "aa", "a", а если по порядку размещений, то все гораздо сложнее. "Всех вариантов" строки "aaa" будет 3! * 1+ 2! * 3 + 1! * 3 + 0! * 1 = 16 включая пустое подмножество.
Я предположил второй вариант.
Включая также сторки и "ааа", тоесть в строке s="Hello" два из всех вариантов будут "ll" и "ll", где первое "ll" это s[3]+s[4], а второе "ll" s[4]+s[3].
0
b_kasenov47
14 / 14 / 1
Регистрация: 28.07.2012
Сообщений: 57
06.08.2012, 22:00 #26
Мне кажется мой вариант вполне себе работает. Если поставить счетчик, то можно и количество этих подстрок подсчиать.
0
Avazart
Эксперт С++
7246 / 5418 / 297
Регистрация: 10.12.2010
Сообщений: 24,042
Записей в блоге: 17
06.08.2012, 23:27 #27
C++
1
std::next_permutation()
Как уже заметели не совсем подходит, нужно свою ф-цию писать.
0
06.08.2012, 23:27
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.08.2012, 23:27
Привет! Вот еще темы с ответами:

Реализация k-стеков - C++
Добрый день! Никак не могу найти информацию по реализации k-стеков. Задача состоит в следующем: 1. описать объектовый тип стек и взять...

Реализация формулы - C++
Формула: M=b(a^x)^-1 mod 11 Реализация __int64 T = fmod(b*pow(pow(a,x),-1),11); выдаёт 0, где ошибся?

реализация предикатов - C++
Народ! Кто-нибудь знает какие-нибудь средства для реализации(удобного создания и хранения) предикатов ??? Те какие-нибудь открытые...

Реализация класса - C++
Спроектировать и реализовать класс BigInt, позволяющий хранить целые числа в диапазоне , и производить набор основных операций с ними. ...


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

Или воспользуйтесь поиском по форуму:
27
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru