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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 28, средняя оценка - 4.79
ramzay
3 / 3 / 1
Регистрация: 17.02.2013
Сообщений: 44
#1

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

21.02.2013, 01:12. Просмотров 4317. Ответов 11
Метки нет (Все метки)

Итак,здравствуйте форумчане.
Привела меня к вам интересная задачка.
Вводится слово,заранее не известно количество букв
необходимо вывести на экран все возможные сочетания,в задании написано для простоты не использовать повторяющиеся символы.
Пример
Вода
Вывод(вывод буду отделять знаком "_"):
В_о_д_а_во_вд_ва_ов_од_...._вод_ода_одав_даво
и т.д.
тоестьв данном случаешь от 1 до 4 символов в сочетании
все сделать необходимо с использованием простейших функций(но желательно без них для лучшего понимания)
Тоесть на примитивном уровне.
Заранее благодарен
никак не могу совладать с данным заданием...

Добавлено через 55 секунд
http://e-maxx.ru/algo/generating_combinations
есть вот такой алгоритм...но применить его невыходит
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.02.2013, 01:12
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Перебор и вывод всех возможных сочетаний (C++):

Организовать перебор всех возможных сочетаний - C++
Затрудняюсь с алгоритмом. Как можно организовать перебор всех возможных группировок? Имеется несколько романов одного писателя. Для...

Перебор всех возможных сочетаний заданных переменных - C++
Чтобы не создавать новую тему, напишу здесь. Есть несколько переменных - около 20, часть переменных может иметь 2 значения, часть - три...

Комбинаторика, перебор всех сочетаний - C++
Предположим есть массив int ar = {0,0,0,0,0,1,1,1} (содержит 0 либо 1, число единиц(нулей) постоянно для всех полученных сочетаний....

Реализовать перебор всех возможных IP-адресов (С++) - C++
Реализовать перебор всех возможных IP-адресов, начиная с 0.0.0.0, заканчивая 255.255.255.0. (проще говоря перебор всех возможных комбинаций...

Перебор всех возможных подмножеств множества целых чисел - C++
Всем привет)))) Пожалуйста, помогите решить задачку!!!!! Очень нужно, срочно!!! Программа перебора всех возможных подмножеств множества...

Перебор всех возможных вариантов с переменными приравненных к определенному значению - C++
Помогите решить задачу: Есть 3 переменные А, В, С и у каждого из них какое-то целочисленное значение, которое задает пользователь. Нужно...

11
nonedark2008
976 / 716 / 161
Регистрация: 28.07.2012
Сообщений: 1,959
21.02.2013, 01:24 #2
А обязателен ли такой порядок вывода?
0
ValeryS
Модератор
6794 / 5202 / 499
Регистрация: 14.02.2011
Сообщений: 17,451
21.02.2013, 01:32 #3
Цитата Сообщение от ramzay Посмотреть сообщение
простейших функций(но желательно без них для лучшего понимания)
без них не получится выводить на экран ведь надо
могу предложить такой подход
берешь массив на 33 ( сколько букв в алфавите) обнуляешь его
анализируешь строку
заполняешь массив
если допустим буква А в первую ячейку записываешь 1
если Б во вторую
а потом проходишь этот массив циклами
0
ramzay
3 / 3 / 1
Регистрация: 17.02.2013
Сообщений: 44
21.02.2013, 02:00  [ТС] #4
Цитата Сообщение от ValeryS Посмотреть сообщение
без них не получится выводить на экран ведь надо
могу предложить такой подход
берешь массив на 33 ( сколько букв в алфавите) обнуляешь его
анализируешь строку
заполняешь массив
если допустим буква А в первую ячейку записываешь 1
если Б во вторую
а потом проходишь этот массив циклами
ну gets и puts можно
возможно я не атк выразился
под обнулением мы понимаем заполнение массива '0'?
все понял за исключением какими циклами проходить так что бы вывод был 2,3,4 буквы(по 1 букве можно итак разбить)
ведь мы не знаем количество букв в слове
был бы благодарен если бы вы помогли хотябы частью кода и желательно на си(необязательно,просто для лучшего понимания)

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

В О Д А
о д а в д а в о а в о д
........... .......... ......... .........
0
ramzay
3 / 3 / 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 быть не может
0
ramzay
3 / 3 / 1
Регистрация: 17.02.2013
Сообщений: 44
22.02.2013, 23:53  [ТС] #11
up
нужно решить тем способом что указан по ссылке.
решино рекурсией,сказали сделать без нее
0
ramzay
3 / 3 / 1
Регистрация: 17.02.2013
Сообщений: 44
25.02.2013, 02:07  [ТС] #12
up!
0
25.02.2013, 02:07
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.02.2013, 02:07
Привет! Вот еще темы с ответами:

Перебор всех возможных подмножеств заданного множества целых чисел - C++
Помогите решить задачу. Есть заданное множество целых чисел: -1 0 1. Нужно перебрать все возможные способы размещения в векторе, этих...

Перебор всех возможных способов размещения n различных предметов по m различным ящикам - C++
Ребят, я на этом форуме не очень давно и хочу попросить помощи, Задача такого рода: написать программу перебора всех возможных способов...

Перебор неповторяющихся сочетаний - C++
Здравствуйте. Существует ли какая-нибудь функция на c++, которая перебирает все возможные перестановки без повторений элементов? например...

Перебор возможных вариантов разреза трубы - C++
Доброго времени суток! Есть задача:"Вводится длина трубы, количество заготовок (1 .. 5), которые можно вырезать из трубы, и длина каждой...


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

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

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