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

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

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

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

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

Задача имеет следующий вид.
Есть набор строка символов неопределенной(заранее) длины.
Нужно из данной строки подсчитать и вывести все варианты возможных комбинаций от одного символа и до 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++
Даны натуральные числа 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++
Кто может помочь с одним моментом в курсовике , курсовик сделан почти весь, но там буквально 5-7 строчек кода нужно чтобы всё заработало. ...

Реализация семафоров - C++
Возможно ли реализовать семафоры вручную или же для этого нужна обязательная поддержка процессора?

Реализация класса - C++
Помогите понять пожалуйста. Пример из Дейтела: #include "stdafx.h" #include <iostream> #include "GradeBook.h" using namespace...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Avazart
Эксперт С++
7117 / 5294 / 273
Регистрация: 10.12.2010
Сообщений: 23,413
Записей в блоге: 17
02.08.2012, 21:48     Реализация комбинаторики #2
А в чем собственно проблема? Бери и перебирай....

Добавлено через 3 минуты
В помощь:
http://www.cplusplus.com/reference/a...t_permutation/
http://www.cplusplus.com/reference/a...v_permutation/
deadstrike
0 / 0 / 0
Регистрация: 14.05.2012
Сообщений: 28
02.08.2012, 21:49  [ТС]     Реализация комбинаторики #3
А вы хороши =)
Как перебрать все варианты?! Я не могу придумать алгоритм который это будет делать...
Приведенная выше ссылка. дает перестановку от n-го и до k-го. А моя задача имеет следующую особенность

допустим есть строка "Hello". Надо все комбинации по два элемента (1-го и 2-го, 1-го и 3-го, 1-го и 4-го, 2-го и 5-го, 2-го и 3-го, 2-го и 4-го и т.д.),
потом по три(1,2,3 ; 1,2,4 ; 1,2,5 ; 2,3,4 etc.)
В этом вся сложность для меня...

Напишите пожалуйста кусок кода если не тяжело.
Avazart
Эксперт С++
7117 / 5294 / 273
Регистрация: 10.12.2010
Сообщений: 23,413
Записей в блоге: 17
02.08.2012, 22:02     Реализация комбинаторики #4
Наброском так нужно еще исключаемый элемент перебирать
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int main()
{
system("chcp 1251");
using namespace std;
 
string s="б#$%&ь";
//getline(cin,s);
while(!s.empty() )
 {
  do { cout << s << endl; }
  while ( next_permutation (s.begin(),s.end()) );
  s.erase(s.begin() );
 }
 
system("pause");
return 0;
}
deadstrike
0 / 0 / 0
Регистрация: 14.05.2012
Сообщений: 28
02.08.2012, 22:19  [ТС]     Реализация комбинаторики #5
см. пост выше (редаг.)
alkagolik
Заблокирован
03.08.2012, 07:52     Реализация комбинаторики #6
deadstrike, писать код не буду, он получится большим. А что делать - разложу по полочкам. Итак:
1. булеан. Это множество подмножеств множества. если у тебя множество мощностью n, то всех его подмножеств, включая пустое подмножество и его самого будет http://www.cyberforum.ru/cgi-bin/latex.cgi?2^{n}. Это как бы намекает на сложность программы если не ограничиваться встроенными типами, и наоборот на ограниченность, если все таки ограничиться встроенными типами. Но это еще цветочки. Задача №1 - получить булеан множества, мощностью n и поместить его в двумерный массив (или файел).
как найти булеан
Bash
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
45
46
47
indicator@pc-host:~$ cat test.cc
#include <iostream>
 
void boolean( int* a, int k ) {
 
    int m = 1 << k, i = 0, j;
    
    while ( i < m ) {
        
        j = 0;
        while ( j < k ) {
            if ( i & (1 << j) )
                std::cout << a[ j ] << ' ';
            ++j;
        }
        std::cout << std::endl;
        ++i;
    }
 
}
 
int main() {
    
    int a[] = { 0, 3, 5, 8 };
    
    boolean( a, 4 );
    return 0;
}
indicator@pc-host:~$ g++ test.cc
indicator@pc-host:~$ ./a.out 
 
0 
3 
0 3 
5 
0 5 
3 5 
0 3 5 
8 
0 8 
3 8 
0 3 8 
5 8 
0 5 8 
3 5 8 
0 3 5 8 
indicator@pc-host:~$

