Здесь я реализовал алгоритм обхода путем комбинации имен в алфавитном порядке до N имен. Алгоритм не пересекает все комбинации 2^N-1, как в упомянутом базовом коде .
Алгоритм объясняется следующим образом. Обозначение i-th имени представлено цифрой i (начиная с 1), тогда комбинация имен может быть представлена последовательностью строго возрастающих цифр. Строго возрастающее ограничение исключает различные перестановки из одной и той же комбинации.
Теперь мы можем пройти через эти представления в алфавитном порядке, как показано ниже (как в реальном словаре). Можно ясно видеть, что есть 2 ключа для обхода: (1) , когда делать округление и (2) , выполняя это с учетом строго возрастающего ограничения . Остальное - правильно их реализовать в коде.
Отказ от ответственности: Низкая эффективность, ремонтопригодность и масштабируемость! Он едва работает на небольшом наборе данных (38 секунд для 1350 комбинаций из M=20 и N=3). Рассмотрите выполнение этой задачи на языке программирования общего назначения, особенно когда набор данных большой. например, Pythonic решение только с 4 строками
Понятие того, что делают алгоритмы
Combination of names
---------------------
1 -- 1 means 'name1'
2
...
n -- Round up to 2-digit combinations after this number
1,2 -- The lowest digit begins at 2 because (1,1) violates the constraint
1,3
...
1,n
2,3 -- begins at 3 because 2,1 and 2,2 violates the constraint
2,4
....
2,n
.....
(n-1),n -- Can't round up to (n,n) so here ends the combinations of 2 digits.
1,2,3 -- In general, round-up gives a consecutive increasing sequence
-- starting from the rounding digit
1,2,4
.... -- repeat until all wanted combinations are exhausted.
А вот код T-SQL
Набор тестовых данных и параметры
use [testdb];
if OBJECT_ID('testdb..test') is not null
drop table testdb..test;
create table test (
[name] VARCHAR(10)
);
GO
-- name list, need not be sorted
insert into test([name])
values ('name1'),('name2'),('name3'),('name4'),('name5');
-- Number of names used in the combination
declare @N int = 3;
Программа
/***** temp variables *****/
-- get number of names
declare @M int;
select @M = count(distinct [name]) from test;
--print @M;
-- array (table variable) of temporary status
declare @arr table (
digit int primary key,
val int,
[name] varchar(max)
)
-- the value of each digits begins from 0
insert @arr(digit, val, [name])
select ROW_NUMBER() over(order by [name]), 0, [name] from test;
-- begin traversal from the first name
update @arr
set val = 1
where digit = 1;
-- check:
-- select * from @arr;
-- concatenation of names
DECLARE @cat VARCHAR(max) = ''
-- current value at the lowest digit
declare @val_now int = 1; -- 1 to N
-- digit pointer and temporary value used for rounding
declare @digit_round int;
declare @val_round int;
-- answer storage
if OBJECT_ID('tempdb..#ans') is not null
drop table #ans;
create table #ans (
names varchar(max)
)
/***** Main Loop *****/
declare @flag_terminate int = 0;
while (@flag_terminate = 0) begin
while @val_now <= @M BEGIN
/** output current combination **/
-- select * from @arr;
set @cat = '';
-- use cursor to preserve name order
declare @name_now varchar(100);
declare cur cursor local
for select (select B.[name] from @arr as B where B.digit = A.val) as [name]
from @arr as A
where A.val > 0
order by [name];
open cur;
while 1=1 begin
fetch next from cur into @name_now;
if @@FETCH_STATUS <> 0 break;
set @cat = case @cat
when '' then ''
else @cat + ','
end + @name_now;
end
close cur;
deallocate cur;
-- Can also do this if you don't care about name order
-- Note that 'order by' won't work on subqueries
-- SELECT @cat = case @cat
-- when '' then ''
-- else @cat + ','
-- end + (select B.[name] from @arr as B where B.digit = A.val)
-- FROM @arr as A
-- where A.val > 0;
insert into #ans(names) values (@cat);
/** Proceed to next combination **/
-- 1. no round-up case
if @val_now < @M begin
set @val_now += 1;
update @arr
set val = @val_now
where digit = 1;
end
-- 2. round-up case
else begin
-- Find which digit at where the rounding process should end
set @digit_round = 1
while @digit_round <= @M begin
-- N.B. Ascending alphabatical sorting of name combanitaions implies
-- max(digit 2) = M - 1
-- max(digit 3) = M - 2
-- ....
-- max(digit N) = M - N + 1
set @val_round = (select val from @arr where digit = @digit_round);
if @val_round < @M - @digit_round + 1
break;
set @digit_round += 1;
end
-- print ' digit_round = ' + str(@digit_round)
-- print ' val_round = ' + str(@val_round)
-- 2.1 regular round-up case
-- rounding process ends within N digits
if @digit_round <= @N begin
while @digit_round >= 1 begin
-- rounded value
set @val_round += 1;
-- print 'start rounding:'
-- print ' digit_round = ' + str(@digit_round)
-- print ' val_round = ' + str(@val_round)
-- update temp table
update @arr
set val = @val_round
where digit = @digit_round;
-- next digit
set @digit_round -= 1;
end
-- reset loop vars
set @val_now = @val_round;
end
-- 2.2 termination case
-- rounding process does not end in N digits
else begin
-- print 'Termination reached!'
set @flag_terminate = 1;
set @val_now = @M + 1;
end
end
end
end
-- output
select * from #ans;
Результат
| | names |
|----|-------------------|
| 1 | name1 |
| 2 | name2 |
| 3 | name3 |
| 4 | name4 |
| 5 | name5 |
| 6 | name1,name2 |
| 7 | name1,name3 |
| 8 | name1,name4 |
| 9 | name1,name5 |
| 10 | name2,name3 |
| 11 | name2,name4 |
| 12 | name2,name5 |
| 13 | name3,name4 |
| 14 | name3,name5 |
| 15 | name4,name5 |
| 16 | name1,name2,name3 |
| 17 | name1,name2,name4 |
| 18 | name1,name2,name5 |
| 19 | name1,name3,name4 |
| 20 | name1,name3,name5 |
| 21 | name1,name4,name5 |
| 22 | name2,name3,name4 |
| 23 | name2,name3,name5 |
| 24 | name2,name4,name5 |
| 25 | name3,name4,name5 |
Протестировано на SQL Server 2017, последняя версия (образ установщика Linux).