SQL puzzle

Dmitry67 · Post by **Dmitry67** » 17 Jan 2002 18:49

Задача с которой мне пришлось столкнуться в реальной жизни.
Даю с упрошениями.

В фирму приходят деньги платежками. Известны их суммы, например:
$100 $1234 $77789 $3 $2 $2343

Известно что с того же щета в тот же день деньги ушли, например, $103.
Вопрос: какие платежки в комбинации могли образовать данную сумму ?
В нашем случае ето очевидно: $103 = $100 + $3
В обшем случае возможно много вариантов.

Задача: вывести все варианты комбинаций. Платежек не очень много (скажем 20-30)
Главное условие: ЗАПРЕШАЕТСЯ ИСПОЛьЗОВАТь ЦИКЛЫ для перебора
Алгоритм должен быть строго линеен

So,
create table Payments (amount money not null)
go
--- populate data
go
Now. Your script ?

[ 17-01-2002: Message edited by: Dmitry67 ]

Andy77 · Post by **Andy77** » 17 Jan 2002 19:45

<blockquote>quote:<hr>Originally posted by Dmitry67:
Главное условие: ЗАПРЕШАЕТСЯ ИСПОЛьЗОВАТь ЦИКЛЫ для перебора
Алгоритм должен быть строго линеен
<hr></blockquote>

О, это интересно, линейное решение задачи о рюкзаке [img:4308802dfb]images/smiles/icon_smile.gif[/img:4308802dfb] зачем тогда её решают с помощью метода ветвей и границ, динамического программирования, жадными алгоритмами?

Или имелось в виду, что в SQL-скрипте не будет цикла? охотно допускаю...

Drom · Post by **Drom** » 17 Jan 2002 23:54

glyuk

[ 17-01-2002: Message edited by: Drom ]

Dmitry67 · Post by **Dmitry67** » 18 Jan 2002 09:06

Сложность задачи експоненициальная конечно
Но сам код на SQL должен быть без циклов

Chapaev · Post by **Chapaev** » 19 Jan 2002 01:56

<blockquote>quote:<hr>Originally posted by Dmitry67:
Задача с которой мне пришлось столкнуться в реальной жизни.
Даю с упрошениями.

В фирму приходят деньги платежками. Известны их суммы, например:
$100 $1234 $77789 $3 $2 $2343

Известно что с того же щета в тот же день деньги ушли, например, $103.
Вопрос: какие платежки в комбинации могли образовать данную сумму ?
В нашем случае ето очевидно: $103 = $100 + $3
В обшем случае возможно много вариантов.

Задача: вывести все варианты комбинаций. Платежек не очень много (скажем 20-30)
Главное условие: ЗАПРЕШАЕТСЯ ИСПОЛьЗОВАТь ЦИКЛЫ для перебора
Алгоритм должен быть строго линеен

So,
create table Payments (amount money not null)
go
--- populate data
go
Now. Your script ?

[ 17-01-2002: Message edited by: Dmitry67 ]<hr></blockquote>

Пусть N - количество платежек.

begin transaction
insert into Payments values (0)

select p1.amount, p2.amount,... pN.amount
from Payments p1, Payments p2,... Payments pN
where p1.amount + p2.amount + ... + pN.amount = @Value

rollback transaction

Dmitry67 · Post by **Dmitry67** » 19 Jan 2002 02:52

Мысль интересная, мне в голову не пришла
Но три недостатка:
1. Количество платежек заранее неизвестно, каждый раз надо менять оператор
2. Не знаю как поведет себя оптимайзер при таком большом числе cross join
3. (главное) одна платежка может быть учтена дважды. Это можно починить добавив identity в payments, и выписав N*(N-1) условие на неравенство
Но мысль интересная
Свой способ (совсем другой) напишу в пн с работы - по памяти могу syntax error сделать, а там текст там уже набит

Chapaev · Post by **Chapaev** » 19 Jan 2002 06:47

<blockquote>quote:<hr>Originally posted by Dmitry67:
Мысль интересная, мне в голову не пришла
Но три недостатка:
1. Количество платежек заранее неизвестно, каждый раз надо менять оператор
2. Не знаю как поведет себя оптимайзер при таком большом числе cross join
3. (главное) одна платежка может быть учтена дважды. Это можно починить добавив identity в payments, и выписав N*(N-1) условие на неравенство
Но мысль интересная
Свой способ (совсем другой) напишу в пн с работы - по памяти могу syntax error сделать, а там текст там уже набит<hr></blockquote>

Согласен. Кроме того, каждая последовательность повторяется много раз.
Вот точное решение и предположении, что в таблице Payments есть identity i:

begin transaction
insert into Payments values (0)

select p1.amount, p2.amount,... pN.amount
from Payments p1, Payments p2,... Payments pN
where p1.amount + p2.amount + ... + pN.amount = @Value
and (p1.i < p2.i or p2.amount=0)
and (p2.i < p3.i or p3.amount=0)
...
and (p(N-1).i < pN.i or pN.amount=0)

rollback transaction

То, что количество платежек заранее неизвестно, не означает, что каждый раз надо менять оператор. Ведь можно заготовить только один с максимальным N.

Dmitry67 · Post by **Dmitry67** » 21 Jan 2002 16:13

My solution:

1. We must know the max. number of payments (N). We must populate (only 1 time) the following table:

create table allnum (i int)
with natural numbers 1..(2^N)-1

Then:
-- assign identity to payments
select Amount,Identity(int) as Id into #P1 from Payments
-- convert identity into 2^^N-1, so it would be 1,2,4,8,16...
select Amount,power(2,Id-1) as bits into #P2 from #P1
-- finally, this statement would find the answer !
select i,sum(Amount) from #P2,allnum where bits&i>0 group by i having sum(Amount)=@Value

[ 21-01-2002: Message edited by: Dmitry67 ]

Drom · Post by **Drom** » 24 Jan 2002 20:53

Dmitry67,
приятная задачка, спасибо. я тут посидел над ней немного: если нет желания ограничивать последовательность, то получается, что надо выбрать все возможные комбинации строк (по одной) из таблицы. без циклов остается рекурсия процедур, функций или триггеров (или неопределенномерная таблица, что уже из области фантастики - в приведенных решениях использовалость произведение фиксированной размерности).
B общем получилась функция (MS SQL 2K), которая выбирает все возможные комбинации строк из таблицы (колонка [id] иcxодной таблицы, как обычно - уникальный ID, но добавлена строка с id=0 для обозначения "отсутствия строки")
<blockquote>code:<hr><pre>CREATE FUNCTION FFN (@n as int)
RETURNS
@Result TABLE (id int, seq varchar(255))
AS
BEGIN

Declare @m int
SELECT @m = @n - 1

IF (@m = -1)
BEGIN
Select @m = (select count(id) from privetTable)-2
END

IF (@m = 0)
BEGIN
INSERT INTO @Result
SELECT id, CONVERT(varchar(255),id) FROM privetTable
END
ELSE
BEGIN
INSERT INTO @Result
SELECT B.id, A.seq + ',' + CONVERT(varchar(255),B.id)
FROM FFN(@m) A, privetTable B
WHERE (A.id > B.id OR B.id = 0)
END

RETURN
END</pre><hr></blockquote>

вызов этой функции
<blockquote>code[quote:686010e1fa]<pre>SELECT seq FROM FFN(0)</pre>[/quote:686010e1fa]

выдает 2^N комбинаций для таблицы с N строками. как заставить ее суммировать значения определенного поля строк из последовательности и что можно сделать where на вызов функции думаю очевидно. Ресурсов на "приличной" табличке из 30-50 строк, конечно, эта штука должна жрать немеряно (запускать боюсь - пробуйте сами, если кто смелый).

D.

Да, эта же функция работает на перебор с ограничением на макс длину последовательности, если ей передать эту длину как параметр.

[b:686010e1fa]added:[/b:686010e1fa]
guess you can also write selfmodifying code or code wich changes table design to solve it, but I don't like self-modifiers today.

[ 24-01-2002: Message edited by: Drom ]

SF_man · Post by **SF_man** » 24 Jan 2002 22:32

To Dmitry67:

Действительно, в общем случае это задача о рюкзаке, которая
не имеет алгоритмов для решения линейной сложности (от размера рюкзака, то есть
числа платежей).
Но в данном конкретном случае вектор является сверхрастущим
(то есть а[0]+а[1]+...+а[i-1]<а[i]), а именно:
2 < 3
2+3 < 100
2+3+100 < 1234
2+3+100+1234 < 2343
2+3+100+1234+2343 < 77789
Известно, что для сверхрастущих векторов задача о рюкзаке вырождается
в линейную (если вектор отсортирован) с помощью всего одного (обратного)
просмотра всех платежей.

[ 24-01-2002: Message edited by: SF_man ]