Форум программистов, компьютерный форум, киберфорум
C для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.79/235: Рейтинг темы: голосов - 235, средняя оценка - 4.79
0 / 0 / 0
Регистрация: 19.09.2008
Сообщений: 10
1

Перебор возможных комбинаций символов

23.09.2008, 21:19. Показов 47670. Ответов 51
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Чет мой чайник совсем не варит! Помогите сделать следущее:
Вывести все возможные комбинации слов. Есть:

C
1
2
char ch_table[] = "abc"; //таблица символов
char word[] = "aaa"; //само слово - начальный вариант
Логика мне ясна, а вот с реализацией туго!

Число возможных вариантов: 3*3*3 = 27

Код
->->->->->
aaa aab aac
aba abb abc
aca acb acc
baa bab bac
bba bbb bbc
bca bcb bcc
caa cab cac
cba cbb cbc
cca ccb ccc
Я думаю начать с конца слова, с постепенным смещением влево. Но вот запутался в циклах...

Допустим меняю последний символ:
aaa aab aac

Затем смещаюсь влево:
aba

Опять последний:
aba abb abc

И у меня ступор... Исходник пустил под скальпель, пытаясь что-то сделать, так что не просите показать

А где есть исходники подобных алгоритмов?
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
23.09.2008, 21:19
Ответы с готовыми решениями:

Перебор всез возможных комбинаций слов из слова их N-символов
Привет! Есть слово, допустим, "box" нужно перебрать все возможные варианты слов, которые возможно...

Перебор всех комбинаций 3-хзначного ключа
Приветствую дорогие форумчане! Помогите реализовать небольшую программку. Есть 3 вложенных...

Перебор и вывод всех возможных сочетаний
Итак,здравствуйте форумчане. Привела меня к вам интересная задачка. Вводится слово,заранее не...

Перебор возможных комбинаций из определенных символов
Например есть символы 'в', 'а', 'о', 'л'. Нужно чтобы отобразило слова сочетающие эти буквы, слова...

51
10 / 10 / 2
Регистрация: 18.08.2008
Сообщений: 127
23.09.2008, 22:20 2
C++
1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
using namespace std;
 
int main(){
    char A[]="ABC";
    for (int i=0;i<3;i++)
        for (int j=0;j<3;j++)
            for (int k=0;k<3;k++)
                cout <<A[i]<<A[j]<<A[k]<<"\t";
 
return 0;
}
Смотри
0
0 / 0 / 0
Регистрация: 19.09.2008
Сообщений: 10
24.09.2008, 09:51  [ТС] 3
Цитата Сообщение от qwone Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
using namespace std;
 
int main(){
    char A[]="ABC";
    for (int i=0;i<3;i++)
        for (int j=0;j<3;j++)
            for (int k=0;k<3;k++)
                cout <<A[i]<<A[j]<<A[k]<<"\t";
 
return 0;
}
Смотри
Хм, а если символов в слове 20? 20 циклов делать под каждый? Не есть хорошо.
Я придумал алгоритм с 2 циклами под любой размер слова, только немного запутался со 2 циклом.


Ура, написал...
Итого: без вывода cout, с использованием strcmp для сравнения комбинации с "паролем", комбинация из 6 символов (26 возможных букв) дала 308 915 776 возможных результатов за 3.4сек (90 857 581 комбинация в секунду)...
0
0 / 0 / 0
Регистрация: 29.09.2008
Сообщений: 9
24.07.2009, 18:47 4
Цитата Сообщение от SiNn3R Посмотреть сообщение
Ура, написал...
Итого: без вывода cout, с использованием strcmp для сравнения комбинации с "паролем", комбинация из 6 символов (26 возможных букв) дала 308 915 776 возможных результатов за 3.4сек (90 857 581 комбинация в секунду)...
напиши реализацию плиз
0
Временно недоступен
957 / 228 / 14
Регистрация: 12.04.2009
Сообщений: 926
24.07.2009, 20:01 5
А это за сколько посчитает?
Код
░TЎ▲[Ъ_"@
0
47 / 47 / 3
Регистрация: 07.01.2009
Сообщений: 297
24.07.2009, 21:02 6
Это комбинаторика. В данном случае, когда слово из 3 букв, то можно тупо все вариации подобрать циклами вложенных(и так можно до 6 вложенных циклов),т.е. получается перебор. Посмотри здесь(алгоритм похожий):
http://algolist.manual.ru/math... ations.php
Можно даже через рекурсию.
0
Заказ софта
343 / 188 / 21
Регистрация: 26.05.2009
Сообщений: 863
24.07.2009, 21:08 7
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
 
int main()
{
    char word[25];
    short len;
 
    std::cout << "Your word: ";
    std::cin.getline(word, 24);
 
    len = (short)strlen(word);
 
    for(short a = 0; a < len; a++)
        for(short b = 0; b < len; b++)
            for(short c = 0; c < len; c++)
                std::cout << word[a] << word[b] << word[c] << "\n";
 
    return 0;
}
0
47 / 47 / 3
Регистрация: 07.01.2009
Сообщений: 297
24.07.2009, 21:21 8
Цитата Сообщение от Search.. Посмотреть сообщение
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
 
int main()
{
    char word[25];
    short len;
 
    std::cout << "Your word: ";
    std::cin.getline(word, 24);
 
    len = (short)strlen(word);
 
    for(short a = 0; a < len; a++)
        for(short b = 0; b < len; b++)
            for(short c = 0; c < len; c++)
                std::cout << word[a] << word[b] << word[c] << "\n";
 
    return 0;
}
Уже написали,что тройной цикл не пойдет ))
0
Эксперт С++
7175 / 3234 / 81
Регистрация: 17.06.2009
Сообщений: 14,164
24.07.2009, 22:04 9
Нужно завести массив, где хранить номера в таблице символов.

