Вход | Регистрация
 

Помогите разработать оптимальный алгоритм

Помогите разработать оптимальный алгоритм
Я
   ДНН
 
04.02.21 - 11:10
Есть заказы. У них есть доп. строковое поле, где указываются номера связанных заказов. Номера указываются без префиксов, например вместо КТ0000031 просто указывают 31. Через запятую можно указать несколько номеров. Номера связанных заказов обычно заполняют только в одном заказе.

Например:
Заказ КТ0000031, связанные заказы не заполнено.
Заказ КТ0000032, связанные заказы не заполнено.
Заказ КТ0000033, связанные заказы: 31, 32.

В итоге все эти 3 заказа считаются связанными.

Еще пример:
Заказ КТ0000041, связанные заказы: 42.
Заказ КТ0000042, связанные заказы не заполнено.
Заказ КТ0000043, связанные заказы: не заполнено.

Заказ КТ0000041 и КТ0000042 считаются связанными, КТ0000043 - нет.

Искать связанные заказы нужно не во всех заказах базы, а они уже приходят в неком массиве по несколько штук. Искать нужно только среди них. Для первого примера это массив с ссылками на заказы КТ0000031, КТ0000032, КТ0000033.
Для второго примера массив с ссылками на заказы КТ0000041, КТ0000042, КТ0000043.

В результате из входящего массива в первом примере вернется тот же самый массив.
А во втором примере вернутся 2 массива. В первом ссылки на заказы КТ0000041 и КТ0000042. Во втором на КТ0000043.

Понятно что можно тупо перебрать их по несколько раз, но хочется какой-то красивый алгоритм. А главное оптимальный.
   Жан Пердежон
 
1 - 04.02.21 - 11:21
Для каждого заказа сохраняй (в тз или в базе) код/ключ связи - ссылку на один из заказов, ну и заполняй соответственно с учётом транзитивной зависимости
   acht
 
2 - 04.02.21 - 11:23
> главное оптимальный
По каким критериям? 

Перебираешь свои заказы, если у заказа заполнено поле зависимости, то скидываешь в результат его самого и все заказы из поля зависимости. По необходмости давишь повторы.
   ДНН
 
3 - 04.02.21 - 11:26
(2) > По каким критериям?
По скорости выполнения
   Bigbro
 
4 - 04.02.21 - 11:27
а если у 42 заполнено 43, а у 43 заполнено 31?
   ДНН
 
5 - 04.02.21 - 11:29
(4) > а если у 42 заполнено 43, а у 43 заполнено 31?
То 41, 42 и 43 считаются связанными. На 31 пофиг, потому что его не было в первоначальном массиве.
   polosov
 
6 - 04.02.21 - 11:29
(0) Добавить РС в котором связать заказы общим УИДом.
   Вафель
 
7 - 04.02.21 - 11:35
а вот в 1 примере 31 и 32 связаны между собой?
   Вафель
 
8 - 04.02.21 - 11:36
а так добавить регистр связанные документы и измерениями Док1, Док2
   ДНН
 
9 - 04.02.21 - 11:38
(7) > а вот в 1 примере 31 и 32 связаны между собой?
Да, я же писал в условии:
В итоге все эти 3 заказа считаются связанными.
   Вафель
 
10 - 04.02.21 - 11:38
разбивать массив на связные массивы - поиском в ширину
   mistеr
 
11 - 04.02.21 - 11:40
(0) >хочется какой-то красивый алгоритм. А главное оптимальный

А ты сдерживай такие желания, пока не появится реальная необходимость. Если в массиве "несколько штук", то "тупо перебрать их" вполне годный алгоритм.
   Вафель
 
12 - 04.02.21 - 11:40
(10) п.1 те берем 1 заказ, смотрим все связные с ним
п.2 берем все заказы связные с заказами п.1 кроме них самих
п.3 итд
   mistеr
 
13 - 04.02.21 - 11:45
А вообще это задача кластеризации. Разбить исходное множество на непересекающиеся подмножетсва, образующие покрытие исходного.

Или можно в терминах графов поставить задачу. Поиск компонент связности на неориентированном графе.
   Bigbro
 
14 - 04.02.21 - 11:47
ну вообще говоря в чистом виде разбиение на непересекающиеся подмножества
   ДНН
 
15 - 04.02.21 - 11:51
Проблема еще в том, что номер заказа с префиксом и нулями, а в связанных заказах без. То есть может быть номер КТ0000019, а в связанных указано 9. В этом случае они не должны связаться. Тупо СтрНайти нельзя использовать, нужно предварительно подготовить какую-то структуру данных, где ссылка и номер без префикса для точного поиска
   mistеr
 
16 - 04.02.21 - 11:52
(15) Наоборот, нужно "9" преобразовать в ссылку, а потом уже прогонять алгоритм.
   Bigbro
 
17 - 04.02.21 - 11:52
(15) ты не умеешь дополнять нулями слева строку до нужной длины? серьезно?
   ДНН
 
18 - 04.02.21 - 11:53
(16) логично
   ДНН
 
