How to get a random combination of rows that sum up to a specific value?

Question

The Table I have:

+--------+--------------------+
|item_id|        value        |
+--------+--------------------+
|  1     | 1                  |
|  2     | 4                  |
|  3     | 2                  |
|  4     | 6                  |
+--------+--------------------+

What the SQL Query Result should be: A random combination of items that sum up to 10 with a variable number of different items (in this case 2.)

+--------------+--------------------+-------------+
|item_id       |        amount      |      sum    |
+--------------+--------------------+-------------+
|2             |2                   |8            |
|3             |1                   |2            |
+--------------+--------------------+-------------+

The results show

You get 2 times item 2 (which has the value of 4 so it adds to a sum of 8).

And you get one time item 3 (which has the value of 2)

This combination sums up to 10.

Is that even possible, when it should not be the same combination always and picked random if there are other possibilitys?

Can you explain the logic? How do you get the expected result? — The Impaler, Jun 30 '19 at 17:17
OK, got it. What database engine do you have, and which version? Otherwise I'll consider generic SQL. — The Impaler, Jun 30 '19 at 18:12
Which version of MySQL? 5.x or 8.x. Those are quite different animals. — The Impaler, Jun 30 '19 at 18:16

score 1 · Answer 1 · answered Jun 30 '19 at 17:20

1

You can get all such combinations using a self-join:

select t1.item_id, t2.item_id
from t t1 join
     t t2
     on t1.value + t2.value = 10;

This puts the values on columns rather than in separate rows.

answered Jun 30 '19 at 17:20

Gordon Linoff

1,242,037
58
646
786

not sure what t2 is, but maybe you understood it wrong. i updated the question – Darkenn Jun 30 '19 at 17:32
@Darkenn t2 is a second reference to the table called t. As the answer says, it's a self-join: t is joined onto another copy of itself. – ADyson Jun 30 '19 at 19:18
but it does not include the possibility of having multiple of the same item as the question says – Darkenn Jun 30 '19 at 19:28
thats why i said a random combination because you could not output all. – Darkenn Jun 30 '19 at 20:06
1

@Darkenn . . . You can add `limit 1` to get one combination. However, the results is *arbitrary* rather than *random*. – Gordon Linoff Jul 01 '19 at 01:08

The Impaler · Accepted Answer · 2019-07-01T14:58:54.897

Assuming you want a single random combination, you can do:

select
  *
from (
  select
    a.item_id as item1, 
    x.n as amount1, 
    a.value * x.n as sum1,
    b.item_id as item2, 
    y.n as amount2, 
    b.value * y.n as sum2,
    rand() as r
  from my_table a
  join my_table b on b.item_id <> a.item_id
  cross join (
    select 1 as n union select 2 union select 3 union select 4 
    union select 5 union select 6 union select 7 union select 8 
    union select 9 union select 10) x
  cross join (
    select 1 as n union select 2 union select 3 union select 4
    union select 5 union select 6 union select 7 union select 8 
    union select 9 union select 10) y
  where a.value * x.n + b.value * y.n = 10
) z
order by r -- sorted randomly
limit 1 -- to get only one combination; remove to get them all

Every time you run this query it picks a random [different] solution.

The script to create the table and data you mentioned (that I used to test) is:

create table my_table (
  item_id int,
  value int
);

insert into my_table (item_id, value) values (1, 1);
insert into my_table (item_id, value) values (2, 4);
insert into my_table (item_id, value) values (3, 2);
insert into my_table (item_id, value) values (4, 6);

EDIT on July 1st, 2019: As requested, here's an equivalent [shorter] solution using a recursive CTE (Common Table Expression), available in MariaDB since 10.2.2 (see Recursive Common Table Expressions):

with recursive
val as (select 1 as n union all select n + 1 from val where n < 10)
select
  *
from (
  select
    a.item_id as item1, 
    x.n as amount1, 
    a.value * x.n as sum1,
    b.item_id as item2, 
    y.n as amount2, 
    b.value * y.n as sum2,
    rand() as r
  from my_table a
  join my_table b on b.item_id <> a.item_id
  cross join val x
  cross join val y
  where a.value * x.n + b.value * y.n = 10
) z
order by r -- sorted randomly
limit 1 -- to get only one combination; remove to get all 22 answers

This solution scales much better if you need to use higher numbers.

that works exactly as expected! lets say i want 3 items that result in a sum of 10, do i just add another cross join? — Darkenn, Jul 01 '19 at 06:07
and if the sum needs to be something else then 10, do you need more union selects? — Darkenn, Jul 01 '19 at 06:22
@Darkenn Yes, unless you upgrade to MariaDB 10.2 where you can use a [short] recursive CTE to generate the numbers. — The Impaler, Jul 01 '19 at 13:50
can you show me the 10.2 version? sorry if it's too much to ask, also im not that advanced with sql. — Darkenn, Jul 01 '19 at 14:01

How to get a random combination of rows that sum up to a specific value?

This combination sums up to 10.

2 Answers2