Страница 1 из 1

Слова из букв

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


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


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

интересно посмотреть разные способы решений
чуть позже выложу свое решение на php...

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

СообщениеДобавлено: 24 сен 2009, 14:11
vovan
Код: Выделить всё
#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);
}


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

СообщениеДобавлено: 25 сен 2009, 09:27
xdsl
А можно прикрепить файл со словами? На несколько тысяч слов? Хочу поучаствовать в тюнинге решений. С разбором полетов.

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

СообщениеДобавлено: 25 сен 2009, 13:22
vovan
во вложении 13 с небольшим тысяч слов
http://omploader.org/vMmYzcQ/words.txt.lzma - здесь около 100000, но без ограничения на размер в 6 символов
также забыл учесть минимально количество симвоов

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

СообщениеДобавлено: 25 сен 2009, 13:31
xdsl
Спасибо! Взял вариант на 100000. Задачку усложняет кодировка UTF-8 для слов, но так даже интереснее будет.

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

СообщениеДобавлено: 29 сен 2009, 08:45
xdsl
По преподавательской натуре разложу решение на части, с пояснялками.

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

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

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

... О! звонок на лекцию, пошел мучать студентов, допишу позже ;)

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

СообщениеДобавлено: 30 сен 2009, 10:23
xdsl
... продолжаем

По привычке своей использую 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, и модифицирован под задачу.

продолжение следует ...

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

СообщениеДобавлено: 30 сен 2009, 22:31
Vladislav_133
По-моему, рациональнее решать по другому. Берем слово из списка и проверяем на наличие букв и все. Во всяком случае это не противоречит условию, как мне кажется.

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

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

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

P.S. Пока два варианта, кто предложит еще?

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

СообщениеДобавлено: 07 окт 2009, 13:14
xdsl
Выдалось немного свободного времени, довел свой вариант решения до конца. Однако возникла проблема, которую элегантно решить никак не выходит. Проблема в utf8, а именно - в однобайтовых символах. Например слово - "сон-трава". Однобайтовый знак "-" портит все. Перестановка становится нетривиальной задачей, либо требует предварительного преобразования строки, а при сравнении - обратного пребразования. Таким образом, скорость, выигранная из-за наличия только одной сортировки набора слов полностью "съедается" преобразованиями и решение Шеколдина лидирует уже не только на длинных словах, но и на коротких тоже.