VPF::Нахождение всех возмлжных комбинаций символов

Code Magister

Дата 25.9.2007, 23:48 (ссылка)

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

Загрузка ...

Magister of Code

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

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

Допустим будем рассматривать только символы от a до z. Вводится максимальная длинна "слова". И далее находятся все возможные комбинации этих символов, не превыщающие длинны n.
Например если n=2, то должно выдать нечто вроде:

Код


a
aa
ab
ac
...
ay
az
b
ba
bb
bc
...
zy
zz

Это сообщение отредактировал(а) Code Magister - 25.9.2007, 23:50

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

Akina

Дата 26.9.2007, 00:09 (ссылка)

(голосов:1)

Загрузка ...

Советчик

Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

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

Код

'Компилировать не советую
for i="a" to "z"
 print i
 for j="a" to "z"
  print i+j
 next j
next i

При длине более 2 символов (или динамической) разумнее использовать рекурсию.

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

О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

Code Magister

Дата 26.9.2007, 15:11 (ссылка)

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

Загрузка ...

Magister of Code

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

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

Ну ето для 2-х символов, а можешь показать как с рекурсией? У меня с ней всегда проблеммы

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

esperant0

Дата 27.9.2007, 09:34 (ссылка)

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

Загрузка ...

Опытный

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

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

for i=1 to n^n*log(n^n)*100

x=случайное число от 1 до п.
y=случайное число размером х
нехт

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

Student->Teacher Assistant ->Research assistant->Microsoft Software Development Engineer

Пользователь получил наказание за то, что проигнорировал замечание которое было написано модератором а затем стерто и которое он - пользователь не мог видеть.

maxim1000

Дата 27.9.2007, 10:31 (ссылка)

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

Загрузка ...

Эксперт

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

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

Цитата(esperant0 @ 27.9.2007, 09:34

)

for i=1 to n^n*log(n^n)*100

x=случайное число от 1 до п.
y=случайное число размером х
нехт

этот код не обязательно выведет _все_ комбинации...

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

qqq

esperant0

Дата 27.9.2007, 10:51 (ссылка)

(голосов:1)

Загрузка ...

Опытный

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

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

Цитата(maxim1000 @ 27.9.2007, 10:31)

Цитата(esperant0 @ 27.9.2007, 09:34

)

for i=1 to n^n*log(n^n)*100

x=случайное число от 1 до п.
y=случайное число размером х
нехт

этот код не обязательно выведет _все_ комбинации...

Вероятность того что код не выведет все комбинации на порядки меньше вероятности того что вселенная взорвется.

А значит?

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

Akina

Дата 27.9.2007, 12:08 (ссылка)

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

Загрузка ...

Советчик

Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

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

Код


Sub RecursiveOutput(Current As String, Length As Integer, Charset As String)
Dim i As Integer
Debug.Print Current
If Len(Current) < Length Then
 For i = 1 To Len(Charset)
  Call RecursiveOutput(Current & Mid(Charset, i, 1), Length, Charset)
 Next i
End If
End Sub

Private Sub Command1_Click()
Call RecursiveOutput("", 3, "abc")
End Sub

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

wils0n

Дата 28.9.2007, 12:33 (ссылка)

(голосов:1)

Загрузка ...

Новичок

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

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

Примерно так. Без рекурсии. Next() генерирует след. комбинацию. Get() выдаёт её.

Код


#include<iostream>
#include<vector>
#include<string>

using std::string;
using std::vector;

class LetterCombination {
public:
    LetterCombination(int length);
    ~LetterCombination() {}

    // генерирует вывод
    string    Get();
    // гачинаем сначала
    void    First();
    // следующая комбинация
    bool    Next();
    // все ли комбинации уже сгенерированы
    bool    ThatsAll();

private:    
    bool    m_ThatsAll;
    // какой длины комбинации генерировать
    int    m_Length;
    // вектор с текущей комбинацией.
    vector<int>    m_Set;
};

LetterCombination::LetterCombination(int length) : m_ThatsAll(true), m_Length(length)
{ 
    m_Set = vector<int>(m_Length);
}

void LetterCombination::First()
{
    m_ThatsAll = false;
    for (int i = 0; i < m_Length; i++) m_Set[i] = 0;
    // первая комбинация 00..001 соответствует 'a'
    m_Set[m_Length-1] = 1;
}

bool LetterCombination::Next()
{
    // если все комбинации уже сгенерированы, то ничего не делаем.
    if ( m_ThatsAll ) return false;

    // увиличиваем последнюю букву.
    int i = m_Length-1;
    m_Set[i]++;

    // если последняя была уже 'z', то превращаем её в 'a' и увиличиваем на один
    // впереди стоящую...
    while( (i>0) && (m_Set[i] == 27) )
    {
        m_Set[i--] = 1;
        m_Set[i]++;
    }

    return !ThatsAll();
}

bool LetterCombination::ThatsAll()
{
    // если в первой позиции буква превзошла 'z', то всё!
    if (m_Set[0] == 27) 
    {
        First();
        m_ThatsAll = true;
    }
    return m_ThatsAll;
}

string LetterCombination::Get()
{
    string res = string();
    int i = m_Length-1;
    
    // конвертируем числа 1..26 в буквы a..z
    while( (i >= 0) && (m_Set[i] > 0) )
    {
        res.insert(0, 1, char(96 + m_Set[i]));
        i--;
    }

    return res;
}

int main(int argc, char** argv)
{
    if (argc < 2) return -1;
    int cnt = atoi(argv[1]);

    LetterCombination lc = LetterCombination(cnt);

    lc.First();
    while (! lc.ThatsAll()) 
    {
        std::cout << lc.Get() << std::endl;
        lc.Next();
    }    

    std::cout << lc.Get() << std::endl;

    return 0;
}

codelord

Дата 18.1.2008, 18:58 (ссылка)

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

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 777
Регистрация: 7.5.2005
Где: ты моя темноглаза я где?!

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

как нить так smile

Код


#include <iostream>
#include <math.h>
using namespace std;

char start = 'a';
char end = 'z';
void show_mas ( char *mas, int len ) {
 for( int i = 0; i < len; ++i  ) {
   cout << *(mas + i ) << " ";
  }
 cout << endl;
}

void next( char *mas, int Len ) {
 int len = Len;
 while( --len >= 0 ) {
        if( *( mas + len ) < end ) {
          if( *( mas + len ) == start || *(mas + len + 1 ) == end ) {
                        memset( mas+len+1, 'a', Len-len-1 );
                }
          ++ *( mas + len );
          show_mas( mas, Len );
          break;
        }
     }
}
int main( int argc, char **argv ) {
 int len = 6;
 char *mas = new char[ len ];
 memset( mas , 'a', len );

 int iter = (int)pow( 26, len );
 for( int i = 0; i < iter ; ++i ) {
  next( mas, len );
 }
delete[] mas;
 return 0;
}

Это сообщение отредактировал(а) codelord - 18.1.2008, 18:59

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

Доступен поиск по исходным кодам в GOOGLE.
http://www.google.com/codesearch

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »