Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.89/55: Рейтинг темы: голосов - 55, средняя оценка - 4.89
0 / 0 / 2
Регистрация: 14.05.2012
Сообщений: 28

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

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

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

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

P.S. приветствуются ссылки на любые статьи сродные данной теме.
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
02.08.2012, 21:36
Ответы с готовыми решениями:

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

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

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

26
Эксперт С++
 Аватар для Avazart
8488 / 6155 / 615
Регистрация: 10.12.2010
Сообщений: 28,683
Записей в блоге: 30
02.08.2012, 21:48
А в чем собственно проблема? Бери и перебирай....

Добавлено через 3 минуты
В помощь:
http://www.cplusplus.com/refer... rmutation/
http://www.cplusplus.com/refer... rmutation/
0
0 / 0 / 2
Регистрация: 14.05.2012
Сообщений: 28
02.08.2012, 21:49  [ТС]
А вы хороши =)
Как перебрать все варианты?! Я не могу придумать алгоритм который это будет делать...
Приведенная выше ссылка. дает перестановку от 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
8488 / 6155 / 615
Регистрация: 10.12.2010
Сообщений: 28,683
Записей в блоге: 30
02.08.2012, 22:02
Наброском так нужно еще исключаемый элемент перебирать
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
0 / 0 / 2
Регистрация: 14.05.2012
Сообщений: 28
02.08.2012, 22:19  [ТС]
см. пост выше (редаг.)
0
 Аватар для alkagolik
1599 / 622 / 113
Регистрация: 15.07.2011
Сообщений: 3,548
03.08.2012, 07:52
deadstrike, писать код не буду, он получится большим. А что делать - разложу по полочкам. Итак:
1. булеан. Это множество подмножеств множества. если у тебя множество мощностью n, то всех его подмножеств, включая пустое подмножество и его самого будет https://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 и до https://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
74 / 74 / 13
Регистрация: 21.10.2010
Сообщений: 376
03.08.2012, 09:02
Никакой математики, чистый перебор.

Сложность: вроде https://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
8488 / 6155 / 615
Регистрация: 10.12.2010
Сообщений: 28,683
Записей в блоге: 30
03.08.2012, 23:28
Цитата Сообщение от 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;
}
//---------------------------------------------------------------------------
Вывод:
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Текущая кодовая страница: 1251
123
132
213
231
312
321
12
13
21
23
31
32
1
2
3
Для продолжения нажмите любую клавишу . . .
1
04.08.2012, 04:58

Не по теме:

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

0
74 / 74 / 13
Регистрация: 21.10.2010
Сообщений: 376
04.08.2012, 12:36
Цитата Сообщение от 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
8488 / 6155 / 615
Регистрация: 10.12.2010
Сообщений: 28,683
Записей в блоге: 30
04.08.2012, 12:38
Попробуйте больше символов например "hello"
0
74 / 74 / 13
Регистрация: 21.10.2010
Сообщений: 376
04.08.2012, 12:42
Цитата Сообщение от Avazart Посмотреть сообщение
Попробуйте больше символов например "hello"

вывод
Code
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
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
8488 / 6155 / 615
Регистрация: 10.12.2010
Сообщений: 28,683
Записей в блоге: 30
04.08.2012, 12:49
У меня выдает 170 комбинаций (учитывая еще то что "L" считается у меня за одну комбинацию)
0
74 / 74 / 13
Регистрация: 21.10.2010
Сообщений: 376
04.08.2012, 13:03
Цитата Сообщение от Avazart Посмотреть сообщение
У меня выдает 170 комбинаций (учитывая еще то что "L" считается у меня за одну комбинацию)
а в чём у меня тогда ошибка?
0
0 / 0 / 2
Регистрация: 14.05.2012
Сообщений: 28
04.08.2012, 22:21  [ТС]
Avazart, Hi4ko, Спасибо большое. Однако, немного комментариев лишними бы не были. =)
alkagolik, Я тебя чуток не понял...

Не по теме:

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

0
Эксперт С++
 Аватар для Avazart
8488 / 6155 / 615
Регистрация: 10.12.2010
Сообщений: 28,683
Записей в блоге: 30
04.08.2012, 22:24
Я привел и алгоритм, коментарии в коде...
0
 Аватар для alkagolik
1599 / 622 / 113
Регистрация: 15.07.2011
Сообщений: 3,548
04.08.2012, 22:40
Цитата Сообщение от Hi4ko Посмотреть сообщение
Никакой математики, чистый перебор.
правильно. Долой логарифмы!
Цитата Сообщение от deadstrike Посмотреть сообщение
alkagolik, Я тебя чуток не понял...
да я как бы тоже не особо тебя понял...
0
74 / 74 / 13
Регистрация: 21.10.2010
Сообщений: 376
04.08.2012, 23:05
Цитата Сообщение от alkagolik Посмотреть сообщение
правильно. Долой логарифмы!

https://www.cyberforum.ru/cgi-bin/latex.cgi?2^n тоже не логарифм, хоть и быстрее https://www.cyberforum.ru/cgi-bin/latex.cgi?n^3 , согласен)
0
быдлокодер
 Аватар для kravam
1724 / 911 / 106
Регистрация: 04.06.2008
Сообщений: 5,705
05.08.2012, 09:53
Немножко теории. Итак, тебе надо Получить Сочетаний Из 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
8488 / 6155 / 615
Регистрация: 10.12.2010
Сообщений: 28,683
Записей в блоге: 30
05.08.2012, 12:04
alkagolik, думаю при проходе по булеану не делается ли лишних перестановок?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
05.08.2012, 12:04
Помогаю со студенческими работами здесь

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

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

Задача с комбинаторики
Сколькими способами можно разместить 10 одинаковых открыток в 4 почтовых ящиках так, чтобы: а) не было пустых ящиков б) во втором ящике...

Уравнения из комбинаторики!
Товарищи, кто чем сможет! Вроде просто , а у меня ну не как не получается. Решите уравнение! Вместо темного, неразборчивого фото -...

Программа с комбинаторики
Есть небольшая проблема . Решал дискретную математику . Но суть не в этом. Наткнулся на такую проблему. Нужно в программном виде решить...


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Новые блоги и статьи
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++
8Observer8 10.03.2026
Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:
Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE
8Observer8 10.03.2026
Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .
Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки
Neotwalker 08.03.2026
Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .
Модульная разработка через nuget packages
DevAlt 07.03.2026
Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере F#
DevAlt 06.03.2026
В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .
Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование
8Observer8 05.03.2026
Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .
SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D
8Observer8 04.03.2026
Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .
SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий
8Observer8 02.03.2026
Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru