Составить из букв комбинации

[sedikpoll]

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

дома -то что нам нужно
омад
дамо
мода -то что нам нужно

Каким способом можно перемешивать имеющеюся буквы?

[SLEDopit]

Каким способом можно перемешивать имеющеюся буквы?

первое, что пришло на ум:

Код: Выделить всё

 $ echo {a,b,c}{a,b,c}{a,b,c} | tr ' ' '\n' | grep a | grep b | grep c
abc
acb
bac
bca
cab
cba

а вот извлечь из этого нужные варианты, это, наверное, только со словарем если.

[grAndrew2]

Я когда-то решал подобную задачу - взял словарь из старого ispell (подойдет даже скомпиленный), там где-то 300к слов без словоформ, кажется, и каждое слово прогонял на предмет grep'пуемости по "^\$WORD$"
т.е. предложенный выше скрипт надо загнать в переменную WORDS=$( ... ) и for word in WORDS do grep... далее разберетесь

[Skyb]

а регекс в баше нет?

[drBatty]

а регекс в баше нет?

есть. ~=

т.е. предложенный выше скрипт надо загнать в переменную WORDS=$( ... ) и for word in WORDS do grep... далее разберетесь

возможно, шаблон /ab|bc/ будет быстрее, чем 2 шаблона /ab/ и /ba/

[Skyb]

Ну а почему бы и не воспользоваться им

[drBatty]

Ну а почему бы и не воспользоваться им smile.gif

потому, что я ерунду сморозил: нам нужно найти ЧТО ИЗ НИХ подходит, а с таким шаблоном я найду много совпадений. Это не совсем то:

дома -то что нам нужно
омад
дамо
мода -то что нам нужно

тут ответ будет ДА. И что? ну в принципе можно вырезать это sed -rn 's/.*(ab|ba).*/\1/p' , а потом uniq, но это будет наверняка дольше.
по моим опытам:

Код: Выделить всё

doc@bx:~/test$ time -p sed -rn '/оббе/{ p;q  }' ru_RU_UTF8.dic
оббегавший/A
real 0.45
user 0.27
sys 0.01
doc@bx:~/test$ time -p grep -q '/оббе/' ru_RU_UTF8.dic
real 0.89
user 0.52
sys 0.03
doc@bx:~/test$ time -p grep  '/оббе/' ru_RU_UTF8.dic
real 0.77
user 0.51
sys 0.03
doc@bx:~/test$ time -p grep -q '/оббе/' ru_RU_UTF8.dic
real 0.81
user 0.54
sys 0.02
doc@bx:~/test$ time -p sed -rn '/оббе/{ p;q  }' ru_RU_UTF8.dic
оббегавший/A
real 0.45
user 0.27
sys 0.01
doc@bx:~/test$ time -p sed -rn '/оббе/{ p;  }' ru_RU_UTF8.dic
оббегавший/A
оббегаемый/A
оббегание/J
оббегать/LMPR
оббегающий/A
real 0.93
user 0.56
sys 0.02

быстрее всего

sed -rn '/оббе/q1'
результат $? равен 1, если нашлось "оббе". оббе впервые встречается в середине словаря.

[watashiwa_daredeska]

Если нужно по словарю искать слова, которые состоят из заданных букв, то я бы вообще пошел по другому пути.
1). Обработать словарь в вид: ключ = отсортированные буквы слова => значение. Например: адмо->мода, адмо->дома, аабббо->баобаб.
2). Заданные буквы также отсортировать и уже искать в словаре по получившемуся ключу.

Один поиск по отсортированному словарю — на порядки быстрее n! линейных поисков :) Может быть, не совсем для чистой командной строки решение, но в самом простом случае sqlite3 можно дёргать и из шелл-скрипта.

[drBatty]

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

я не знаю... вроде скорость в тестах и так достаточна (я-же не знаю исходных данных). Но я-бы бы пошёл по третьему пути: конечно я отсортировал-бы словарь, но потом его порезал скажем на 1000 кусков (33буквы * 33 == 1089), и выбрал-бы кусок словаря по первым двум буквам, скорость увеличится в ~1000 раз (отрезать 2 буквы и выбрать словарь - это быстро, и O(1)) простенькое хеширование и сработает неплохо.

На практике я помнится считал CRC32 от слова, а словарь порезал на 256 частей, а то у меня куски по вышеописанному методу очень разные получились - не эффективно, с CRC32 оказалось быстрее. Конечно подошла-бы любая хеш функция, вот только у меня был bash, cksum, и sed :(

А вообще использовать EXT3/4 как БД оказалось очень эффективно и удобно: ключ==имя файла, данные внутри. Зачем мне деревья из БД, если они уже в ФС имеются? И неплохие, кстати.

Кстати, хотел MySQL, но очень медленно из bash'а запросы делать, а собирать запросы в пачки очень сложно было...

[SLEDopit]

А вообще использовать EXT3/4 как БД оказалось очень эффективно и удобно: ключ==имя файла, данные внутри.

Не согласен. Как минимум на ext такая база ограничена количеством инодов.

Код: Выделить всё

 $ df -i /home
Filesystem            Inodes   IUsed   IFree IUse% Mounted on
/dev/sdb7             196800    3096  193704    2% /home

200 тысяч, как то не густо (:
Да и выборка, особенно в случае вложенных запросов, будет крайне неэффективной.

но очень медленно из bash'а запросы делать,

в смысле медленно?
echo "SELECT something FROM table;" | mysql -uuser -ppassword database
чего тут медленного то? несекурно, да. но не медленно.

собирать запросы в пачки очень сложно было...

да ладно, легким движением sed любой текстовый файл превращается в sql файл (:

[drBatty]

Не согласен. Как минимум на ext такая база ограничена количеством инодов.

ну и что? любая БД ограничена.

200 тысяч, как то не густо (:

мне хватило с избытком - уже на 70 000 узлах диск был заполнен.

Да и выборка, особенно в случае вложенных запросов, будет крайне неэффективной.

??? у меня есть MySQL, я не идиот. А для простых запросов эффективность в разы выше MySQL.

echo "SELECT something FROM table;" | mysql -uuser -ppassword database
чего тут медленного то? несекурно, да. но не медленно.

попробуйте.

да ладно, легким движением sed любой текстовый файл превращается в sql файл (:

а я, можно подумать, QBASIC'ом собирал ;)
bash вообще медленный, и у меня bash был в самом конце:
s/.*/mysql < tmp.sql/e
получается быстрее, чем
s/..../echo "SELECT..." | mysql/e
(на самом деле, труба | это тоже файл, а тут две трубы - sed тоже через пайп передаёт, s//команда/w PIPE /bin/sh)

PS: верю. в других случаях будет по другому, в моём было именно так. а тут похожий случай.

PPS: а я не кричал, что БД - маздай :-) просто одно из специализированных решений. Мне самому весело было смотреть на каталог размером в сотни метров (именно каталог, а не файлы в нём).

[SLEDopit]

попробуйте.

ну, я просто этим постоянно пользуюсь (:

PPS: а я не кричал, что БД - маздай :-)

Мда, что-то я в полудреме все немного не так понял. Мои извинения.