Алгоритм полного перебора вариантов. Нужна помощь.

11.07.04

✎

13:07

Есть список значений. Нужно добавить в этот список все значения типа так: зн1+Зн2, зн1+зн3, зн2+зн3,зн2+зн1,зн1+зн2+зн3... Мне как-то NS давал такой алгоритм, но я его потерял :).

1 SnarkHunter

11.07.04

✎

15:00

На форуме есть поиск...
Очень сложная задачка на сортировку массива списков значений.

2 Матрейя

11.07.04

✎

15:13

1. Здесь нет такого алгоритма.

4 Глазья

11.07.04

✎

17:06

Зырк...Зырк...

7 mextier

12.07.04

✎

01:45

http://algolist.manual.ru/maths/combinat/permutations.php

8 Матрейя

12.07.04

✎

03:17

7. Спасибо.

9 Матрейя

14.07.04

✎

13:54

NS, вспомни плиз свой вариант. Он самый лучший из всех, что я видел.

10 NS

14.07.04

✎

18:53

Самый быстрый - без рекурсии на массиве...
Тебе нужно в список поместить все возможные значения? Или всё таки рюкзак (подобрать требуюмую сумму)?

11 Матрейя

14.07.04

✎

23:24

Значения - текст. То есть нужно перебрать все возможные варианты комбинаций слов. От единичных значений до полного перебора возможных перестановок слов в тексте.

12 NS

14.07.04

✎

23:27

(11) Для чего такая задача?
Если ты хочешь сравнить две строки по словам - делать надо совсем по другому....

13 Матрейя

14.07.04

✎

23:37

12. Задача такая:
1.есть сторока поиска (слово, несколько слов, слог, допускаются произвольные сочетания русского и транслита).
2. Есть список значений (или ТЗ), где стока поиска разбивается на варианты: полная строка, сочетания слов, слова, слоги, слова с подстановками из другого алфавита. Этот список формируется по запросу. То есть изначально только вариант полной стороки поиска. Затем делается запрос SQL .... where %like=(КлючПоиска). Если рекордсет пустой - в список значений добавляется вариант с более мягкими условиями и т.д. То есть поиск по релевантности.
3. Результат рекурсивного запроса - это фильтр для ИспользоватьСписокЭлементов(Фильтр)

14 NS

14.07.04

✎

23:53

похоже правда перемудрил... но...
//*******************************************
Процедура Сформировать()
перем а[100],в[100],с[100];
Кол=3;
Для м=1 по кол цикл
в[м]=1; //для выводы результатов
а[м]=""+м;//массив строк
Конеццикла;
сч=0;
пока сч<=Кол цикл
стр="";
Для м=1 по Кол цикл
стр=стр+а[в[м]];
КонецЦикла;
Для м=1 по кол цикл
с[м]=0;
КонецЦикла;
флаг=0;
Для м=1 по кол цикл
зн=с[в[м]]+1;
Если зн>1 тогда
флаг=1;
прервать;
КонецЕсли;
с[в[м]]=зн;
КонецЦикла;
Если флаг=0 Тогда
сообщить(стр);
КонецЕсли;
в[1]=в[1]+1;
Сч=1;
Пока в[сч]>Кол цикл
в[сч]=1;
сч=сч+1;
Если сч>кол Тогда
прервать;
иначе
в[сч]=в[сч]+1;
КонецЕсли;
конеццикла;
КонецЦикла;
КонецПроцедуры

15 Матрейя

15.07.04

✎

00:08

Чет миранда глючит... Каждое слово к аналогу - это как? Словарь составлять?

16 NS

15.07.04

✎

00:20

перем а[100],в[100],с[100];
Кол=6;
Для м=1 по кол цикл
в[м]=1; //для вывода результатов
а[м]=""+м;//массив строк
Конеццикла;
сч=0;
пока сч<=Кол цикл
стр="";
Для м=1 по Кол цикл
стр=стр+а[в[м]];
КонецЦикла;
Для м=1 по кол цикл
с[м]=0;
КонецЦикла;
флаг=0;
Для м=1 по кол цикл
Если с[в[м]]=1 тогда
флаг=1;
прервать;
КонецЕсли;
с[в[м]]=1;
КонецЦикла;
Если флаг=0 Тогда
сообщить(стр);
КонецЕсли;
в[1]=в[1]+1;
Сч=1;
Пока в[сч]>Кол цикл
в[сч]=1;
сч=сч+1;
Если сч>кол Тогда
прервать;
иначе
в[сч]=в[сч]+1;
КонецЕсли;
конеццикла;
КонецЦикла;
Так чище - но чё-то мне этот алгоритм не нравится... сейчас быстрее напишу....

17 NS

15.07.04

✎

00:21

Да, словарик...
Группируется по аналогам, и если слово входит в группу - то беретсяч вместо него главное (первое) из группы....
Есно перед этим слова все приводятся к одному регистру.

18 romix

15.07.04

✎

00:28

Пары значений?

Если есть массив ABCD, то все пары значений перебираются так:

AB-AC-AD
BC-BD
CD

Для ABCDE вот так:

AB-AC-AD-AE
BC-BD-BE
CD-CE
DE

Если нужно для сортировки, то это имхо самый простой алгоритм.

19 NS

15.07.04

✎

00:31

Нет, не пары, а есно все перестановки... пары - слишком просто....
Для а=1 по кол-1 цикл
Для б=а+1 по кол цикл
сообшить(""+а+б);
КонецЦикла;
КонецЦикла;

20 Матрейя

15.07.04

✎

00:33

18. телефон в базе = nokia, в поиске можно набрать нокия или "нокia чихлы"

21 NS

15.07.04

✎

00:35

Значит в словарике - на нокию - много соответствий...
Либо перед поиском в таблице соответствий - далается некое крутое преобразование (приведение) слов... круче, чем ВРЕГ...
Но принцип везде одинаковый.

22 Матрейя

15.07.04

✎

00:38

21. Критична скорость формирования вариантов для like. Не более 2 сек должно для любых строк с максимальной эфективностью отсечений маловероятных вариантов.

23 romix

15.07.04

✎

00:48

(20) Безусловно клейте на товар коды. Какие еще "нокиа чехлы" или "nokia чехлы"? Только код! Или на всем товаре есть штрихкод. Даже не пытайтесь подстраиваться под такие вещи! Иначе все недостачи по складу повесят на вас, и все задержки с отгрузкой товара и/или отрицательные остатки повесят тоже на вас.

24 NS

15.07.04

✎

01:35

Готов окончательный вариант поиска всех перестановок:
Процедура Сформировать()
перем а[100],в[100],с[100];
Кол=5;
Для м=1 по кол цикл
в[м]=кол-м+1; //для вывода результатов
а[м]=""+м;//массив строк
с[м]=1; //Занятые значения
Конеццикла;
Флаг=1;
пока Флаг=1 цикл
стр="";
Для м=1 по Кол цикл
стр=стр+а[в[м]];
КонецЦикла;
сообщить(стр);
с[в[1]]=0;
Для м=2 по Кол цикл
Флаг=0;
с[в[м]]=0;
Для к=в[м]+1 по Кол цикл
Если с[к]=0 Тогда
флаг=1;
с[к]=1;
в[м]=к;
прервать;
КонецЕсли;
КонецЦикла;
Если Флаг=1 Тогда
прервать;
КонецЕсли;
КонецЦикла;
Если флаг=1 Тогда
сч=1;
Для к=1 по м-1 цикл
пока с[сч]=1 цикл
сч=сч+1;
КонецЦикла;
в[м-к]=сч;
с[сч]=1;
КонецЦикла;
КонецЕсли;
КонецЦикла;
КонецПроцедуры

25 romix

15.07.04

✎

01:52

Если нужен быстрый поиск по словам, входяшим в наименование, то нужен словарик.
Структура таблицы: колонки Слово (индексируемая) и Ссылка (ссылка на Номенклатуру).

"нокia" никто не напишет - все слово пойдет одним языком.
"чихлы" тоже никто не напишет (подстраиваться под ошибки при использовании русского языка - не дело).

26 Матрейя

15.07.04

✎

10:29

23. Штрих-код, код - все это есть. Просто элитные программисты используют элитные фенечки :)
24. Спасибо, NS, наверное подойдет.

27 romix

15.07.04

✎

23:43

(26) Ну, блин, исследователи :-)