генерировать все возможные подмножества из массива символов в MATLAB

Question

Мне нужно сгенерировать все возможные подмножества из массива символов в MATLAB с уменьшенным временем выполнения. Например: вход = 'ABCA'; выход = «А», 'B', 'C', 'AB', 'ДО НАШЕЙ ЭРЫ', 'CA', 'ABC', «ДСС», 'ABCA'

Answer 1

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

При случайном вводе 500 символов и maxLen при 20 я получил 4207817 уникальных подстрок.Мой компьютер (с MATLAB R2017a) занял 12 секунд, чтобы найти их.Является ли это достаточно быстрым или нет, зависит от вас, но я бы не стал дополнительно его оптимизировать.

input = 'ABCA';
maxLen = 4;

subsets = {};
for len = 1:maxLen
   subs = cell(1,numel(input)-len+1);
   for start = 1:numel(subs)
      subs{start} = input(start:start+len-1);
   end
   subs = unique(subs);
   subsets = [subsets,subs];
end
disp(subsets)

Вывод:

'A'    'B'    'C'    'AB'    'BC'    'CA'    'ABC'    'BCA'    'ABCA'

Если важно сохранить порядокподстроки, затем добавьте аргумент 'stable' к вызову unique:

   subs = unique(subs,'stable');

Например, для input = 'AFCB'; вывод без 'stable':

'A'    'B'    'C'    'F'    'AF'    'CB'    'FC'    'AFC'    'FCB'    'AFCB'

а с 'stable' это:

'A'    'F'    'C'    'B'    'AF'    'FC'    'CB'    'AFC'    'FCB'    'AFCB'