Поиск Лексикографически наименьшее расположение некоторой строки

Question

Название может показаться, что это очень распространенный вопрос, но, пожалуйста, несите меня.

В принципе, можно сказать, что в каждом индексе строки вы знаете, какие алфавиты могут быть в этом индексе, а затем вы хотите найти лексикографически наименьшее расположение.

Так, например:

Index | Options 
-------|---------- 
    1 | 'b' 
    2 | 'c', 'a' 
    3 | 'd', 'c' 
    4 | 'c', 'a' 

Итак, следовательно, о/р должен быть badc. И да, кстати, персонажи не могут повторить так жадный алгоритм.

Я думаю, что мы могли бы использовать какой-то поиск по ширине, создавая очередь или что-то вроде строки, и каждый раз, когда мы находили, мы не могли создать другую перестановку, вы выпадаете из списка. Сомнение это оптимально, хотя должно быть что-то в O(N). Есть идеи?

И нет, я не думаю, что C это плохо, но я предпочел бы фрагменты кода в C/C++: р

Спасибо!

Answer 1

Это может быть разрешено путем согласования алгоритма. Вы можете использовать решение сетевого потока для решения этой проблемы. Это можно разбить на двухчастную задачу графа.

Чтобы быть точным решением проблемы максимального веса или максимального соответствия максимальной стоимости, было бы решением.

Ниже двудольное множество вершин -

LEVEL   Alphabets 
1     a 
2     b 
3     c 
4     d 
        e 
        . 
        . 
        . 
        z 

Теперь назначьте ребра из множества уровня, чтобы установить алфавит, только и только те варианты, для этого уровня. Таким образом, здесь будут края: {1, b}, {2, a}, {2, c}, {3, c}, {3, d}, {4, a}, {4, c} Теперь , чтобы получить лексикографически мере результат вам нужно присвоить вес края в этой моде -

Edge Wt. = 26^(N-Level) * ('z' - Alphabet) 

Так, например, край вес ребра {2, с} будет

26^(4-2) * (26-3) = 26^2*23 

Теперь вы можете используйте стандартное решение максимального соответствия максимальной стоимости. Это полиномиальное решение. И это был бы лучший подход, насколько я могу думать сейчас. Наивное решение является экспоненциальным решением 26^N, поэтому, я думаю, вы были бы довольны полиномиальным решением.

Answer 2

Наивный подход состоит в том, чтобы использовать обратную трассировку и попробовать все возможные решения, однако это будет недостаточно эффективно (26!). Затем вы можете улучшить это решение backtrack, используя динамическое программирование с помощью битовой маски. Битовая маска может помочь вам сохранить, какие символы вы использовали до сих пор.

Напишите рекурсивную функцию, которая принимает два входа, индекс, который должен назначать символ, и битовая маска, которая указывает, какие символы мы использовали до сих пор. Первоначально битмаска содержит 26 нулей, что означает, что мы не использовали никаких символов. После присвоения символа некоторому индексу мы соответствующим образом меняем битмаску. Например, если мы используем символ a, мы устанавливаем первый бит битовой маски на 1. Таким образом, вы не будете решать много перекрывающихся под-проблем.

#include <iostream> 
#include <queue> 
#include <vector> 
#include <map> 
using namespace std; 

vector<vector<char> > data; 
map< pair<int,int>, string > dp; 

string func(int index, int bitmask){ 
    pair<int,int> p = make_pair(index,bitmask); 
    if (dp.count(p)) 
     return dp[p]; 
    string min_str = ""; 
    for (int i=0; i<data[index].size(); ++i){ 
     if ((bitmask&(1<<(data[index][i]-'a'))) == 0){ 
      string cur_str = ""; 
      cur_str += data[index][i]; 
      if (index+1 != data.size()){ 
       int mask = bitmask; 
       mask |= 1<<(data[index][i]-'a'); 
       string sub = func(index+1, mask); 
       if (sub == "") 
        continue;  
       cur_str += sub; 
      } 
      if (min_str == "" || cur_str < min_str){ 
       min_str = cur_str; 
      } 
     } 
    } 
    dp[p] = min_str; 
    return min_str; 
} 


int main() 
{ 
    data.resize(4); 
    data[0].push_back('b'); 
    data[1].push_back('c'); 
    data[1].push_back('a'); 
    data[2].push_back('d'); 
    data[2].push_back('c'); 
    data[3].push_back('c'); 
    data[3].push_back('a'); 
    cout << func(0,0) << endl; 
}