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

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

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

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

P.S. приветствуются ссылки на любые статьи сродные данной теме.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.08.2012, 21:36     Реализация комбинаторики
Посмотрите здесь:

C++ Функция комбинаторики....
C++ реализация cat в с++
C++ Реализация стека
C++ Реализация
C++ Реализовать рекурсивно алгоритм комбинаторики
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
05.08.2012, 15:48     Реализация комбинаторики #21
Avazart, это смотря с какой стороны посмотреть. Постановка задачи до сих пор не точная.
Цитата Сообщение от deadstrike Посмотреть сообщение
Нужно из данной строки подсчитать и вывести все варианты возможных комбинаций от одного символа и до length(str)
что значит все варианты для входной строки "aaa"? Если смотреть по номиналу то "все варианты" представлены тремя способами "aaa", "aa", "a", а если по порядку размещений, то все гораздо сложнее. "Всех вариантов" строки "aaa" будет 3! * 1+ 2! * 3 + 1! * 3 + 0! * 1 = 16 включая пустое подмножество.
Я предположил второй вариант.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Avazart
 Аватар для Avazart
6912 / 5152 / 254
Регистрация: 10.12.2010
Сообщений: 22,660
Записей в блоге: 17
05.08.2012, 15:57     Реализация комбинаторики #22
Я не про это...

Немогу понять что затратне?
Делать перестаноки с каждым элемнетом булеана (как вы предложили), или укарачивать полученое множество !length перестановок и удалять повторения (как делал я) ?
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
alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
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) тоже разными методами можно.
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].
b_kasenov47
14 / 14 / 1
Регистрация: 28.07.2012
Сообщений: 57
06.08.2012, 22:00     Реализация комбинаторики #26
Мне кажется мой вариант вполне себе работает. Если поставить счетчик, то можно и количество этих подстрок подсчиать.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.08.2012, 23:27     Реализация комбинаторики
Еще ссылки по теме:

Реализация стека C++
C++ Элементы Комбинаторики
C++ Работа с формулами комбинаторики

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

Или воспользуйтесь поиском по форуму:
Avazart
 Аватар для Avazart
6912 / 5152 / 254
Регистрация: 10.12.2010
Сообщений: 22,660
Записей в блоге: 17
06.08.2012, 23:27     Реализация комбинаторики #27
C++
1
std::next_permutation()
Как уже заметели не совсем подходит, нужно свою ф-цию писать.
Yandex
Объявления
06.08.2012, 23:27     Реализация комбинаторики
Ответ Создать тему
Опции темы

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