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

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

Форум программистов > C/C++: Для новичков > Перебрать все цепочки языка в заданном диапазоне

Автор: Alexey91 16.10.2011, 08:56

Здравствуйте!

Есть язык, который задается множеством {0,1}
Как можно перебрать все возможные элементы множества в заданном диапазоне

Например, диапазон от 2 до 3 включительно
00,01,10,11
000,001,010,011,100,101,110,111

Проблема в том, что язык может состоять из произвольных цепочек, т.е. {a,b,0}, {d,e,1}

Автор: math64 16.10.2011, 09:26

Перебирай N = количество букв в слове
Для I = 1..N
Перебирай все возможные буквы на I-м месте
Проверь полученное слово на допустимость в языке

Автор: Alexey91 16.10.2011, 09:34

math64, мне не понятно как перебирать

Хорошо для {0,1}
Минимальная длина слова N=2. Начинаем цикл.
Первая позиция (I=1). Выбираем 0 или 1. Выбрали 0. На второй тоже 0. Получили 00
Но в данном случае я выбираю сам ))), а не программа
Как сделать так, чтобы программа сама догадывалась, что следующее будет, например, 01

Автор: Alexey91 16.10.2011, 10:20

Я придумал с помощью рекурсии
Например N=3 (длина цепочек 3)

Код


char **M; // Множество цепочек
si label=0, L=7, S=2;  // L - длина цепочки, S - размер алфавита
char alphabet[2]={'0','1'}

// shift сдвиг по позиции текущей цепочки
// label номер элемента во множестве цепочек

void rek(char* A, si N, si shift)
{
 si i,j,k;

 if(N==1)
 {
  for(k=0; k < S; k++, label++)
  {
   A[shift]=alphabet[k];
   for(j=0; j < L; j++) M[label][j]=A[j];
  }
  shift=0;
 }

 else
 {
  for(i=0; i < S; i++)
  {
   A[shift]=alphabet[i];
   rek(A,N-1,shift+1);
  }

 }


}

Автор: math64 16.10.2011, 13:20

Код


const char letters[] = "01";
const int letterCount = sizeof(letters)/ sizeof(letters[0]) - 1;
const char firstLetter = letters[0];
const char lastLetter = letters[letterCount-1];
char nextLetter(char letter) {
   const char*p = strchr(letters, letter);
   return p[1];
}
bool nextWord (char* word, int wordLen = 0) {
  if (wordLen == 0)
    wordLen = strlen(word);
  for (int i = wordLen - 1; i >=0; i--) {
    char letter = word[i];
    if (letter == lastLetter) {
       word[i] = firstLetter;
       continue;
    }
    word[i] = nextLetter(letter);
    return true;
  }
  return false;
}

void enumWords(int len) {
  char* word = new char[len+1];
  for(int i =0; i < len; i++)
    word[i] = firstLetter;
  word[len] = '\0';
  do {
    addWord(word);
  } while(nextWord(word, len) );
  delete[] word;
}

Автор: Alexey91 16.10.2011, 16:13

math64, зачем вы пишете const перед переменными?

Автор: math64 16.10.2011, 19:41

Цитата(Alexey91 @ 16.10.2011, 16:13

)

math64, зачем вы пишете const перед переменными?

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

Код


class Language {
public:
  typedef void (*AddWord)(const char*); // callback функция

  Language(const char* p_letters);
  ~Langage();
  char nextLetter(char letter);
  bool nextWord(char* word, int length = 0);
  void enumWords(int length, AddWord addWord);
private:
  char* letters;
  int letterCount;
  char firstLetter;
  char lastLetter;
};