Помогите решить следующую задачку.

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

Теперь собственно задача. На группы наложено ограничение в минимум N переменных, попадающих в данную группу. Если в группу попадает менее N переменных, группы необходимо объединять. Объединять тоже необходимо в определенном порядке. Таблица группы выглядит примерно так:

group lvl1 lvl2 lvl3
a 1 1 1
b 2 1 1
c 3 2 1
d 4 2 1

Это означает, что если количество элементов в 1 или 2 (3 или 4) группе будет недостаточно, то их необходимо объединить в группу 1 (2) на lvl2. А если на lvl2 в 1 или 2 группе будет все еще недостаточно элементов необходимо и их объединить.

Заранее спасибо.

AndreTM,

Ок. И все это нужно сделать в FoxPro :)

P.S. если все еще не тот раздел, не мог бы модератор перенести в упомянутый выше AndreTM раздел. Спасибо.

AndreTM,

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

Задачу, наверно, проще описать следующим образом:
Есть много-много яблок разного цвета и размера. (переменные)
Есть корзины, в которые необходимо поместить все яблоки. (группы)

То есть задача раскидать все яблоки по корзинам.

На корзины наложено ограничение в минимальное количество яблок. То есть, например, если маленьких зеленых яблок мало - из нужно объединить со средними зелеными яблоками (ну или желтыми маленькими, как угодно :) ).

То есть в лучшем случае мы обходимся без объединений корзин и в каждой из них есть больше необходимого минимума яблок.

В худшем случае все корзины объединяются. Порядок объединений задан. Ну вроде все.

ВладимирМ,

Это я конечно неправильно сделал, что выплеснул всю задачу сюда. Наверно, лучше описать имеено проблему.

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

группа, кол-во элементов, этап_объединения_1, этап_объединения_2, этап_объединения_3..
1, 60, 1, 1, 1
2, 70, 2, 1, 1
3, 110, 3, 2, 1
4, 30, 4, 3, 1
5, 150, 5, 3, 1

Мы разложили некоторые переменные по группам. На данном этапе появляется ограничение на количество элементов группы снизу.
Минимальное количество элементов = 100. Также дается порядок объединения групп. Рассмотрим на данном примере, что должно получится:

На входе имеем 5 групп, 2 из содержат более 100 элементов, остальные нет. Смотрим на первый этап объединения, тут объединения нет. Значит задача не решена. Идем на второй уровень, и здесь все получается хорошо: 60+70>100 и 30+150>100.

Таким образом, из 5 изначальных групп, получилось 3. Понятно, что последним этапом объединения групп является объединение всех групп.

На данный момент самым сложным для меня представляется следующее: как проанализировать входящий файл на количество этапов объединения, при условии, что мы знаем принцип, по которому называются поля, например, level1, level2, level3, ... , leveln. Как определить количество названных таким образом столбцов? Количество отличных от level# столбцов переменно.


Но как-то некрасиво не ответить Вам на вопросы, поэтому:
1. каким образом связаны таблицы переменных и групп?
аналитически (на группы наложены условия)
2. ну, каким образом можно вычислить сколько переменных входят в одну группу?
по условию, условия записаны перечислением определенных характеристик, которыми должна обладать переменная, т.е. возвращаясь к яблокам и корзинам, примером условия некоторой корзины может быть: цвет='зеленый' И размер='средний'
3. Что Вы понимаете под "объединением"?
сумма элементов групп
4. Если объединяемые группы содержат разные условия, то какие условия должны попасть в итоговую (объединенную) группу?
новое_условие=(условие1 OR условие2)

ВладимирМ,

большое спасибо Вам.

ВладимирМ,

еще раз спасибо и не могли бы Вы еще помочь мне немного?

Вопрос следующий: как реализовать для этой же задачи группировку на разных уровнях?

В приложенном примере, 9 групп и 3 этапа объединения. Тут правильнее, как мне кажется, пойти сверху вниз, то есть от крупного объединения к мелким. В данном примере (ограничение 100 элементов на группу), на 3ем этапе мы видим 160+250 элементов > 100. Идем дальше, на втором этапе и 160, и 250 больше 100. Идем дальше, 80 элементов в 1ой и второй группе не удовлетворяют условию, поэтому для них оставляем объединение - stage2_group1. Однако, и 150, и 100 >= 100, поэтому группу 2 из stage2 бьем еще раз.

Таким образом получаем объединенные группы:
stage2_group1
stage1_group3
stage1_group4

Заранее спасибо!

ВладимирМ,

может я чего-то не предусматриваю, но мне кажется, что алгоритм должен выглядеть так:

*пусть stage1 - самое крупное объединение

для i = 2 до n
суммируем элементы по группам этого уровня, сохраняем в массив;
(для вашего примера это 1-1 с мощностью 90 и 1-2 со 120)

если все элементы массива вида 1-Х содержат >= 100 элементов
(Х зависит от этапа объединения, сейчас Х на втором месте, так как i = 2)

то сохраняем в таблицу (со всеми группами в отдельную колонку - актуальный этап объединения) i для групп вида 1-Х

иначе i -1, и исключаем из дальнейшего рассмотрения
следующий

Как-то так.

ВладимирМ,

Ну вроде с алгоритмом не было проблемы, хотя я понимаю, что возможны тонкости при реализации.

Но написал я сюда только по одной причине - я не могу перевести алгоритм в код и именно на этом этапе надеялся на помощь..

ВладимирМ,

Спасибо, буду очень признателен. Сам тоже попробую, может и выйдет что-нибудь.

ВладимирМ,

Спасибо большое. По понятным причинам, чтобы разобраться в коде мне нужно больше времени. Однако, мне кажется, что программа работает несколько некорректно. При таких условиях результат должен был быть:
1 гр - 160
2 гр - 150
3 гр - 100
4 гр - 150

Также я "поигрался" с исходными данными и выявил некоторую закономерность - похоже, что на stage1 не происходит разбиения.

Плюс при некоторым вариантах исходных данных возможно задубливание (например, если ввести группам a,b,c,d количество элементов по 20). Собственно поэтому в алгоритме я предлагал результирующая таблицу вида:
a, 40, stage2-1
b, 40, stage2-1
c, 40, stage2-1
d, 40, stage2-1
e, 50, stage1-3
f, 50, stage1-3
g, 50, stage1-3
h, 50, stage1-4
i, 50, stage1-4
j, 150, stage1-5

[имя_группы], [мощность], [уровень_объединения], [номер_объединенной_группы].

То есть обновляемая последняя колонка. Такой вид результата легко поддается анализу.

Если у Вас будет время/возможность/желание помочь я буду очень рад. Еще раз спасибо.

ВладимирМ,

все равно не проходит проверку - поставить всем группам по 10 элементов, результатом должна быть одна группа :(.

ВладимирМ,

похоже сработало, пока не уверен на 100%, но кажется есть.

Подскажите, пожалуйста, как проанализировать результат, я имею ввиду, что при таких условиях:

Результат будет:

То есть я вижу, как это получилось, но можно ли как-нибудь поставить в соответствие имя новой группы к старым?

ВладимирМ,

Сегодня я получил input, раньше не было возможности выложить. Посмотрите, пожалуйста:
В приложенном файле:
1. знакомые поля stage1-stage6
2. order - номер группы
3. также было поле "условие", я его удалил, чтобы не загромождать таблицу + это не важно, так как из этих условий я получаю количество элементов (мощность) - колонки m_hor, obk, okt и т.д. Они создаются в цикле.
4. Также в цикле я создаю для каждой колонки с количеством элементов, колонку с таким же названием + первая буква 's'.
5. И вот в эти колонки пытаюсь проставить этап объединения (пытаюсь, потому что у меня все не выходит).

Возвращаясь к вопросу об имени группы - главное, чтобы каждому order (самой мелкой группе) соответствовала объединенная группа, то есть те группы, которые были объединены друг с другом, будут иметь одинаковое название объединенной группы.

На предыдущем примере, если оставить имена начальных и итоговых групп, то следующий вид был бы идеален: