:: Игры Разума
Комбинаторика
Вячеслав Клепинин
Автор

Сообщений: 1597
Откуда: Санкт-Петербург
Дата регистрации: 26.03.2004
Что-то тихо стало в этом топике. Поэтому предлагаю задачку по комбинаторике.

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

Строительн|ая|ую|ой компани|я|ю|ей|и

Количество слов в словосочетании не ограничено.
Нужно получить массив, содержащий все возможные комбинации словоформ - но без перестановки слов:

1. Строительная компания
2. Строительная компанию
3. Строительная компанией
4. Строительная компании
5. Строительную компания
6. Строительную компанию
7. Строительную компанией
8. Строительную компании
9. Строительной компания
10. Строительной компанию
11. Строительной компанией
12. Строительной компании

Если кто поможет с алгоритмом, тому - будет большое спасибо!
Ну а ежели кто даст код - то моя благодарность будет безгранична!



Исправлено 4 раз(а). Последнее : Вячеслав Клепинин, 04.10.07 14:59
Ratings: 0 negative/0 positive
Re: Комбинаторика
PaulWist

Сообщений: 14601
Дата регистрации: 01.04.2004
Слава, что-то не понятно помимо имен существительных ты так же изменяешь окончание у прилагательного и это вроде противоречит постановки задачи

Цитата:
Каждое слово в словосочетании (все слова - имена существительные)

А так на первый взгляд для имени существителього надо иметь все окончания, ну и дальше дело техники, другое дело если надо составить осмыссленные сочетания, тогда это действительно задачка.


------------------
Есть многое на свете, друг Горацио...
Что и не снилось нашим мудрецам.
(В.Шекспир Гамлет)
Ratings: 0 negative/0 positive
Re: Комбинаторика
Вячеслав Клепинин
Автор

Сообщений: 1597
Откуда: Санкт-Петербург
Дата регистрации: 26.03.2004
Паша, да, это моя опечатка. Не только существительные.
Но я застрял именно для случая, когда слов в словосочетании несколько (и заранее неизвестно, сколько).
Ratings: 0 negative/0 positive
Re: Комбинаторика
AleksM

Сообщений: 17881
Дата регистрации: 11.11.2003
ИМХО
1. Кол-во слов в словосочетании (GETWORDCOUNT())
2. Разбить словосочетание на слова
3. Кол-во окончаний для слова ((GETWORDCOUNT()))
4. И комбинируем, через вложенные циклы, например, а можно и через SELECTы


------------------
Лучше переесть, чем недоспать.
Не спеши, а то успеешь.
Ratings: 0 negative/0 positive
Re: Комбинаторика
Вячеслав Клепинин
Автор

Сообщений: 1597
Откуда: Санкт-Петербург
Дата регистрации: 26.03.2004
Саша, а вот про пункт 4 можно поподробнее?
Первые три пункта я уже давно выполнял, а потом "застрял" - именно на четвёртом.
Вот мой код:
lcMain = 'Пивоваренн|ая|ой|ую|ые компани|я|и|ей|ю Балтик|а|е|у|ой'
lnWordCount = GETWORDCOUNT(lcMain, ' ')
lnIndex = 1
FOR i = 1 TO lnWordCount
lcWord = GETWORDNUM(lcMain, i, ' ')
DIMENSION laWord[lnIndex, 2]
lnExtCount = GETWORDCOUNT(lcWord, '|')
IF lnExtCount = 1 && Слово не содержит окончаний (нет словоформ)
laWord[lnIndex, 1] = lcWord
laWord[lnIndex, 2] = i
lnIndex = lnIndex + 1
ELSE && В слове есть словоформы
lcBase = GETWORDNUM(lcWord, 1, '|')
FOR j = 2 TO lnExtCount
DIMENSION laWord[lnIndex, 2]
laWord[lnIndex, 1] = lcBase + GETWORDNUM(lcWord, j, '|')
laWord[lnIndex, 2] = i
lnIndex = lnIndex + 1
ENDFOR
ENDIF
ENDFOR
CREATE CURSOR tttt (word c(50), pn i)
INSERT INTO tttt FROM ARRAY laWord
SELECT tttt
GO TOP
BROWSE
USE IN tttt

Поле pn содержит порядковый номер слова в словосочетании.



Исправлено 1 раз(а). Последнее : Вячеслав Клепинин, 04.10.07 16:25
Ratings: 0 negative/0 positive
Re: Комбинаторика
ssa

Сообщений: 12999
Откуда: Москва
Дата регистрации: 23.03.2005
Create Cursor main (word1 v(15), word2 v(15))
Insert into main values ('Строительн', 'компани')
Create Cursor suff1 (suff c(10))
Insert into suff1 values ('ая')
Insert into suff1 values ('ую')
Insert into suff1 values ('ой')
Create Cursor suff2 (suff c(10))
Insert into suff2 values ('я')
Insert into suff2 values ('ю')
Insert into suff2 values ('ей')
Insert into suff2 values ('и')
Select word1+suff1, word2+suff2 from main m, (Select s1.suff as suff1, s2.suff as suff2 from suff1 s1, suff2 s2) s
Идея понятна?


------------------
Лень - это неосознанная мудрость.
Ratings: 0 negative/0 positive
Re: Комбинаторика
leonid

Сообщений: 3202
Откуда: Рига
Дата регистрации: 03.02.2006
Извиняюсь, писал на шестерке, так что функция word_num собственная.
* Не более девяти слов
lcMain = 'Пивоваренн|ая|ой|ую|ые компани|я|и|ей|ю Балтик|а|е|у|ой'
local ar1(1), ar2(1), m.cnt, m.cnt2, m.fld, m.jn, m.sl
m.cnt=word_num(lcMain, " ", @ar1)
m.fld=""
m.jn=""
for i=1 to m.cnt
m.cur_name="cur"+allt(str(i))
create cursor (m.cur_name) (f1 C(30))
m.cnt2=word_num(ar1(i), "|", @ar2)
for j=2 to m.cnt2
insert into (m.cur_name) values (ar2(1)+ar2(j))
next
m.fld=m.fld+","+m.cur_name+".f1 as f"+allt(str(i))
m.jn=m.jn+","+m.cur_name
next
m.sl="select "+substr(m.fld,2)+" from "+substr(m.jn,2)+" into cursor result"
&sl
browse
function word_num
lparameter m.txt, m.razd, ar1
if len(m.razd)=0
return 0
endif
local m.cn1, m.cn2, m.st1, m.txt2, m.ln, m.i
m.cn1=occurs(m.razd,m.txt)
if m.cn1=0
if empty(m.txt)
return 0
else
dimension ar1(1)
ar1(1)=m.txt
return 1
endif
else
m.cn2=0
m.txt2=m.razd+m.txt+m.razd
m.ln=len(m.razd)
for m.i=1 to m.cn1+1
m.st1=substr(m.txt2,at(m.razd,m.txt2,m.i)+m.ln,at(m.razd,m.txt2,m.i+1)-at(m.razd,m.txt2,m.i)-m.ln)
m.st1=allt(m.st1)
if !empty(m.st1)
m.cn2=m.cn2+1
dimension ar1(m.cn2)
ar1(m.cn2)=m.st1
endif
next
return m.cn2
endif
Ratings: 0 negative/0 positive
Re: Комбинаторика
AleksM

Сообщений: 17881
Дата регистрации: 11.11.2003
И от меня (писал в 9-ке стилем 7-ки)
LOCAL lcStr, lnWords, lnWord, lnExts, lnExt
LOCAL lcWord, lcExt
lcStr = "Строительн|ая|ую|ой компани|я|ю|ей|и Дальсантехпедал|ь"
lnWords = GETWORDCOUNT(lcStr," ")
LOCAL ARRAY laWords(lnWords)
CREATE CURSOR cWords (id i, Word c(100))
CREATE CURSOR cExts (WordID i, ExtID i, Ext c(10))
FOR lnWord = 1 TO lnWords
lcWord = GETWORDNUM(lcStr, lnWord, " ")
INSERT INTO cWords VALUES (lnWord, LEFT(lcWord,AT("|",lcWord)-1))
lnExts = GETWORDCOUNT(lcWord,"|")
FOR lnExt = 2 TO lnExts
lcExt = GETWORDNUM(lcWord, lnExt, "|")
INSERT INTO cExts VALUES (lnWord, lnExt, lcExt)
NEXT
NEXT
SELECT a.ID, ALLTRIM(a.Word)+ALLTRIM(b.Ext) as Word ;
FROM cWords a ;
INNER JOIN cExts b ON b.WordID=a.ID ;
INTO CURSOR cWordExts
SELECT a.Word ;
FROM cWordExts a ;
WHERE a.Id=1 ;
INTO CURSOR cWordComb
FOR lnWord = 2 TO lnWords
SELECT ALLTRIM(a.Word) + " " + ALLTRIM(b.Word) as Word ;
FROM cWordComb a ;
INNER JOIN cWordExts b ON b.ID=lnWord ;
INTO CURSOR cWordComb
NEXT
BROWSE


------------------
Лучше переесть, чем недоспать.
Не спеши, а то успеешь.
Ratings: 0 negative/0 positive
Re: Комбинаторика
AleksM

Сообщений: 17881
Дата регистрации: 11.11.2003
Слав, а мож padeg.dll лучше?


------------------
Лучше переесть, чем недоспать.
Не спеши, а то успеешь.
Ratings: 0 negative/0 positive
Re: Комбинаторика
AleksM

Сообщений: 17881
Дата регистрации: 11.11.2003
Дык в 6-ке в foxtools.fll эти ф-ции есть


------------------
Лучше переесть, чем недоспать.
Не спеши, а то успеешь.
Ratings: 0 negative/0 positive
Re: Комбинаторика
leonid

Сообщений: 3202
Откуда: Рига
Дата регистрации: 03.02.2006
Да, есть вроде, но у меня она немного другая - сразу массив создает, на мой взгляд удобнее.
Ratings: 0 negative/0 positive
Re: Комбинаторика
Вячеслав Клепинин
Автор

Сообщений: 1597
Откуда: Санкт-Петербург
Дата регистрации: 26.03.2004
Про padeg.dll - у меня её нету...
В общем, решение нашёл вот такое, с использованием рекурсии. Позволяет указывать от одного до произвольного количества слов, каждое из которых может иметь, а может и не иметь словоформ.

PUBLIC gaWord[1,2]
lcMain = 'Это пивоваренн|ая|ой|ую компани|я|и|ей|ю Балтик|а|е|у|ой'
lnWordCount = GETWORDCOUNT(lcMain, ' ')
lnIndex = 1
FOR i = 1 TO lnWordCount
lcWord = GETWORDNUM(lcMain, i, ' ')
DIMENSION gaWord[lnIndex, 2]
lnExtCount = GETWORDCOUNT(lcWord, '|')
IF lnExtCount = 1 && Слово не содержит окончаний (нет словоформ)
gaWord[lnIndex, 1] = lcWord
gaWord[lnIndex, 2] = i
lnIndex = lnIndex + 1
ELSE && В слове есть словоформы
lcBase = GETWORDNUM(lcWord, 1, '|')
FOR j = 2 TO lnExtCount
DIMENSION gaWord[lnIndex, 2]
gaWord[lnIndex, 1] = lcBase + GETWORDNUM(lcWord, j, '|')
gaWord[lnIndex, 2] = i
lnIndex = lnIndex + 1
ENDFOR
ENDIF
ENDFOR
CREATE CURSOR result (word c(50))
GetNewWordForm("", 1)
SELECT result
GO TOP
BROWSE
USE IN result
FUNCTION GetNewWordForm(tcWord, tnIndex)
LOCAL i, lnALen, llSuccess
lnALen = ALEN(gaWord, 1)
FOR i = 1 TO lnALen
IF gaWord[i, 2] = tnIndex
llSuccess = .t.
GetNewWordForm(tcWord + " " + ALLTRIM(gaWord[i,1]), gaWord[i, 2] + 1)
ENDIF
ENDFOR
IF !llSuccess
INSERT INTO result (word) VALUES (tcWord)
ENDIF

Нужно ещё немного доработать напильником, так как результат мне нужен именно в массиве, а не в курсоре.
Но, главное, не сложно и работает правильно!

Всем спасибо!
Ratings: 0 negative/0 positive
Re: Комбинаторика
ssa

Сообщений: 12999
Откуда: Москва
Дата регистрации: 23.03.2005
sStr='Это пивоваренн|ая|ой|ую компани|я|и|ей|ю Балтик|а|е|у|ой'
Words=Getwordcount(sStr)
SelFields1 = ''
SelFields2 = ''
Suffx = ''
Create Cursor Main (w1 v(15))
Append Blank
For i=1 To Words
lcI = Ltrim(Str(i))
Create Cursor ('suff'+lcI) (suff c(10))
WordFull=Getwordnum(sStr, i)
Word=Getwordnum(WordFull, 1,'|')
If i>1
Alter Table main Add Column ('w'+lcI) v(15)
Endif
Replace ('w'+lcI) With Word in main
For j=1 To Getwordcount(WordFull, '|')
Insert Into ('suff'+lcI) Values (Iif(j>1,Getwordnum(WordFull, j, '|'), ''))
Next
SelFields1 = SelFields1 + Iif(i>1, ',','')+'w'+lcI+'+'+'suff'+lcI
SelFields2 = SelFields2 + Iif(i>1, ',','')+'s'+lcI+'.suff as suff'+lcI
Suffx = Suffx + Iif(i>1, ',','')+'suff'+lcI+' s'+lcI
Next
*ssa* Select @SelFields1 from main m, (Select @SelFields2 from @Suffx) s
ccc ='Select '+SelFields1+' from main m, (Select '+SelFields2+' from '+Suffx+') s' && сюда дописать into array <Array>
&ccc
Вот-с, собственно. Для вывода в массив достаточно выполнить действия, описанные в коментарии.


------------------
Лень - это неосознанная мудрость.
Ratings: 0 negative/0 positive


Извините, только зарегистрированные пользователи могут оставлять сообщения в этом форуме.

On-line: 5 (Гостей: 5)

© 2000-2024 Fox Club 
Яндекс.Метрика