Как эффективно найти уникальные массивы ячеек в наборе ячеек в MATLAB? - PullRequest
Новая
       14

Как эффективно найти уникальные массивы ячеек в наборе ячеек в MATLAB?

1 голос
/ 17 марта 2011

Мне нужно найти только уникальные массивы ячеек в наборе ячеек.Например, если это мой ввод: 

I = {{'a' 'b' 'c' 'd' 'e'} ...
     {'a' 'b' 'c'} ...
     {'d' 'e'} ...
     {'a' 'b' 'c' 'd' 'e'} ...
     {'a' 'b' 'c' 'd' 'e'} ...
     {'a' 'c' 'e'}};

Тогда я бы хотел, чтобы мой вывод выглядел следующим образом: 

I_unique = {{'a' 'b' 'c' 'd' 'e'} ...
            {'a' 'b' 'c'} ...
            {'d' 'e'} ...
            {'a' 'c' 'e'}};

У вас есть идеи, как это сделать?Порядок элементов в выходных данных не имеет значения, но эффективность имеет значение, так как массив ячеек I может быть очень большим.

Ответы [ 2 ]

1 голос
/ 17 марта 2011

РЕДАКТИРОВАТЬ: Обновлен для использования более эффективного алгоритма.

Если эффективность равносильна из-за большого количества наборов в I, то ваш лучший вариант, вероятно, состоит в том, чтобы свернуть ваши собственные оптимизированные циклы. Эта проблема имеет некоторое сходство с предыдущим вопросом о , как эффективно удалять наборы, которые являются подмножествами или равны другим . Разница здесь в том, что вас не интересует удаление подмножеств , просто дубликатов , поэтому код в моем ответе на другой вопрос можно изменить для дальнейшего сокращения количество сравнений.

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

Для каждой из этих групп у нас будет два вложенных цикла: внешний цикл над каждым набором, начинающийся в конце наборов, и внутренний цикл над каждым набором, предшествующим этому. Если / когда найдено первое совпадение, мы можем пометить этот набор как «не уникальный» и разорвать внутренний цикл, чтобы избежать дополнительных сравнений. Запуск внешнего цикла в конце наборов дает нам дополнительный бонус, который устанавливается в I_unique и будет поддерживать исходный порядок появления в I.

А вот и полученный код: 

I = {{'a' 'b' 'c' 'd' 'e'} ...  %# The sample cell array of cell arrays of
     {'a' 'b' 'c'} ...          %#   strings from the question
     {'d' 'e'} ...
     {'a' 'b' 'c' 'd' 'e'} ...
     {'a' 'b' 'c' 'd' 'e'} ...
     {'a' 'c' 'e'}};
nSets = numel(I);                    %# The number of sets
nStrings = cellfun('prodofsize',I);  %# The number of strings per set
uniqueIndex = true(1,nSets);         %# A logical index of unique elements

for currentSize = unique(nStrings)   %# Loop over each unique number of strings

  subIndex = find(nStrings == currentSize);  %# Get the subset of I with the
  subSet = I(subIndex);                      %#   given number of strings

  for currentIndex = numel(subSet):-1:2      %# Outer loop
    for compareIndex = 1:currentIndex-1      %# Inner loop
      if isequal(subSet{currentIndex},subSet{compareIndex})  %# Check equality
        uniqueIndex(subIndex(currentIndex)) = false;  %# Mark as "not unique"
        break                                %# Break the inner loop
      end
    end
  end

end

I_unique = I(uniqueIndex);  %# Get the unique values
1 голос
/ 17 марта 2011

Если ваши ячейки содержат только отсортированные одиночные символы, вы можете сохранить только уникальные последовательности, используя: 

>> I = {{'a' 'b' 'c' 'd' 'e'} {'a' 'b' 'c'} {'d' 'e'} {'a' 'b' 'c' 'd' 'e'} {'a' 'b' 'c' 'd' 'e'} {'a' 'c' 'e'}};
>> I_unique = cellfun(@char, I, 'uniformoutput', 0);
>> I_unique = cellfun(@transpose, I_unique, 'uniformoutput', 0);
>> I_unique = unique(I_unique)

I_unique = 

    'abc'    'abcde'    'ace'    'de'

Затем можно снова разделить полученные ячейки на отдельные символы: 

>> I_unique = cellfun(@transpose, I_unique, 'uniformoutput', 0);
>> I_unique = cellfun(@cellstr, I_unique, 'uniformoutput', 0);
>> I_unique = cellfun(@transpose, I_unique, 'uniformoutput', 0);
>> I_unique{:}

ans = 

    'a'    'b'    'c'


ans = 

    'a'    'b'    'c'    'd'    'e'


ans = 

    'a'    'c'    'e'


ans = 

    'd'    'e'
...