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

Перебор и вывод всех возможных сочетаний - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 28, средняя оценка - 4.79
ramzay
2 / 2 / 1
Регистрация: 17.02.2013
Сообщений: 44
21.02.2013, 01:12     Перебор и вывод всех возможных сочетаний #1
Итак,здравствуйте форумчане.
Привела меня к вам интересная задачка.
Вводится слово,заранее не известно количество букв
необходимо вывести на экран все возможные сочетания,в задании написано для простоты не использовать повторяющиеся символы.
Пример
Вода
Вывод(вывод буду отделять знаком "_"):
В_о_д_а_во_вд_ва_ов_од_...._вод_ода_одав_даво
и т.д.
тоестьв данном случаешь от 1 до 4 символов в сочетании
все сделать необходимо с использованием простейших функций(но желательно без них для лучшего понимания)
Тоесть на примитивном уровне.
Заранее благодарен
никак не могу совладать с данным заданием...

Добавлено через 55 секунд
http://e-maxx.ru/algo/generating_combinations
есть вот такой алгоритм...но применить его невыходит
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
nonedark2008
623 / 501 / 92
Регистрация: 28.07.2012
Сообщений: 1,338
21.02.2013, 01:24     Перебор и вывод всех возможных сочетаний #2
А обязателен ли такой порядок вывода?
ValeryS
Модератор
6373 / 4839 / 440
Регистрация: 14.02.2011
Сообщений: 16,038
21.02.2013, 01:32     Перебор и вывод всех возможных сочетаний #3
Цитата Сообщение от ramzay Посмотреть сообщение
простейших функций(но желательно без них для лучшего понимания)
без них не получится выводить на экран ведь надо
могу предложить такой подход
берешь массив на 33 ( сколько букв в алфавите) обнуляешь его
анализируешь строку
заполняешь массив
если допустим буква А в первую ячейку записываешь 1
если Б во вторую
а потом проходишь этот массив циклами
ramzay
2 / 2 / 1
Регистрация: 17.02.2013
Сообщений: 44
21.02.2013, 02:00  [ТС]     Перебор и вывод всех возможных сочетаний #4
Цитата Сообщение от ValeryS Посмотреть сообщение
без них не получится выводить на экран ведь надо
могу предложить такой подход
берешь массив на 33 ( сколько букв в алфавите) обнуляешь его
анализируешь строку
заполняешь массив
если допустим буква А в первую ячейку записываешь 1
если Б во вторую
а потом проходишь этот массив циклами
ну gets и puts можно
возможно я не атк выразился
под обнулением мы понимаем заполнение массива '0'?
все понял за исключением какими циклами проходить так что бы вывод был 2,3,4 буквы(по 1 букве можно итак разбить)
ведь мы не знаем количество букв в слове
был бы благодарен если бы вы помогли хотябы частью кода и желательно на си(необязательно,просто для лучшего понимания)

Добавлено через 18 секунд
Цитата Сообщение от nonedark2008 Посмотреть сообщение
А обязателен ли такой порядок вывода?
нет,важно чтобы были все возможные сочетания
MrGrig
176 / 159 / 2
Регистрация: 08.10.2012
Сообщений: 422
21.02.2013, 06:27     Перебор и вывод всех возможных сочетаний #5
без знания количества элементов в массиве, к сожалению не получится. Нужно его подсчитывать либо передавать вместе с массивом. Но есть одно но. Если вводить с клавиатуры я обычно ввожу в массив длинною 1к символов. Потом беру его длинну создаю динамический массив такого же размера и переношу в него содержимое первого. Соответственно длину в этот момент можно записать. При считывании из файла примерно такая же ситуация. если брать статический массив, то у него можно подсчитать размер стандартной функцией. Все буквы я бы записал бы в бинарное дерево. В ней рекурсивная функция. Код я писать не буду ибо времени мало, алгоритм опишу примерный но умельцы тут возможно его подшаманят.
Итак обычный обход бинарного дерева не важно.
В самих листьях нужен маркер присутствия. Переходим в левый элемент вызываем функцию опять. и т.д. пока не обойдем всё дерево, на обратном ходу выводить букву хранящуюся в листе. Очень затратный механизм правда, который вполне возможно будет работать месяц, если на входе будет строка длиньше символов 20-30, но с другой стороны в строке из 30 символов которые в худшем случае не повторяются примерно 2*10^44 комбинаций и это только длиной в 30 символов, а нам необходимо рассмотреть еще и 29, 28 и т.д...
ValeryS
Модератор
6373 / 4839 / 440
Регистрация: 14.02.2011
Сообщений: 16,038
21.02.2013, 09:06     Перебор и вывод всех возможных сочетаний #6
Цитата Сообщение от ramzay Посмотреть сообщение
ведь мы не знаем количество букв в слове
Вот здесь возникает вопрос от решения зависит дальнейшее поведение программы
количество букв в слове?
или количество разных букв в слове?
В слове Абба 2 4 буквы? или 4?или 3 если мы различаем большие и малые буквы?
nonedark2008
623 / 501 / 92
Регистрация: 28.07.2012
Сообщений: 1,338
21.02.2013, 09:59     Перебор и вывод всех возможных сочетаний #7
Первым делом я бы подсчитал кол-во неповторяющихся букв в слове, занес бы их в массив(или в Вектор). Пусть таких букв будет N. Теперь у нас есть множество букв, каждое сочетание, которое можно составить, можно представить в виде битовой маски из N бит, где каждый бит означает - входит ли данная буква в сочетание или нет. Если переберешь все числа от 1 до N-1, то ты переберешь все возможные сочетания. Осталось написать только дешифратор - из битовой маски выводить сочетание.
ramzay
2 / 2 / 1
Регистрация: 17.02.2013
Сообщений: 44
21.02.2013, 11:25  [ТС]     Перебор и вывод всех возможных сочетаний #8
Цитата Сообщение от ValeryS Посмотреть сообщение
Вот здесь возникает вопрос от решения зависит дальнейшее поведение программы
количество букв в слове?
или количество разных букв в слове?
В слове Абба 2 4 буквы? или 4?или 3 если мы различаем большие и малые буквы?
слово будут вводится без повторяющихся символов,в условии моего задания сказано для упрощение вводите без повторябщихся символов.
Dr.Urban
63 / 58 / 7
Регистрация: 14.12.2011
Сообщений: 193
21.02.2013, 11:35     Перебор и вывод всех возможных сочетаний #9
А если сделать рекурсивно?

В О Д А
о д а в д а в о а в о д
........... .......... ......... .........
ramzay
2 / 2 / 1
Регистрация: 17.02.2013
Сообщений: 44
21.02.2013, 14:46  [ТС]     Перебор и вывод всех возможных сочетаний #10
Цитата Сообщение от Dr.Urban Посмотреть сообщение
А если сделать рекурсивно?

В О Д А
о д а в д а в о а в о д
........... .......... ......... .........
рекурсию вроде как никто не запрещал,но если честно я пока не понимаю как возможно сделать эту задачу с тем что мы изучили.
но тут нет вроде как сочитания 'вдо' дво и других.(если не так понял простите)

Добавлено через 3 часа 1 минуту
длинну масива можем подсчитать функцией strlen
слово не будет состоять больше чем из 10 символов
да и без повтор символов больше 33 быть не может

Добавлено через 4 минуты
длинну масива можем подсчитать функцией strlen
слово не будет состоять больше чем из 10 символов
да и без повтор символов больше 33 быть не может

Добавлено через 42 секунды
длинну масива можем подсчитать функцией strlen
слово не будет состоять больше чем из 10 символов
да и без повтор символов больше 33 быть не может
ramzay
2 / 2 / 1
Регистрация: 17.02.2013
Сообщений: 44
22.02.2013, 23:53  [ТС]     Перебор и вывод всех возможных сочетаний #11
up
нужно решить тем способом что указан по ссылке.
решино рекурсией,сказали сделать без нее
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.02.2013, 02:07     Перебор и вывод всех возможных сочетаний
Еще ссылки по теме:

Комбинаторика, перебор всех сочетаний C++
Перебор возможных вариантов разреза трубы C++
Организовать перебор всех возможных сочетаний C++

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

Или воспользуйтесь поиском по форуму:
ramzay
2 / 2 / 1
Регистрация: 17.02.2013
Сообщений: 44
25.02.2013, 02:07  [ТС]     Перебор и вывод всех возможных сочетаний #12
up!
Yandex
Объявления
25.02.2013, 02:07     Перебор и вывод всех возможных сочетаний
Ответ Создать тему
Опции темы

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