Найти все комбинации

Question

Мой учитель задает алгоритм, который найдет все комбинации. У меня есть набор данных, и длина может быть переменной. Поэтому комбинации должны быть такими:

a 
b 
c 
aa 
ab 
ac 
... 
ccbc 
ccca 
cccb 
cccc 

Они будут храниться в таблице «слово», содержащей одно поле varchar. Я сделал это с петлей, потому что я не люблю рекурсивность и JT имеет лучшую производительность:

DROP PROCEDURE combi; 
CREATE PROCEDURE combi 
AS 
BEGIN 
    DELETE FROM word 
    DECLARE @i BIGINT 
    DECLARE @j INT 
    DECLARE @word NVARCHAR(24) 
    DECLARE @str NVARCHAR(62) 
    DECLARE @combinations BIGINT 
    DECLARE @currentlength TINYINT 
    DECLARE @maxcurrentlength TINYINT 
    SET @maxcurrentlength=4 
    SET @str='azertyuiopqsdfghjklmwxcvbnAZERTYUIOPQSDFGHJKLMWXCVBN' -- length=62 
    SET @currentlength=1 
    -- loop on the length of the text 
    WHILE @currentlength<=@maxcurrentlength BEGIN 
     SET @combinations=POWER(62,@currentlength) 
     SET @i=0 
     -- get all combinations 
     WHILE i<@combinations BEGIN 
      SET @word='' 
      SET @j=0 
      -- generate word 
      WHILE @j<@currentlength BEGIN 
       SET @word=@word+SUBSTRING(@str, (FLOOR(@i/POWER(62,@currentlength-@j-1)) % 62) +1, 1) 
       SET @j=@j+1 
      END 
      INSERT INTO word VALUES (@word) 
      SET @i=@i+1 
     END 
     SET @currentlength=@currentlength+1 
    END 
END; 
EXEC combi; 

Проблема заключается в том, когда я использую длину 8, мои сбои сервера: кажется, что POWER(62,@currentlength-@j-1) проблема.

Answer 1

Вы, вероятно, переполняете тип int, который вы переходите на POWER(), поскольку documentation for power предлагает POWER() возвращает тот же тип, который вы его кормите.

Попробуйте использовать:

SET @word=@word+SUBSTRING(@str, (FLOOR(@i/POWER(CAST(62 AS BIGINT),@currentlength-@j-1)) % 62) +1, 1) 

Answer 2

Я немного запутался о том, как задать вопрос. Вы просите «найти все комбинации», что очень легко сделать с помощью CROSS JOIN. Если вам нужно получить длину 4, то вы присоединитесь к таблице с доступными значениями для себя 4 раза, и вы в значительной степени сделали. Если вам нужно получить строки в поле 1, вы можете объединить их в выборе. Как это:

declare @values table (
value nvarchar(100)) 

insert @values values ('a'),('b'),('c') 

select v1.value+v2.value+v3.value+v4.value 
from @values v1 cross join 
    @values v2 cross join 
    @values v3 cross join 
    @values v4 
order by v1.value+v2.value+v3.value+v4.value 

Answer 3

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

declare @characters table (character nchar(1)) 
declare @words table (word nvarchar(100)) 
insert @characters values ('a'),('b'),('c') 
INSERT @words (word) VALUEs ('') 
DECLARE @Required_length int 
DECLARE @length int 
SET @Required_length = 4 
SET @length = 0 
WHILE @length <= @Required_length 
BEGIN 
SET @length = @length+1 
INSERT @words (word) 
SELECT w.word + c.character 
FROM @words w JOIN @characters c ON LEN(w.word) = @length-1 
END 
SELECT word from @words where len(word) = @Required_length 

• Старт с нулевой длиной слова в
• Добавить все возможные символы нулевой длины слова, чтобы получить все один символ слова
• Добавить все возможные символы до конца все один символ слова, чтобы получить все два символьных слова
• Добавьте все возможные символы в конец всех двух символов слова , чтобы получить все три символа слова
• и т.п ....

Вы можете сделать его более эффективным, указав длину в виде столбца в таблице слов, чтобы вам не нужно было вычислять длины, когда вы их фильтруете, но поскольку это было установлено вашим учитель, я не буду делать всю работу за вас

Answer 4

Первой вставки всех символов

SET NOCOUNT ON; 
create table ##chars (col char(1)) 
declare @i int 
set @i=65 
while @i<=90 /* A-Z */ 
begin 
    insert into ##chars values(CHAR(@i)) 
    set @i=@i+1 
end 
set @i=97 
while @i<=122 /* a-z */ 
begin 
    insert into ##chars values(CHAR(@i)) 
    set @i=@i+1 
end 
set @i=48 
while @i<=57 /* 0-9 */ 
begin 
    insert into ##chars values(CHAR(@i)) 
    set @i=@i+1 
end 

Теперь номера набора для комбинаций

create table ##result(word varchar(10)) 
declare @wide int 
set @wide=4 /* set how many combinations are calculated */ 


insert into ##result select * from ##chars 
while @wide>1 
begin 
    begin tran w 
    insert into ##result select a.word+b.col from ##result a, ##chars b 
    commit tran w 
set @wide=@wide-1 
end 
select * from ##result 
/* 
drop table ##chars 
drop table ##result 
*/ 

Answer 5

Вот общее решение с использованием рекурсивный КТР:

CREATE TABLE t (i nchar(1)) 
INSERT INTO t VALUES ('a'),('b'),('c') 

;WITH cte AS (
    SELECT cast(i AS nvarchar(4000)) AS combo, 1 AS ct 
    FROM t 

    UNION ALL 
    SELECT cte.combo + t.i, ct + 1 
    FROM cte 
    CROSS JOIN t 
    WHERE ct <= 4 -- your maximum length 
    ) 
SELECT combo 
FROM cte 
ORDER BY ct, combo 

SQL Fiddle.

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