VPF::Какой алгоритм использовать? - Форум программистов

lamber

Дата 11.1.2011, 22:07 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 143
Регистрация: 20.12.2008

Репутация: нет
Всего: нет

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

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

alexvs11

Дата 11.1.2011, 22:35 (ссылка)

(нет голосов)

Загрузка ...

hell is here

Профиль
Группа: Участник
Сообщений: 518
Регистрация: 21.8.2010

Репутация: 6
Всего: 10

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

lamber

Дата 11.1.2011, 22:36 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 143
Регистрация: 20.12.2008

Репутация: нет
Всего: нет

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

htzg

Дата 11.1.2011, 23:00 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 150
Регистрация: 17.4.2010

Репутация: нет
Всего: нет

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

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

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

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

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

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

lamber

Дата 12.1.2011, 01:28 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 143
Регистрация: 20.12.2008

Репутация: нет
Всего: нет

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

azesmcar

Дата 12.1.2011, 08:44 (ссылка)

(голосов:1)

Загрузка ...

uploading...

Профиль
Группа: Участник Клуба
Сообщений: 6291
Регистрация: 12.11.2004
Где: Армения

Репутация: 81
Всего: 211

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/d59a9f84d53d...1540956d64c6cf3

Это сообщение отредактировал(а) azesmcar - 12.1.2011, 08:59

миг

Дата 14.1.2011, 19:29 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 158
Регистрация: 15.9.2008

Репутация: нет
Всего: 1

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

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

--------------------

Oaks may fall when reeds stand the storm.

lamber

Дата 14.1.2011, 20:37 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 143
Регистрация: 20.12.2008

Репутация: нет
Всего: нет

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

azesmcar

Дата 14.1.2011, 21:03 (ссылка)

(нет голосов)

Загрузка ...

uploading...

Профиль
Группа: Участник Клуба
Сообщений: 6291
Регистрация: 12.11.2004
Где: Армения

Репутация: 81
Всего: 211

lamber

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

lamber

Дата 14.1.2011, 22:01 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 143
Регистрация: 20.12.2008

Репутация: нет
Всего: нет

2azesmcar

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

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

Это сообщение отредактировал(а) lamber - 14.1.2011, 22:03

lamber

Дата 15.1.2011, 02:17 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 143
Регистрация: 20.12.2008

Репутация: нет
Всего: нет

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;
}

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

Это сообщение отредактировал(а) lamber - 15.1.2011, 02:18

azesmcar

Дата 15.1.2011, 07:52 (ссылка)

(нет голосов)

Загрузка ...

uploading...

Профиль
Группа: Участник Клуба
Сообщений: 6291
Регистрация: 12.11.2004
Где: Армения

Репутация: 81
Всего: 211

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

)

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

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

htzg

Дата 15.1.2011, 16:49 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 150
Регистрация: 17.4.2010

Репутация: нет
Всего: нет

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

)

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

спасибо!

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

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »