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

Замена элемента из множества - C++

Восстановить пароль Регистрация
 
r1se3
0 / 0 / 0
Регистрация: 18.09.2013
Сообщений: 37
09.07.2015, 17:51     Замена элемента из множества #1
Подскажите с оптимальным решением задачи.

Имеется динамический vector элементов для подстановки.
std:vector<std::string> letters_rep;
letters_rep.push_back("r");
letters_rep.push_back("u");
letters_rep.push_back("z");
letters_rep.push_back("w");


Имеется строка, в которой необходимо заменить символ:
std:string str = "zLhpgjHps53p";

Задача:
Заменить элемент "p", на элементы из множества, получив все возможные вариации, т.е.:

zLhrgjHzs53u
zLhrgjHrs53z
zLhwgjHus53z
zLhzgjHzs53z
и т.д.


Заранее благодарен.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
S_el
1907 / 1502 / 296
Регистрация: 15.12.2013
Сообщений: 5,915
09.07.2015, 17:57     Замена элемента из множества #2
r1se3, а где ваше решение и что понимается под оптимальным?
r1se3
0 / 0 / 0
Регистрация: 18.09.2013
Сообщений: 37
09.07.2015, 18:05  [ТС]     Замена элемента из множества #3
S_el, Начал реализовать вот так, но не знаю как правильно оформить луп.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
std:string str = "zLhpgjHps53p";
size_t count_p = std::count(str.begin(), str.end(), 'p');
 
std:vector<std::string> letters_rep;
letters_rep.push_back("r");
letters_rep.push_back("u");
letters_rep.push_back("z");
letters_rep.push_back("w");
 
int iter = static_cast< int >(pow(letters_rep.size(), std::count(hash.begin(), hash.end(), 'p'))); //макс количество
 
//не знаю как реализовать луп, для изменения и проверки
set<std::string>my_set;
for
{
if (my_set.count("1234"))
   //уже есть
else
  my_set.insert("1234");
}
S_el
1907 / 1502 / 296
Регистрация: 15.12.2013
Сообщений: 5,915
09.07.2015, 18:07     Замена элемента из множества #4
r1se3, тогда давайте как обычно.Пишите алгоритм и к каждому пункту свое видение реализации на C++.
r1se3
0 / 0 / 0
Регистрация: 18.09.2013
Сообщений: 37
09.07.2015, 18:10  [ТС]     Замена элемента из множества #5
S_el, я выше написал свое видение.

Вычисляю возможное множество, количество_букв^сколько_раз_встретилось_р
Далее, необходимо реализовать луп, в котором произойдут возможные замены.
S_el
1907 / 1502 / 296
Регистрация: 15.12.2013
Сообщений: 5,915
09.07.2015, 18:15     Замена элемента из множества #6
Цитата Сообщение от r1se3 Посмотреть сообщение
я выше написал свое видение.
оно рабочее?

Кстати,что вы хотите сделать 10 строчкой?
r1se3
0 / 0 / 0
Регистрация: 18.09.2013
Сообщений: 37
09.07.2015, 18:34  [ТС]     Замена элемента из множества #7
S_el, нет, оно не рабочее, т.к. я не знаю как проитерировать все возможные вариации.

В 10 строке, я вычисляю возможное колчество итоераций.
т.е. 5^2 = 25, за 25 итераций, возможно получить все решения.

Добавлено через 15 минут
S_el,

Извиняюсь, у меня 4 буквы и 3 вхожения. Следовательно
4^3
S_el
1907 / 1502 / 296
Регистрация: 15.12.2013
Сообщений: 5,915
09.07.2015, 18:52     Замена элемента из множества #8
r1se3, давайте еще раз.
На входе вот это:
C++
1
std:string str = "zLhpgjHps53p";
и это:
C++
1
2
3
4
letters_rep.push_back("r");
letters_rep.push_back("u");
letters_rep.push_back("z");
letters_rep.push_back("w");
на выходе - вектор строк,каждая из которых образована заменой буквы p на символ из второго вектора?
r1se3
0 / 0 / 0
Регистрация: 18.09.2013
Сообщений: 37
09.07.2015, 18:53  [ТС]     Замена элемента из множества #9
S_el, да вы поняли верно.
S_el
1907 / 1502 / 296
Регистрация: 15.12.2013
Сообщений: 5,915
09.07.2015, 19:03     Замена элемента из множества #10
например так:
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
# include<iostream>
# include<vector>
# include<string>
 
int main()
    {
    std::string str = "zLhpgjHps53p";
    std::vector<char> letters_rep;
    letters_rep.push_back('r');
    letters_rep.push_back('u');
    letters_rep.push_back('z');
    letters_rep.push_back('w');
    std::vector<std::string> res(letters_rep.size(),str);
 
    std::vector<size_t> vec_index;
    for(size_t i=0;i<str.size();i++)
        if(str[i]=='p')
            vec_index.push_back(i);
 
    for(size_t j=0;j<letters_rep.size();j++)
        for(const auto &i :vec_index)
            res[j][i]=letters_rep[j];
 
    for(const auto &el :res)
        std::cout<<el<<std::endl;
    return 0;
    }
r1se3
0 / 0 / 0
Регистрация: 18.09.2013
Сообщений: 37
09.07.2015, 19:09  [ТС]     Замена элемента из множества #11
S_el, нет, вы не до конца поняли задачу.

Суть заключается в том, что они должны получится комбинаторно, т.е. как у меня вначале написанно:

zLhrgjHzs53u
zLhrgjHrs53z
zLhwgjHus53z
zLhzgjHzs53z

и т.д.

А в вашем решение, просто замена p одной буквой.

Должно получиться 4^3 = 64 решения(строки)
S_el
1907 / 1502 / 296
Регистрация: 15.12.2013
Сообщений: 5,915
09.07.2015, 20:16     Замена элемента из множества #12
Цитата Сообщение от S_el Посмотреть сообщение
на выходе - вектор строк,каждая из которых образована заменой буквы p на символ из второго вектора?
Цитата Сообщение от r1se3 Посмотреть сообщение
да вы поняли верно.
Надо точнее формулировать.
Напишите пример,который полно описывает задачу,мне пока не удалось понять по какому признаку следует проводить каждую замену.
r1se3
0 / 0 / 0
Регистрация: 18.09.2013
Сообщений: 37
10.07.2015, 11:22  [ТС]     Замена элемента из множества #13
S_el, Все возможные замены.
Признак очевидный, исходя из комбинаторика и теории вероятности, мы знаем какое количество замен 'p' возможно. Необходимо реализовать алгоритм, который будет рекурсивно/итеративно заменять элемент, на предложенные.
S_el
1907 / 1502 / 296
Регистрация: 15.12.2013
Сообщений: 5,915
10.07.2015, 17:13     Замена элемента из множества #14
r1se3, когда-то писал что-то похожее:
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
# include <iostream>
# include <vector>
# include <algorithm>
# include <iterator>
# include <functional>
# include <cmath>
# include <string>
 
std::vector<std::vector<size_t>> create_Index(const size_t &N,const size_t &M);
 
int main()
    {
    std::string str = "zLhpgjHps53p";
    std::vector<char> letters_rep;
    letters_rep.push_back('r');
    letters_rep.push_back('u');
    letters_rep.push_back('z');
    letters_rep.push_back('w');
 
    std::vector<size_t> vec_index;
    for(size_t i=0;i<str.size();i++)
        if(str[i]=='p')
            vec_index.push_back(i);
    size_t A=vec_index.size(),B=letters_rep.size();
    auto SI = create_Index(A,B);
    size_t C =SI.size();
    std::vector<std::string> res(C,str);
    for(size_t j=0;j<C;j++)
        for(size_t i=0;i<A;i++)
            res[j][vec_index[i]]=letters_rep[SI[j][i]];
            
    for(const auto &el :res)
        std::cout<<el<<std::endl;
 
    return 0;
    }
 
std::vector<std::vector<size_t>> create_Index(const size_t &N,const size_t &M)
    {
    std::vector<std::vector<size_t>> VS(pow(M,N)); 
    size_t count=0;
 
    std::function<void(size_t,std::vector<size_t>)> Var=
        [&](size_t ind,std::vector<size_t> vec)
        {
        if(ind==0) 
            {
            VS[count++] =vec; 
            return;
            }
        else
            {
            std::vector<size_t> newvec(vec);
            auto temp = N-ind+1;
            newvec.resize(temp);
            for(size_t j=0;j<M;j++)
                {
                newvec[temp-1]=j;
                Var(ind-1,newvec);
                }
            }
        };
    Var(N,std::vector<size_t>());
    return VS;
    }
r1se3
0 / 0 / 0
Регистрация: 18.09.2013
Сообщений: 37
13.07.2015, 10:32  [ТС]     Замена элемента из множества #15
S_el, я решил похоже.
У меня рандомно выбираеться буква для замены, и подставляется. И так для каждой 'p'. Все это помешщается в сет, и отнимается общий счетчик вариантов. Так по кругу, пока варианты не закончатся.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int iter = static_cast< int >(pow(letters_rep.size(), count_p));
 
        //create possibility
        std::set<std::string>mutationstr;
        if (count_p != 0)
        {
            do{
                std::string str = hash;
                int pos;
                for (int i = 0; i < count_p; i++)
                {
                    int output = 0 + (rand() % (int)(letters_rep.size() - 1 - 0 + 1));
                    while ((pos = str.find('p')) != std::string::npos)
                        str.replace(pos, 1, letters_rep[output]);
                }
                if (mutationstr.count(str)) iter--;
                else mutationstr.insert(str);
            } while (iter != 0);
        }
        else mutationstr.insert(hash);
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.07.2015, 11:14     Замена элемента из множества
Еще ссылки по теме:

замена элемента матрицы на пробел C++
C++ Число изъять из множества А, если оно является элементом множества А, но не является элементом множества В
Где в коде происходит замена максимального и минимально элемента в строке массива? C++

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

Или воспользуйтесь поиском по форуму:
S_el
1907 / 1502 / 296
Регистрация: 15.12.2013
Сообщений: 5,915
13.07.2015, 11:14     Замена элемента из множества #16
Цитата Сообщение от r1se3 Посмотреть сообщение
У меня рандомно выбираеться буква для замены, и подставляется. И так для каждой 'p'. Все это помешщается в сет, и отнимается общий счетчик вариантов. Так по кругу, пока варианты не закончатся.
Мне кажется такое решение будет не эффективным даже по сравнению с моим вариантом.
Yandex
Объявления
13.07.2015, 11:14     Замена элемента из множества
Ответ Создать тему
Опции темы

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