Слова из букв

Интересные алгоритмы, олимпиадные задачи, эффектные и эффективные решения. freepascal, delphi, c, c++, c#, java, javascript, perl, ruby, python, php, bash, wsh и т.д. Компиляторы, интерпретаторы, линкеры, отладчики, системы контроля версий и многое другое.

Модератор: xdsl

Слова из букв

Сообщение arengin 24 сен 2009, 09:55

Из набора букв (не менее 3 букв, не более 6) создать существующие слова из 3,4,5,6 символов если это возможно
Существующие слова находятся в файле slova.txt
Например:
Код: Выделить всё
код
дуб
соль
кот


Например на слово "сток"
Выводит
Код: Выделить всё
ток
кот
сок
сток


Если слов нет, то выводится "слов не найдено"

интересно посмотреть разные способы решений
чуть позже выложу свое решение на php...
Аватара пользователя
arengin
 
Сообщения: 6
Зарегистрирован: 24 сен 2009, 07:37
Откуда: Курьер Плюс
Полное имя: Ренжин А.В.

Re: Слова из букв

Сообщение vovan 24 сен 2009, 14:11

Код: Выделить всё
#include <stdio.h>
#include <stdlib.h>
#include <wchar.h>
#include <locale.h>

int comp(const void *a, const void *b)
{
    return *(wchar_t *)a-*(wchar_t *)b;
}

int main(void)
{
    setlocale(LC_ALL, "");
    FILE *fin;
    if ((fin=fopen("words.txt", "r"))==NULL) {
        wprintf(L"error open file\n");
        exit(1);
    }
    wchar_t st[100];
    wscanf(L"%ls", st);
    int len=wcslen(st);
    qsort(st, len, sizeof(wchar_t), comp);
    wchar_t wrd[100], word[100], *w1, *w2;
    int  cnt=0, ln;
    int i,j;
    while (1) {
        if (fwscanf(fin, L"%ls", word)<1) break;
        wcscpy(wrd, word);
        ln=wcslen(wrd);
        qsort(wrd, ln, sizeof(wchar_t), comp);
        j=0;
        w1=st;
        w2=wrd;
        while (*w1 && *w2)
            if (*w1==*w2) {
                w1++;
                w2++;
            } else w1++;
        if (!(*w2)) {
            wprintf(L"%ls\n", word);
            cnt++;
        }
    }
    if (!cnt) wprintf(L"Не найдено\n");
    fclose(fin);
}

Последний раз редактировалось vovan 25 сен 2009, 13:43, всего редактировалось 1 раз.
vovan
 
Сообщения: 27
Зарегистрирован: 07 фев 2009, 16:16
Полное имя: Щеколдин Владимир Викторович

Re: Слова из букв

Сообщение xdsl 25 сен 2009, 09:27

А можно прикрепить файл со словами? На несколько тысяч слов? Хочу поучаствовать в тюнинге решений. С разбором полетов.
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Слова из букв

Сообщение vovan 25 сен 2009, 13:22

во вложении 13 с небольшим тысяч слов
http://omploader.org/vMmYzcQ/words.txt.lzma - здесь около 100000, но без ограничения на размер в 6 символов
также забыл учесть минимально количество симвоов
Вложения
words.tar.bz2
(39.15 Кб) Скачиваний: 434
vovan
 
Сообщения: 27
Зарегистрирован: 07 фев 2009, 16:16
Полное имя: Щеколдин Владимир Викторович

Re: Слова из букв

Сообщение xdsl 25 сен 2009, 13:31

Спасибо! Взял вариант на 100000. Задачку усложняет кодировка UTF-8 для слов, но так даже интереснее будет.
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Слова из букв

Сообщение xdsl 29 сен 2009, 08:45

По преподавательской натуре разложу решение на части, с пояснялками.

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

Это вариант универсальный но не оптимальный. На больших наборах и длинном исходном слове устанем ждать, ибо n!*m - число возможных перестановок слова длиной N умножить на количество контрольных слов (кол-во сравнений).

Оптимизацию проведем в два этапа:
1. Исходный массив контрольных слов отсортируем, что резко ускорит поиск соответствия с m до log(2)m, и даже более, если перестановку сделать по уму.
2. Будем производить сравнение еще до конца формирования перестановки, чтобы отбросить заведомо негодные варианты.

... О! звонок на лекцию, пошел мучать студентов, допишу позже ;)
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Слова из букв

Сообщение xdsl 30 сен 2009, 10:23

... продолжаем

По привычке своей использую freepascal для решения задачи.
Решение буду выкладывать по частям, тем более, что отдельные части решения пригодятся и в других задачах.

В данном посте рассмотрим собственно реализацию самой перестановки, без сравнения полученных результатов с набором контрольных слов. Тем не менее, процедура перестановки сделана самодостаточной, переписывать ее в окончательном решении задачи не придется. Вместо этого сделаны две заглушки: check - будущая функция проверки очередной комбинации букв исходного слова на совпадение с контрольными словами, и out - будущая процедура вывода полученного совпадения.
Код: Выделить всё
{$mode objfpc}

Const Count=4; // Количество букв в слове
type TAlpha=word; // тип символа, выбран такой для последующей корректной работы с utf8
     TWord=ARRAY [1..Count] of TAlpha; // массив, содержащий исходное слово
     TCheck=(cNotFound,cFound,cPartialFound); // слово не найдено, найдено, частично совпадает

// заглушка для поиска совпадений
function Check(var _word:TWord; num:integer):TCheck;
begin
  result:=cFound;
  if Count=num then exit;
  if num>2 then begin
   if (_word[1]=3) and (_word[2]=2) then begin
    result:=cNotFound;
    exit;
   end;
  end;
  result:=cPartialFound;
end;

// заглушка для вывода
procedure Out(var _word:TWord; _count:integer);
  var i:integer;
begin
  for i:=1 to _count do write(_word[i]:4);
  writeln;
end;

// сама перестановка
procedure perest(var _word:TWord; Len:integer; Num:integer);
  procedure swap(var A,B:TAlpha);
   var C:word; begin c:=a; a:=b; b:=c; end;
  var i:integer; chk:TCheck;
begin
   chk:=check(_word,num);
   if chk=cFound then out(_word,num);
   if (Num=len) then exit;
   if chk<>cNotFound then perest(_word,len,num+1);
   for i:=num+1 to Count do begin
    swap(_word[num],_word[i]);
    perest(_word,len,num+1);
    swap(_word[num],_word[i]);
   end;
end;

var A:TWord;  { Обрабатываемое слово }
     i:integer;
begin
randomize;
// тестовое заполнение и проверка
for i:=1 to Count do begin
  a[i]:=i{random(10)};
  write(a[i]:4);
end;
writeln;
writeln;
perest(a,Count,1);
end.


Код перестановки был взят отсюда: ftp://shgpi.edu.ru/ftp.vc.shgpi/teaching/metod_materials/posobie_recur.pdf, стр. 13-14, и модифицирован под задачу.

продолжение следует ...
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Слова из букв

Сообщение Vladislav_133 30 сен 2009, 22:31

По-моему, рациональнее решать по другому. Берем слово из списка и проверяем на наличие букв и все. Во всяком случае это не противоречит условию, как мне кажется.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Слова из букв

Сообщение xdsl 01 окт 2009, 08:25

Vladislav_133 писал(а):По-моему, рациональнее решать по другому. Берем слово из списка и проверяем на наличие букв и все. Во всяком случае это не противоречит условию, как мне кажется.

Согласен. Для конкретно этой задачи - несомненно. Щеколдин именно такой способ решения предложил и реализовал во втором посте: https://shgpi.edu.ru/forum/viewtopic.php?p=1169#p1169. Жаль без комментариев ;). Тем не менее, свой вариант доведу до конца, т.к. он универсально решает задачу перестановки и может применяться во всех комбинаторных задачах, хотя по эффективности и будет серьезно проигрывать первому. Можно сказать, что решение Щеколдина - олимпиадное, а мое - инженерное (менее эффективное, но применимое к более широкому классу задач).

P.S. Пока два варианта, кто предложит еще?
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

Re: Слова из букв

Сообщение xdsl 07 окт 2009, 13:14

Выдалось немного свободного времени, довел свой вариант решения до конца. Однако возникла проблема, которую элегантно решить никак не выходит. Проблема в utf8, а именно - в однобайтовых символах. Например слово - "сон-трава". Однобайтовый знак "-" портит все. Перестановка становится нетривиальной задачей, либо требует предварительного преобразования строки, а при сравнении - обратного пребразования. Таким образом, скорость, выигранная из-за наличия только одной сортировки набора слов полностью "съедается" преобразованиями и решение Шеколдина лидирует уже не только на длинных словах, но и на коротких тоже.
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.


Вернуться в Алгоритмизация и программирование

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 0

cron