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

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

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

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

02.08.2012, 21:36. Просмотров 2835. Ответов 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
Нарушитель
Эксперт С++
7232 / 5404 / 293
Регистрация: 10.12.2010
Сообщений: 23,956
Записей в блоге: 17
02.08.2012, 21:48 #2
А в чем собственно проблема? Бери и перебирай....

Добавлено через 3 минуты
В помощь:
http://www.cplusplus.com/reference/algorithm/next_permutation/
http://www.cplusplus.com/reference/algorithm/prev_permutation/
0
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.)
В этом вся сложность для меня...

Напишите пожалуйста кусок кода если не тяжело.
0
Avazart
Нарушитель
Эксперт С++
7232 / 5404 / 293
Регистрация: 10.12.2010
Сообщений: 23,956
Записей в блоге: 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;
}
0
deadstrike
0 / 0 / 0
Регистрация: 14.05.2012
Сообщений: 28
02.08.2012, 22:19  [ТС] #5
см. пост выше (редаг.)
0
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> и т.д.
1
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"
1
Миниатюры
Реализация комбинаторики  
Avazart
Нарушитель
Эксперт С++
7232 / 5404 / 293
Регистрация: 10.12.2010
Сообщений: 23,956
Записей в блоге: 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
Для продолжения нажмите любую клавишу . . .
1
kravam
04.08.2012, 04:58
  #9

Не по теме:

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

0
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 ответ такой же
0
Avazart
Нарушитель
Эксперт С++
7232 / 5404 / 293
Регистрация: 10.12.2010
Сообщений: 23,956
Записей в блоге: 17
04.08.2012, 12:38 #11
Попробуйте больше символов например "hello"
0
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
0
Avazart
Нарушитель
Эксперт С++
7232 / 5404 / 293
Регистрация: 10.12.2010
Сообщений: 23,956
Записей в блоге: 17
04.08.2012, 12:49 #13
У меня выдает 170 комбинаций (учитывая еще то что "L" считается у меня за одну комбинацию)
0
Hi4ko
74 / 74 / 4
Регистрация: 21.10.2010
Сообщений: 376
04.08.2012, 13:03 #14
Цитата Сообщение от Avazart Посмотреть сообщение
У меня выдает 170 комбинаций (учитывая еще то что "L" считается у меня за одну комбинацию)
а в чём у меня тогда ошибка?
0
deadstrike
0 / 0 / 0
Регистрация: 14.05.2012
Сообщений: 28
04.08.2012, 22:21  [ТС] #15
Avazart, Hi4ko, Спасибо большое. Однако, немного комментариев лишними бы не были. =)
alkagolik, Я тебя чуток не понял...

Не по теме:

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

0
04.08.2012, 22:21
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.08.2012, 22:21
Привет! Вот еще темы с ответами:

Реализация 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, позволяющий хранить целые числа в диапазоне , и производить набор основных операций с ними. ...


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

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

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