C
1
2
3
4
char char_table[] = "abc";    // таблица символов
int char_count= 3;              // кол-во символов
int word_size;                    // размер слова
int word_num[MAX_WORD];  // номера в ch_table[]
Элементы word_num[] - это числа от 0 до char_count-1.
А потом просто в цикле увеличивать значения в word_num[] не забывая делать переносы в другой разряд.
0
562 / 373 / 55
Регистрация: 05.04.2009
Сообщений: 767
30.07.2009, 23:39 10
Цитата Сообщение от SiNn3R Посмотреть сообщение
Вывести все возможные комбинации слов
Цитата Сообщение от #pragma Посмотреть сообщение
А это за сколько посчитает?
Код:
░TЎ▲[Ъ_"@
"За сколько?" - это уже второй вопрос!
Кому надо подождут!
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
#include <iostream>
#include <iomanip>
#include <string>
#include <math.h>
 
using namespace std;
//=============================================== 
int main()
{
char * sn = "abcd";
 
const  int  len =          strlen(sn);
const long rlen = (long)pow(len, len);
string sx[rlen];
 
    //-----initialization--------
    
    for(int i = 0; i <  len; i++)
    for(int j = 0; j < rlen; j++)
    {               //*************************** 
        sx[j] = sn[(  j/(long)pow(len, i)  )%len ] + sx[j];
    }               //***************************
    //---------out---------------------------------
    
    for(int i = 0; i < rlen; cout << endl,i++)
    {
        cout << setw(len + 2) << i + 1 << " " << setw(len + 2)<< sx[i];
    }//----------------------------------------------------------------
 
system("pause"); 
return EXIT_SUCCESS;
}
//===============================================
0
depict1
281 / 146 / 4
Регистрация: 11.07.2009
Сообщений: 606
31.07.2009, 09:12 11
Цитата Сообщение от SiNn3R Посмотреть сообщение
А где есть исходники подобных алгоритмов?
C++
1
2
3
#include <algorithm>
std::next_permutation
std::prev_permutation
1
Эксперт С++
3071 / 1409 / 425
Регистрация: 19.01.2009
Сообщений: 3,880
31.07.2009, 11:05 12
Вот небольшой исходничек, написаный, после прочтения "Техники Сетевых Атак", Криса Касперски:
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
46
47
#include <stdio.h>
 
#define BUFFMAX 3
 
char buff[BUFFMAX];
 
char cb_poslmax, cb_poslmin;
int  wordb;
 
 
void get_next_pwd(int n)
{
    if (buff[n]==cb_poslmax)
    {
        buff[n] = cb_poslmin;
        if (!n)
        {
            // переход на новый разряд
            buff[++wordb] = cb_poslmin;
        }
        else
        {
            get_next_pwd(--n);
        }
    }
    else
        buff[n]++;
}
 
 
main()
{
    cb_poslmax = 'z';
    cb_poslmin = 'a';
 
    memset(buff, 0, sizeof(buff));
 
    buff[0] = cb_poslmin;
 
    wordb = 0;
 
    while (wordb<BUFFMAX)
    {
        get_next_pwd(wordb);
        printf("%s\n", buff);
    }
}
0
577 / 571 / 65
Регистрация: 29.01.2009
Сообщений: 1,274
31.07.2009, 14:04 13
polivets, если делать цикл с таким условием
C++
1
2
3
4
5
while (wordb<BUFFMAX)
{
        get_next_pwd(wordb);        
        printf("%s\n", buff);
}
то будет затираться завершающий нуль-символ. Правильнее тогда задать буфер как buff[BUFFMAX+1].
0
562 / 373 / 55
Регистрация: 05.04.2009
Сообщений: 767
31.07.2009, 18:09 14
zim22,
Цитата Сообщение от zim22 Посмотреть сообщение
Сообщение от SiNn3R
А где есть исходники подобных алгоритмов?

zim22
Код C++
#include <algorithm>
std::next_permutation
std:rev_permutation
они делают немножко ни то о чем просил автор вопроса
Цитата Сообщение от SiNn3R Посмотреть сообщение
aaa aab aac
aba abb abc
aca acb acc
baa bab bac
bba bbb bbc
bca bcb bcc
caa cab cac
cba cbb cbc
cca ccb ccc
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
#include <iostream>
#include <algorithm>
 
using namespace std;
 
//==========================================
int main () 
{
char arr[] = "abc";
 
const int N = strlen(arr);
 
    cout << "  arr[" <<  N <<  "] \n\n  ";
 
    sort(arr, arr + N); //reverse (arr, arr + N);
    cout << arr << "\n\n  ";
 
    while( next_permutation(arr, arr + N) )//prev_permutation
    {
        for(int i = 0; i < N; i++)
        {
            cout << arr[i]; 
        }
 
        cout << endl << "  ";   
    }
  
system("pause");
return EXIT_SUCCESS;
}
//==========================================
Вывод такой ->
abc

acb
bac
bca
cab
cba
0
depict1
281 / 146 / 4
Регистрация: 11.07.2009
Сообщений: 606
31.07.2009, 19:01 15
Цитата Сообщение от mirso Посмотреть сообщение
они делают немножко ни то о чем просил автор вопроса
я понял это уже после того, как запостил
0
0 / 0 / 0
Регистрация: 28.10.2009
Сообщений: 4
28.10.2009, 17:40 16
Люди хелп ми по другому никак ..мне нужно найти комбинацию из abc по 5 разов ВОТ пример (составить смог только 47 комбинаций а их должнобыть 120): ababc, bbbab, cbbcc ну и т.д. не могу больше мозг кипит а программы так до сих пор и не нашёл=(((((
0
эволюционирую потихоньку
468 / 466 / 91
Регистрация: 30.06.2009
Сообщений: 1,401
28.10.2009, 17:48 17
по-другому ? в смысле решение отличное от решения в 14м посте?
0
0 / 0 / 0
Регистрация: 28.10.2009
Сообщений: 4
28.10.2009, 18:07 18
Цитата Сообщение от TanT Посмотреть сообщение
по-другому ? в смысле решение отличное от решения в 14м посте?
нет я подставил символы тобишь буквы абс , но эти буквы обозначают для меня кое что иное , код который мне нужно подобрать состоит из 5 раз по 3 буквы , ещё раз приведу пример , : aaaaa, bbbbb, ccccc, ababc, bbbcb, aabcc.... что то в этом роде код зашифрован в 5 - и значениях а в одно значение можно подставить только a,b, или с . Теперь думаю понятней похожий пример я видел на этом сайте уже только там было из 3 по 3 , ; aaa, bbb, ccc, aab,aac,abb , abc, acc ....и т.д.
0
эволюционирую потихоньку
468 / 466 / 91
Регистрация: 30.06.2009
Сообщений: 1,401
28.10.2009, 18:27 19
короче, в твоём слове 5 символов каждый из которых может принимать одно из 3х значений

Добавлено через 3 минуты
чтото мне подсказывает что там далеко не 120 вариантов
0
0 / 0 / 0
Регистрация: 28.10.2009
Сообщений: 4
28.10.2009, 18:38 20
Да вот именно это я и хотел сказать , просто времени мало спешу=)

Добавлено через 8 минут
я нашёл формулу кабинаторики:
m
А , где n число элементов ,по m элементов
n

Добавлено через 39 секунд
Amn = n (n - 1)(n - 2) ... (n - m + 1).


Сочетаниями называют комбинации, составленные из n различных элементов по m элементов, которые отличаются хотя бы одним элементом. Число сочетаний
0
28.10.2009, 18:38
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
28.10.2009, 18:38
Помогаю со студенческими работами здесь

Перебор всех возможных комбинаций символов строки
Всем привет! Подскажите пожалуйста как осуществить перебор символов в строке, БЕЗ ПОВТОРОВ, только...

Как осуществить перебор всех возможных комбинаций символов строки
типа есть 3 символа - a, b, c 3*3=27 возможных вариантов для подбора aaa bbb ccc aab abb aba...

Перебор возможных комбинаций
Всем доброго времени. Имеется набор символов &quot;123456789&quot;. Нужно получить все возможные комбинации в...

Перебор возможных комбинаций
Уважаемые участники форума, был бы очень благодарен, если бы вы подсказали, как решить следующую...


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru