Форум программистов, компьютерный форум 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++ Реализовать рекурсивно алгоритм комбинаторики
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Avazart
 Аватар для Avazart
6905 / 5145 / 253
Регистрация: 10.12.2010
Сообщений: 22,634
Записей в блоге: 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
 Аватар для Avazart
6905 / 5145 / 253
Регистрация: 10.12.2010
Сообщений: 22,634
Записей в блоге: 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
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
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
 Аватар для Avazart
6905 / 5145 / 253
Регистрация: 10.12.2010
Сообщений: 22,634
Записей в блоге: 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
 Аватар для Avazart
6905 / 5145 / 253
Регистрация: 10.12.2010
Сообщений: 22,634
Записей в блоге: 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
 Аватар для Avazart
6905 / 5145 / 253
Регистрация: 10.12.2010
Сообщений: 22,634
Записей в блоге: 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" считается у меня за одну комбинацию)
а в чём у меня тогда ошибка?
deadstrike
0 / 0 / 0
Регистрация: 14.05.2012
Сообщений: 28
04.08.2012, 22:21  [ТС]     Реализация комбинаторики #15
Avazart, Hi4ko, Спасибо большое. Однако, немного комментариев лишними бы не были. =)
alkagolik, Я тебя чуток не понял...

Не по теме:

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

Avazart
 Аватар для Avazart
6905 / 5145 / 253
Регистрация: 10.12.2010
Сообщений: 22,634
Записей в блоге: 17
04.08.2012, 22:24     Реализация комбинаторики #16
Я привел и алгоритм, коментарии в коде...
alkagolik
 Аватар для alkagolik
1510 / 616 / 79
Регистрация: 15.07.2011
Сообщений: 3,552
04.08.2012, 22:40     Реализация комбинаторики #17
Цитата Сообщение от Hi4ko Посмотреть сообщение
Никакой математики, чистый перебор.
правильно. Долой логарифмы!
Цитата Сообщение от deadstrike Посмотреть сообщение
alkagolik, Я тебя чуток не понял...
да я как бы тоже не особо тебя понял...
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 , согласен)
kravam
быдлокодер
 Аватар для kravam
1512 / 872 / 44
Регистрация: 04.06.2008
Сообщений: 5,271
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;
}
                                        //+
                                        //+
                                        //+
                                        //+
                                        //+
Подобным образом реализовано получение всех сочетаний с возвратом, без возврата с учётом порядка и без учёта порядка. Работает с вектором, списком, очередями. Со строками не работает, но есть исходник при желании можно подправить.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.08.2012, 12:04     Реализация комбинаторики
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
Avazart
 Аватар для Avazart
6905 / 5145 / 253
Регистрация: 10.12.2010
Сообщений: 22,634
Записей в блоге: 17
05.08.2012, 12:04     Реализация комбинаторики #20
alkagolik, думаю при проходе по булеану не делается ли лишних перестановок?
Yandex
Объявления
05.08.2012, 12:04     Реализация комбинаторики
Ответ Создать тему
Опции темы

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