2. размещения, перестановки. Число всех перестановок порядка n равно n!, вот тебе и ягодки. После того как мы нашли булеан и (к примеру пока будем полагать что все множества в двумерном массиве) поместили его в двумерный массив. (т.к. длины массивов разные, то можно в нулевом элементе массива array[ i ][ 0 ] указывать его длину, а после уже плясать из первого элемента array[ i ][ 1 ]). Теперь мы создаем цикл от i = 0 и до http://www.cyberforum.ru/cgi-bin/latex.cgi?2^{n} и начинаем осуществлять перестановки массива &array[ i ][ 1 ] с размером array[ i ][ 0 ]. Функций перестановки на форуме море. Указанная стандартная функция не подходит, т.к. она рассчитана на перестановки без повторений, но в сети полно валяется алгоритмов и исходных текстов, так что удачи.

З.Ы. из поста #3 я понял что номинальные значения символов в расчет не берутся, т.е. если множеству {a,a,a,a} поставить в соответствие множество {0, 1, 2, 3}, то надо найти все размещения <0, 1, 2, 3>, <0, 1, 3, 2> и т.д.
Hi4ko
74 / 74 / 4
Регистрация: 21.10.2010
Сообщений: 376
03.08.2012, 09:02     Реализация комбинаторики #7
Никакой математики, чистый перебор.

Сложность: вроде http://www.cyberforum.ru/cgi-bin/latex.cgi?O(s.length^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
29
30
31
32
33
34
35
36
37
#include <iostream>
#include <string>
#include <vector>
 
using namespace std;
 
int main(){
    string s;
    cin >> s;
    vector< vector<string> > ans(s.length());
    for(int i = 0; i < ans.size(); ++i){
        if(i == 0){
            for(int j = 0; j < s.length() - i; ++j){
                string t(s.substr(j,1));
                ans[i].push_back(t);
            }
        }
        else{
            for(int j = 0; j < s.length() - i; ++j){
                string t = s.substr(j,i);
                for(int z = j + i; z < s.length(); ++z){
                    t.append(s.substr(z,1));
                    ans[i].push_back(t);
                    t.erase(t.length() - 1, 1);
                }
            }
        }
    }
    int a = 0;
    for(int i =0; i < ans.size(); ++i)
        a += ans[i].size();
    for(int i = 0; i < ans.size(); ++i)
        for(int j = 0; j < ans[i].size(); ++j)
            cout << ans[i][j] << endl;
    cout << endl;
    cout << a << endl;
}
Во вложении вывод на строку "hello"
Миниатюры
Реализация комбинаторики  
Avazart
Эксперт С++
7117 / 5294 / 273
Регистрация: 10.12.2010
Сообщений: 23,413
Записей в блоге: 17
03.08.2012, 23:28     Реализация комбинаторики #8
Цитата Сообщение от Hi4ko Посмотреть сообщение
Во вложении вывод на строку "hello"
Думаю там не все комбинации получены.

1. Получить все перестановки с максимальной длиной исходной строки
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
29
30
31
32
33
int main()
{
system("chcp 1251");
using namespace std;
 
string s="123";
//getline(cin,s); // Ввод
 
vector<string> c;
// Получение возможных перестановок
sort(s.begin(),s.end() );
do {  c.push_back(s); }
while ( next_permutation (s.begin(),s.end()) );
 
vector<string> buf(c);
 
while(buf.back().size()>1)
 {
  // "Укорачивание строк"
  for(size_t i=0; i<buf.size(); i++)  buf[i].erase(buf[i].end()-1 );
  // Удаление одинаковых комбинаций
  sort(buf.begin(),buf.end() );
  buf.erase(unique(buf.begin(),buf.end()),buf.end() );
  // добавляем
  copy(buf.begin(),buf.end(),back_inserter(c) );
 }
//  Вывод
copy(c.begin(),c.end(),ostream_iterator<string>(cout,"\n"));
 
system("pause");
return 0;
}
//---------------------------------------------------------------------------
Вывод:
Код
Текущая кодовая страница: 1251
123
132
213
231
312
321
12
13
21
23
31
32
1
2
3
Для продолжения нажмите любую клавишу . . .
kravam
04.08.2012, 04:58
  #9

Не по теме:

Я-то уж думал запрос действительно на реализацию... У меня такой класс есть охренительный..

Hi4ko
74 / 74 / 4
Регистрация: 21.10.2010
Сообщений: 376
04.08.2012, 12:36     Реализация комбинаторики #10
Цитата Сообщение от Avazart Посмотреть сообщение
Думаю там не все комбинации получены.
Вы правы:
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
45
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
bool comp(char s1,char s2){
    return s1> s2;
}
 
int main(){
    string s;
    cin >> s;
    vector< vector<string> > ans(s.length());
    for(int i = 0; i < ans.size(); ++i){
        if(i == 0){
            for(int j = 0; j < s.length() - i; ++j){
                string t(s.substr(j,1));
                ans[i].push_back(t);
            }
        }
        else{
            for(int j = 0; j < s.length() - i; ++j){
                string t = s.substr(j,i);
                for(int z = j + i; z < s.length(); ++z){
                    t.append(s.substr(z,1));
                    string lol = t;
                    sort(lol.begin(),lol.end());
                    do {  ans[i].push_back(lol); }
                    while ( next_permutation (lol.begin(),lol.end()) );
                    t.erase(t.length() - 1, 1);
                }
            }
        }
    }
    int a = 0;
    for(int i =0; i < ans.size(); ++i)
        a += ans[i].size();
    for(int i = 0; i < ans.size(); ++i)
        for(int j = 0; j < ans[i].size(); ++j)
            cout << ans[i][j] << endl;
    cout << endl;
    cout << a << endl;
}
на 123 ответ такой же
Avazart
Эксперт С++
7117 / 5294 / 273
Регистрация: 10.12.2010
Сообщений: 23,413
Записей в блоге: 17
04.08.2012, 12:38     Реализация комбинаторики #11
Попробуйте больше символов например "hello"
Hi4ko
74 / 74 / 4
Регистрация: 21.10.2010
Сообщений: 376
04.08.2012, 12:42     Реализация комбинаторики #12
Цитата Сообщение от Avazart Посмотреть сообщение
Попробуйте больше символов например "hello"

вывод
Код
h
e
l
l
o
eh
he
hl
lh
hl
lh
ho
oh
el
le
el
le
eo
oe
ll
lo
ol
lo
ol
ehl
elh
hel
hle
leh
lhe
ehl
elh
hel
hle
leh
lhe
eho
eoh
heo
hoe
oeh
ohe
ell
lel
lle
elo
eol
leo
loe
oel
ole
llo
lol
oll
ehll
elhl
ellh
hell
hlel
hlle
lehl
lelh
lhel
lhle
lleh
llhe
ehlo
ehol
elho
eloh
eohl
eolh
helo
heol
hleo
hloe
hoel
hole
leho
leoh
lheo
lhoe
loeh
lohe
oehl
oelh
ohel
ohle
oleh
olhe
ello
elol
eoll
lelo
leol
lleo
lloe
loel
lole
oell
olel
olle
ehllo
ehlol
eholl
elhlo
elhol
ellho
elloh
elohl
elolh
eohll
eolhl
eollh
hello
helol
heoll
hlelo
hleol
hlleo
hlloe
hloel
hlole
hoell
holel
holle
lehlo
lehol
lelho
leloh
leohl
leolh
lhelo
lheol
lhleo
lhloe
lhoel
lhole
lleho
lleoh
llheo
llhoe
lloeh
llohe
loehl
loelh
lohel
lohle
loleh
lolhe
oehll
oelhl
oellh
ohell
ohlel
ohlle
olehl
olelh
olhel
olhle
olleh
ollhe

162
Avazart
Эксперт С++
7117 / 5294 / 273
Регистрация: 10.12.2010
Сообщений: 23,413
Записей в блоге: 17
04.08.2012, 12:49     Реализация комбинаторики #13
У меня выдает 170 комбинаций (учитывая еще то что "L" считается у меня за одну комбинацию)
Hi4ko
74 / 74 / 4
Регистрация: 21.10.2010
Сообщений: 376
04.08.2012, 13:03     Реализация комбинаторики #14
Цитата Сообщение от Avazart Посмотреть сообщение
У меня выдает 170 комбинаций (учитывая еще то что "L" считается у меня за одну комбинацию)
а в чём у меня тогда ошибка?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.08.2012, 22:21     Реализация комбинаторики
Еще ссылки по теме:

реализация цикла for - C++
Здравствуйте, как посчитать сумму чисел в цикле for от числа А до B... никак не могу понять как это реализовать... И еще один вопрос,...

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

Реализация MD5 ? - C++
Помогите найти реализацию MD5 хеширование на C++ или C# (или если у кого нибудь уже есть исходники, то пожалуйста скиньте ссылку на...

Реализация стека - C++
Всем доброго времени суток! Нашел в на просторах интернета исходник реализации стека. Но не совсем понятен код. Что бы понять - я...

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


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

Или воспользуйтесь поиском по форуму:
deadstrike
0 / 0 / 0
Регистрация: 14.05.2012
Сообщений: 28
04.08.2012, 22:21  [ТС]     Реализация комбинаторики #15
Avazart, Hi4ko, Спасибо большое. Однако, немного комментариев лишними бы не были. =)
alkagolik, Я тебя чуток не понял...

Не по теме:

kravam, А можешь дать посмотреть?

Yandex
Объявления
04.08.2012, 22:21     Реализация комбинаторики
Ответ Создать тему
Опции темы

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