Строка и вопрос об отображении символа для гуру там

РЕДАКТИРОВАТЬ: Это должен быть самый быстрый и простой алгоритм. Некоторые могут поспорить со стилем или портативностью; Я думаю, что это идеально подходит для встраиваемого типа, и я уже потратил на это достаточно много времени. Оригинал оставляю ниже.

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

Генерирует 231 млн строк в секунду или ~ 9,5 цикла на строку на ядре Core2 с тактовой частотой 2,2 ГГц. Условия тестирования и использования указаны ниже.

#include <iostream>
using namespace std;

int const alphabet_size = CHAR_MAX+1;
typedef int map_t; // may be char or short, small performance penalty
int const sign_bit = 1<< CHAR_BIT*sizeof(map_t)-1;
typedef map_t cmap[ alphabet_size ];

void CreateMap( char *str, cmap &m ) {
    fill( m, m+sizeof(m)/sizeof(*m), 0 );
    char *str_end = strchr( str, 0 ) + 1;
    str_end[-1] = ' '; // space-terminated strings
    char prev = ' ';
    for ( char *pen = str; pen != str_end; ++ pen ) {
        if ( * pen == ' ' ) {
            m[ prev ] |= sign_bit;
            prev = 0;
        }
        m[ * pen ] = * pen;
        if ( prev != ' ' ) swap( m[prev], m[ *pen ] );
        prev = *pen;
    }
    for ( int mx = 0; mx != sizeof(m)/sizeof(*m); ++ mx ) {
        if ( m[mx] == 0 ) m[mx] = mx | sign_bit;
    }
}

bool NextMapping( char *s, char *s_end, cmap &m ) {
    for ( char *pen = s; pen != s_end; ++ pen ) {
        map_t oldc = *pen, newc = m[ oldc ];
        * pen = newc & sign_bit-1;
        if ( newc >= 0 ) return true;
    }
    return false;
}

int main( int argc, char **argv ) {
    uint64_t cnt = 0;
    cmap m;
    CreateMap( argv[1], m );
    char *s = argv[2], *s_end = strchr( s, 0 );
    do {
        ++ cnt;
    } while ( NextMapping( s, s_end, m ) );
    cerr << cnt;
    return 0;
}

ОРИГИНАЛ:

Не такой короткий и прочный, как мне хотелось бы, но вот кое-что.

• Требует, чтобы входная строка всегда содержала первую букву в алфавитном порядке в каждом наборе замены.
• Выполнить a la maptool 'aeo dgh bi' abbd
• Вывод находится в обратном лексикографическом порядке.
• Производительность примерно 22 цикла на строку (100 млн строк в секунду при 2,2 ГГц Core2)
  • НО моя платформа пытается быть умной с строкой s, замедляя ее
  • Если я изменю его на использование строк char * , он будет работать со скоростью 142M строк / сек (~ 15,5 цикла / строка)
• Должно быть возможно работать быстрее, используя char [256] таблица отображения и еще один char [256] , определяющий, какие символы завершают цикл.

Структура данных карты представляет собой массив узлов, связанных в кольцевые списки.

#include <iostream>
#include <algorithm>
using namespace std;

enum { alphabet_size = UCHAR_MAX+1 };

struct MapNode {
     MapNode *next;
     char c;
     bool last;
     MapNode() : next( this ), c(0), last(false) {}
};

void CreateMap( string s, MapNode (&m)[ alphabet_size ] ) {
    MapNode *mprev = 0;
    replace( s.begin(), s.end(), ' ', '\0' );
    char *str = const_cast<char*>(s.c_str()), *str_end = str + s.size() + 1;
    for ( char *pen = str; pen != str_end; ++ pen ) {
        if ( mprev == 0 ) sort( pen, pen + strlen( pen ) );
        if ( * pen == 0 ) {
            if ( mprev ) mprev->last = true;
            mprev = 0;
            continue;
        }
        MapNode &mnode = m[ * pen ];
        if ( mprev ) swap( mprev->next, mnode.next ); // link node in
        mnode.c = * pen; // tell it what char it is
        mprev = &mnode;
    }
       // make it easier to tell that a node isn't in any map
    for ( MapNode *mptr = m; mptr != m + alphabet_size; ++ mptr ) {
        if ( mptr->next == mptr ) mptr->next = 0;
    }
}

bool NextMapping( string &s, MapNode (&m)[ alphabet_size ] ) {
    for ( string::iterator it = s.begin(); it != s.end(); ++ it ) {
        MapNode &mnode = m[ * it ];
        if ( mnode.next ) {
            * it = mnode.next->c;
            if ( ! mnode.last ) return true;
        }
    }
    return false;
}

int main( int argc, char **argv ) {
    MapNode m[ alphabet_size ];
    CreateMap( argv[1], m );
    string s = argv[2];
    do {
        cerr << s << endl;
    } while ( NextMapping( s, m ) );
 return 0;
}

