Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Какой алгоритм использовать?

Автор: lamber 11.1.2011, 22:07

Столкнулся с нетривиальной задачей (для меня во всяком случае). Ну не будем многословным.
Дана строка:
I have a s{bad,terrible,doubt} feelings about this s{place,face,house}.

Как видим здесь есть макрос s{} в нем через запятую перечисляются разные варианты. Внимание вопрос как можно собрать в файле все возможные варианты предложения без повторений, если количество макросов в строке не известно.

Автор: alexvs11 11.1.2011, 22:35

как их количество может быть не известным, где что задается?

Автор: lamber 11.1.2011, 22:36

Строка с макросами берется из файла или вводится пользователем.

Автор: htzg 11.1.2011, 23:00

Это задача из серии когда не известно кол-во вложенный циклов

поможет виртуальная машина паскаля... (по-моему так называется)
заводите два массива цифр ( один лимиты, другой счетчики ) с размером равным кол-ву макросов...
лимиты выставляете по кол-ву слов в соответствующем макросе (или плюс один, если слова из этого макроса может не быть)...
потом начинаете перебирать младший счетчик, как достиг лимита обнуляете и увеличиваете на один следующий счетчик,
когда он в свою очередь достигнит лимита, также обнуляете и к следующий на один и т.д.

на каждой итерации теперь можно формировать строку, использую счетчики как индексы слова в макросе.

п.с.: из макросов нужно сформировать массивы со словами

Добавлено через 3 минуты и 13 секунд
http://liveworkspace.org/code/de3bf0578debf094100f066dd7bf4365

вот пример только здесь вместо слов в макросе перебираются символы

Автор: lamber 12.1.2011, 01:28

Блин что -то щас "синий" не могу разобрать, сможешь привести более конкретный пример, по задаче в коде.
ЗЫ
Мож с утра разберу код что скинул хз )))

Автор: azesmcar 12.1.2011, 08:44

lamber

Рекурсией.
Как-то так.

Код


#include <iostream>
#include <vector>
#include <string>
#include <iterator>
#include <algorithm>
#include <boost/format.hpp>

typedef std::vector<std::string> strings;
typedef std::vector<strings> macros_list;

void format_string(boost::format fmt, macros_list::iterator it, macros_list::iterator end, strings& data)
{
    for (strings::iterator strit = it->begin(); strit != it->end(); ++strit)
    {
        boost::format temp = fmt;
        if (it + 1 != end)
            format_string(temp % *strit, it + 1, end, data);
        else
            data.push_back((temp % *strit).str());
    }
}

int main()
{
    std::string str = "I have a %1% feelings about this %2%";

    macros_list macros;
    macros.push_back(strings());
    macros.back().push_back("bad");
    macros.back().push_back("terrible");
    macros.back().push_back("doubt");

    macros.push_back(strings());
    macros.back().push_back("place");
    macros.back().push_back("face");
    macros.back().push_back("house");

    strings data;
    format_string(boost::format(str), macros.begin(), macros.end(), data);

    std::copy(data.begin(), data.end(), std::ostream_iterator<std::string>(std::cout, "\n"));
}

http://liveworkspace.org/code/d59a9f84d53d9aa2e1540956d64c6cf3

Автор: миг 14.1.2011, 19:29

Цитата(lamber @ 12.1.2011, 01:28)

из серии пустите переночевать, а то пить хочется и кушать))

Автор: lamber 14.1.2011, 20:37

2миг
Сам то понял что сказал :?

Автор: azesmcar 14.1.2011, 21:03

lamber

Тему то что забросил? Пометь если вопрос решен (а он решен?).

Автор: lamber 14.1.2011, 22:01

2azesmcar

Вот щас сижу разбираюсь (последние два дня времени не было). Пытаюсь разобратся с алгоритмом который привел htzg, но пока безуспешно (моск не может адаптировать его под свою задачу, видимо слишеом маленький xD ). Твой вариант не очень подходит, с boost я не в товарищах, да и не хотелось бы тянуть такую либу для решения такой задачи. Вообщем тема открыта, если найду качественное решение вопроса, выложу код.

Включаемся господа, одна голова хорошо, а с несколькими можно и выпить)))

Автор: lamber 15.1.2011, 02:17

2htzq
Прекланяю колено алгоритм реально крут, видно я слишком туп разбирался около 4 часов с ним, хотя как видно в нем всего "пару строк" кода.

ниже работающий код решающий поставленную задачу.
Объявялеются особые благодарности htzq и azesmcar

Код


#include <vector>
#include <string>
#include <iostream>

using namespace std;

vector<size_t> counters;
vector<size_t> limits;
vector<vector<string>> macros;
vector<string> temp;
string temp_line;

string insert(string text,string from,string to)
{
  size_t index;
  index=text.find(from);
  if(index!=string::npos){
  text.replace(index, from.length(), "");
  text.insert(index,to);
  return text;
  }
  return "";

}

bool next_iterate()
{
    for(size_t i=0;i<limits.size();i++)
        if(!(++counters[i]<limits[i])) counters[i]=0;
        else
            return true;

    return false;
}
int main ()
{
  temp.push_back("bad");
  temp.push_back("terrible");
  temp.push_back("doubt");
  macros.push_back(temp);
  temp.clear();

  temp.push_back("place");
  temp.push_back("face");
  temp.push_back("house");
  macros.push_back(temp);
  temp.clear();

  string line("I have a @ feelings about this @");

  for(size_t i=0;i<macros.size();i++)
      limits.push_back(macros[i].size());

  counters.resize(macros.size());

  do
  {
      temp_line=line;
      for(size_t i=0;i<counters.size();i++)
      {          
          temp_line=insert(temp_line,"@",macros[i].at(counters[i]));
          
      }
       cout<<temp_line<<endl;

  }while(next_iterate());
  getchar();
  return 0;
}

Тему можно закрывать.

Автор: azesmcar 15.1.2011, 07:52

Цитата(lamber @ 14.1.2011, 22:01

)

boost я не в товарищах

boost я использовал лишь для замены макросов, можешь сам написать эту часть с помощью stl алгоритмов.

Автор: htzg 15.1.2011, 16:49

Цитата(lamber @ 15.1.2011, 02:17

)

2htzq
Прекланяю колено алгоритм реально крут, видно я слишком туп разбирался около 4 часов с ним, хотя как видно в нем всего "пару строк" кода.

спасибо!

Мне этот алгоритм самому когда-то подсказали! ;)