19 - 04.02.21 - 11:54
(17) там не только нули
   Bigbro
 
20 - 04.02.21 - 11:55
ну давай примеры тогда своих номеров, где не только нули
и принцип по которому определять их.
   Вафель
 
21 - 04.02.21 - 11:56
(15) при записи документа обновляй регистр. ссылки ищи сам, запросом
   ДНН
 
22 - 04.02.21 - 11:56
(20) КТ0000019
Ну да, можно вначале добавить префикс, в рамках одного массива заказа он совпадает, а потом нули
   Вафель
 
23 - 04.02.21 - 11:57
типо Номер ПОДОБНО %00+ Номер
   Bigbro
 
24 - 04.02.21 - 11:57
КТ001011
КТ001012, 10, 11
такие проблемы?
   ДНН
 
25 - 04.02.21 - 11:57
(21) придется писать обработку, которая заполнит регистр для тысяч уже созданных заказов
   Вафель
 
26 - 04.02.21 - 11:58
но как можно 9 преобразовать в 19???
   mistеr
 
27 - 04.02.21 - 12:00
Вот тебе простой алгоритм со множествами.

Множества в 1С будем представлять как Соответствие либо как Массив.
На входе исходное множество Заказы (массив). У каждого заказа есть Связи (массив)
На выходе наборы связанных заказов Наборы (массив соответствий). Вначале Наборы пустой

Для каждого заказа из Заказы ищем набор, куда его включить. Для этого перебираем его связи и смотрим в какой из имеющихся наборов связь входит. Туда же добавляем и сам заказ. Если связи входят в несколько наборов, объединяем все эти наборы в один и добавляем туда заказ. Если связи не входят ни в один из наборов, добавляем новый набор, включаем в него заказ и все его связи.

Получается три вложенных цикла.
   acht
 
28 - 04.02.21 - 12:01
(19) НомерЗаказа = "КТ" + Прав("0000000" + Формат(Строка, "ЧН=; ЧГ="), 7);

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

Хотя у тебя, похоже, не только в алгоритме сопоставления проблемы....
   ДНН
 
29 - 04.02.21 - 12:01
Всем спасибо, пошел на обед, потом сделаю и выложу свой говнокод сюда)
   acht
 
30 - 04.02.21 - 12:03
(29) Лучше не надо
 
 Рекламное место пустует
   b_ru
 
31 - 04.02.21 - 12:06
Если автоматизировать бардак, получается автоматизированный бардак (с)

В данном случае нужно ввести дополнительную сущность. Не знаю вашей специфики, поэтому удачное название не предложу. Пусть будет "Группа заказов". Сделать справочник этих групп заказов, сделать в заказе реквизит "Группа заказов", заполнить справочник и этот реквизит обработкой на основании ваших строк.
   Garykom
 
32 - 04.02.21 - 12:18
(0) Обычный граф.
Проблема только с "обычно заполняют только в одном заказе" - когда не стыкуется
   Garykom
 
33 - 04.02.21 - 12:20
(32)+ Графы принято коротко хранить в виде двумерной таблицы связей.
Короче ТЗ по колонкам/строкам номера заказов, значения заполнены 0.
Если есть связь то ставь 1 между нужным номером колонки и строки, зеркально там учти это не обязательно.
   Bigbro
 
34 - 04.02.21 - 12:22
(33) ТЗ будет плохо - очень разреженные данные, будешь хранить 99% пустых ячеек.
   Ненавижу 1С
 
35 - 04.02.21 - 12:29
   Garykom
 
36 - 04.02.21 - 12:30
(34) Ну массив тогда
В базе это лучше хранить заведя через расширения документ или справочник ГруппыЗаказов с ТЧ куда доки заказов прицеплять
   Garykom
 
37 - 04.02.21 - 12:31
(34) Я больше про сам алгоритм, тупо приводим все к номера и через них работаем.
Потом обратная операция из коротких номеров получаем ссылки заказов как то.
На практике все сложней с годовой нумерацией и ловлей номеров на стыке года.
   Bigbro
 
38 - 04.02.21 - 12:45
(37) посмотри на (4) и (5) - там возможно еще какая то сущность подразумевается, поскольку на 31 пофиг внезапно.
   GANR
 
39 - 04.02.21 - 12:54
(0) Первым делом я бы отказался от указаний заказов через запятую, а перевел бы на табличную часть или реквизит Родительский заказ если древовидное подчинение заказов друг другу - так исключена была бы пользовательская ошибка. Ну разумеется данные перенес бы в неё из строки какими-нибудь поделками. Только после того, как данные будут приведены в порядок и будет исключено указание ссылок на номера несуществующих заказов вижу смысл продолжать работу. Иначе это будет бесконечный цикл вопросов и переделок, которым я не то что заниматься, даже видеть не хочу.
   ДНН
 
40 - 04.02.21 - 14:51
вроде даже работает. Только на вход приходит не массив ссылок, а массив строк табл. части с колонкой "Документ", где ссылка на заказ:



Функция РазбитьЗаказы(МассивСтрок)
    
    ТаблицаСвязей = Новый ТаблицаЗначений;
    ТаблицаСвязей.Колонки.Добавить("Заказ");
    ТаблицаСвязей.Колонки.Добавить("Связь");
    
    СоответствиеНомеров = Новый Соответствие;
    СоответствиеСопутствующихНомеров = Новый Соответствие;
    СвязиЗаказа = Новый Соответствие;
    
    //получим все данные из БД

    Для Каждого Стр Из МассивСтрок Цикл
        РеквизитыЗаказа = ОбщегоНазначения.ЗначенияРеквизитовОбъекта(Стр.Документ, "Номер, НомераСопутствующихЗаказов");
        НомерБезПрефикса = Сред(РеквизитыЗаказа.Номер, 3); 
        СоответствиеНомеров.Вставить(НомерБезПрефикса, Стр.Документ);
        СоответствиеСопутствующихНомеров.Вставить(Стр.Документ, РеквизитыЗаказа.НомераСопутствующихЗаказов);
    КонецЦикла;    
    
    //заполним связи ссылками

    Для Каждого Стр Из МассивСтрок Цикл
        МассивЗаказов = Новый Массив;
        НомераСопутствующихЗаказов = СоответствиеСопутствующихНомеров.Получить(Стр.Документ);
        МассивНомеров = СтрРазделить(НомераСопутствующихЗаказов, ",", Ложь);
        Для Каждого Номер Из МассивНомеров Цикл
            Номер = Формат(СокрЛП(Номер), "ЧГ=0");
            Колво = Макс(11 - СтрДлина(Номер), 0);
            Номер = Прав("00000000000" + Номер, Колво);
            ЗаказПоНомеру = СоответствиеНомеров.Получить(Номер);
            Если Не ЗаказПоНомеру = Неопределено Тогда
                МассивЗаказов.Добавить(ЗаказПоНомеру);        
            КонецЕсли;         
        КонецЦикла;
        СвязиЗаказа.Вставить(Стр.Документ, МассивЗаказов);
    КонецЦикла;    
    
    Связь = 0;
    
    Для Каждого Стр Из МассивСтрок Цикл
        ТекущаяСвязь = Неопределено;
        НайдСтр = ТаблицаСвязей.Найти(Стр.Документ, "Заказ");
        Если НайдСтр = Неопределено Тогда
            //заказа еще нет в таблице

            ТекущиеЗаказы = Новый Массив;
            ТекущиеЗаказы.Добавить(Стр.Документ);
            
            СопЗаказы = СвязиЗаказа.Получить(Стр.Документ);
            Для Каждого СопЗаказ Из СопЗаказы Цикл
                НайдСтрСоп = ТаблицаСвязей.Найти(СопЗаказ, "Заказ");
                Если НайдСтрСоп = Неопределено Тогда 
                    ТекущиеЗаказы.Добавить(СопЗаказ);
                Иначе
                    //заказ может быть связан с другим заказом, который уже был добавлен в таблицу

                    ТекущаяСвязь = НайдСтрСоп.Связь;    
                КонецЕсли;    
            КонецЦикла;    
            
            //в таблице нет ни заказа, ни его связей

            Если ТекущаяСвязь = Неопределено Тогда
                Связь = Связь + 1;
                ТекущаяСвязь = Связь;
            КонецЕсли;    
        Иначе
            //если заказ был добавлен ранее через связи

            ТекущаяСвязь = НайдСтр.Связь;
            ТекущиеЗаказы = СвязиЗаказа.Получить(Стр.Документ);
        КонецЕсли;    
        
        Для Каждого ТекЗаказ Из ТекущиеЗаказы Цикл
            НовСтр = ТаблицаСвязей.Добавить();
            НовСтр.Заказ = ТекЗаказ;
            НовСтр.Связь = ТекущаяСвязь;    
        КонецЦикла;    
    КонецЦикла;    
    
    //вернем массив массивов

    МассивСвязей = Новый Массив;
    
    Связи = ТаблицаСвязей.Скопировать(, "Связь");
    Связи.Свернуть("Связь");
    Для Каждого Стр Из Связи Цикл
        НС = ТаблицаСвязей.НайтиСтроки(Новый Структура("Связь", Стр.Связь));
        Массив = Новый Массив;
        Для Каждого НайдСтр Из НС Цикл
            Если Массив.Найти(НайдСтр.Заказ) = Неопределено Тогда
                Массив.Добавить(НайдСтр.Заказ);
            КонецЕсли;    
        КонецЦикла;    
        МассивСвязей.Добавить(Массив);
    КонецЦикла;    
    
    Возврат МассивСвязей;
КонецФункции
   breezee
 
41 - 04.02.21 - 16:46
Хранить ссылки а не строки. Кто-нибудь неразрывный пробел с экселя в номер копирует и всё - скажут что Ваш быстрый алгоритм кривой)
За оф извините, не смог сдержаться)


Список тем форума
Рекламное место пустует  Рекламное место пустует
ВНИМАНИЕ! Если вы потеряли окно ввода сообщения, нажмите Ctrl-F5 или Ctrl-R или кнопку "Обновить" в браузере.