Я бы хотел создать массив индексов той же длины, что и строка, все инициализированные нулем. Затем мы рассматриваем этот массив индексов как счетчик для перечисления всех возможных отображений нашей исходной строки. Индекс 0 сопоставляет эту позицию в строке с первым отображением для этого символа, 1 - со вторым и т. Д. Мы можем проходить их по порядку, просто увеличивая последний индекс в массиве, перенося на следующую позицию, когда мы достичь максимального количества сопоставлений для этой позиции.

Чтобы использовать ваш пример, у нас есть сопоставления

'a' => 'e', 'o'
'b' => 'i'

Для входной строки «abba» нам нужен четырехэлементный массив для наших индексов:

[0,0,0,0] => "abba"
[0,0,0,1] => "abbe"
[0,0,0,2] => "abbo"
[0,0,1,0] => "abia"
[0,0,1,1] => "abie"
[0,0,1,2] => "abio"
[0,1,0,0] => "aiba"
[0,1,0,1] => "aibe"
[0,1,0,2] => "aibo"
[0,1,1,0] => "aiia"
[0,1,1,1] => "aiie"
[0,1,1,2] => "aiio"
[1,0,0,0] => "ebba"
[1,0,0,1] => "ebbe"
[1,0,0,2] => "ebbo"
[1,0,1,0] => "ebia"
[1,0,1,1] => "ebie"
[1,0,1,2] => "ebio"
[1,1,0,0] => "eiba"
[1,1,0,1] => "eibe"
[1,1,0,2] => "eibo"
[1,1,1,0] => "eiia"
[1,1,1,1] => "eiie"
[1,1,1,2] => "eiio"
[2,0,0,0] => "obba"
[2,0,0,1] => "obbe"
[2,0,0,2] => "obbo"
[2,0,1,0] => "obia"
[2,0,1,1] => "obie"
[2,0,1,2] => "obio"
[2,1,0,0] => "oiba"
[2,1,0,1] => "oibe"
[2,1,0,2] => "oibo"
[2,1,1,0] => "oiia"
[2,1,1,1] => "oiie"
[2,1,1,2] => "oiio"

Прежде чем мы начнем генерировать эти строки, нам понадобится где-то чтобы сохранить их, что в C означает, что нам придется выделить память. К счастью, мы уже знаем длину этих строк и можем вычислить количество строк, которые мы собираемся сгенерировать - это просто произведение количества отображений для каждой позиции.

Хотя вы можете вернуть их в массиве , я предпочитаю использовать обратный вызов , чтобы возвращать их, когда я их нахожу.

#include <string.h>
#include <stdlib.h>
int each_combination( 
    char const * source, 
    char const * mappings[256],
    int (*callback)(char const *, void *), 
    void * thunk
) {
  if (mappings == NULL || source == NULL || callback == NULL )
  {
    return -1;
  }
  else
  {
    size_t i;
    int rv;
    size_t num_mappings[256] = {0};
    size_t const source_len = strlen(source);
    size_t * const counter = calloc( source_len, sizeof(size_t) );
    char * const scratch = strdup( source );

    if ( scratch == NULL || counter == NULL )
    {
      rv = -1;
      goto done;
    }

    /* cache the number of mappings for each char */
    for (i = 0; i < 256; i++)
      num_mappings[i] = 1 + (mappings[i] ? strlen(mappings[i]) : 0);

    /* pass each combination to the callback */
    do {
      rv = callback(scratch, thunk);
      if (rv != 0) goto done;

      /* increment the counter */
      for (i = 0; i < source_len; i++)
      {
        counter[i]++;
        if (counter[i] == num_mappings[(unsigned char) source[i]])
        {
          /* carry to the next position */
          counter[i] = 0;
          scratch[i] = source[i];
          continue;
        }
        /* use the next mapping for this character */
        scratch[i] = mappings[(unsigned char) source[i]][counter[i]-1];
        break;
      }
    } while(i < source_len);

done:
    if (scratch) free(scratch);
    if (counter) free(counter);
    return rv;
  }
}
#include <stdio.h>
int print_each( char const * s, void * name)
{
    printf("%s:%s\n", (char const *) name, s);
    return 0;
}
int main(int argc, char ** argv)
{
  char const * mappings[256] = { NULL };
  mappings[(unsigned char) 'a'] = "eo";
  mappings[(unsigned char) 'b'] = "i";

  each_combination( "abba", mappings, print_each, (void *) "abba");
  each_combination( "baobab", mappings, print_each, (void *) "baobab");

  return 0;
}

По сути, вы хотите выполнить поиск в глубину (DFS) или любой другой обход ориентированного ациклического графа слов (DAWG). Я опубликую код в ближайшее время.

Здесь есть ссылка на архив фрагментов, который делает это, здесь Permute2.c . Есть еще один вариант перестановки строк (я думаю, вы могли бы затем отфильтровать те, которых нет на карте!) См. Здесь в архиве ' snippets ' ...

Надеюсь, это поможет, { {1}} С уважением, Том.