сортировка с явным разрешением связывания (повторяющихся элементов)

Question

По умолчанию функция MATLAB sort обрабатывает связи / повторяющиеся элементы, сохраняя порядок элементов, то есть

>> [srt,idx] = sort([1 0 1])

srt =

    0     1     1


idx =

    2     1     3

Обратите внимание, что два элемента со значением 1 вНа вход произвольно получают присвоенные индексы 2 и 3 соответственно.idx = [3 1 2], однако, будет в равной степени действительной сортировки.

Я хотел бы функцию [srt, all_idx] = sort_ties (in), которая явно возвращает все возможные значения для idx, которые согласуются сотсортированный вывод.Конечно, это произойдет только в случае связей или повторяющихся элементов, и all_idx будет иметь размерность nPossibleSorts x length (in).

Я начал использовать рекурсивный алгоритм для этого, но быстро понял, что все быловыходит из-под контроля, и кто-то должен был решить это раньше!Есть предложения?

Answer 1

У меня была идея, подобная , что предложил Р. М. . Однако это решение обобщено для обработки любого количества повторяющихся элементов во входном векторе. Сначала код сортирует входные данные (используя функцию SORT ), затем перебирает каждое уникальное значение, чтобы сгенерировать все перестановки индексов для этого значения (используя функцию PERMS ), сохраняя результаты в массиве ячеек. Затем эти перестановки индекса для каждого отдельного значения объединяются в общее число перестановок для отсортированного индекса путем соответствующей репликации их с функциями KRON и REPMAT :

function [srt,all_idx] = sort_ties(in,varargin)

  [srt,idx] = sort(in,varargin{:});
  uniqueValues = srt(logical([1 diff(srt)]));
  nValues = numel(uniqueValues);
  if nValues == numel(srt)
    all_idx = idx;
    return
  end

  permCell = cell(1,nValues);
  for iValue = 1:nValues
    valueIndex = idx(srt == uniqueValues(iValue));
    if numel(valueIndex) == 1
      permCell{iValue} = valueIndex;
    else
      permCell{iValue} = perms(valueIndex);
    end
  end
  nPerms = cellfun('size',permCell,1);

  for iValue = 1:nValues
    N = prod(nPerms(1:iValue-1));
    M = prod(nPerms(iValue+1:end));
    permCell{iValue} = repmat(kron(permCell{iValue},ones(N,1)),M,1);
  end
  all_idx = [permCell{:}];

end

А вот несколько примеров результатов:

>> [srt,all_idx] = sort_ties([0 2 1 2 2 1])

srt =

     0     1     1     2     2     2

all_idx =

     1     6     3     5     4     2
     1     3     6     5     4     2
     1     6     3     5     2     4
     1     3     6     5     2     4
     1     6     3     4     5     2
     1     3     6     4     5     2
     1     6     3     4     2     5
     1     3     6     4     2     5
     1     6     3     2     4     5
     1     3     6     2     4     5
     1     6     3     2     5     4
     1     3     6     2     5     4

Answer 2

Рассмотрим пример A=[1,2,3,2,5,6,2]. Вы хотите найти индексы, где встречается 2, и получить все возможные перестановки этих индексов.

Для первого шага используйте unique в сочетании с histc, чтобы найти повторяющийся элемент и индексы, где он встречается.

uniqA=unique(A);
B=histc(A,uniqA);

Вы получаете B=[1 3 1 1 1]. Теперь вы знаете, какое значение в uniqA повторяется и сколько раз. Чтобы получить индексы,

repeatIndices=find(A==uniqA(B==max(B))); 

, что дает индексы как [2, 4, 7]. Наконец, для всех возможных перестановок этих индексов используйте функцию perms.

perms(repeatIndices)
ans =

 7     4     2
 7     2     4
 4     7     2
 4     2     7
 2     4     7
 2     7     4

Я верю, что это делает то, что вы хотели. Вы можете написать функцию-оболочку для всего этого, чтобы у вас было что-то компактное, например out=sort_ties(in). Скорее всего, вы должны включить условное выражение вокруг строки repeatIndices, чтобы, если B было всеми единицами, вы не продвигались дальше (то есть связи отсутствуют)

Answer 3

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

function [srt,idx] = tie_sort(in,order)

L = length(in);
[srt,idx] = sort(in,order);

for j = 1:L-1 % for each position in sorted array, look for repeats following it

  for k = j+1:L

    % if repeat found, add possible permutations to the list of possible sorts
    if srt(j) == srt(k)

       swapped = 1:L; swapped(j) = k; swapped(k) = j;
       add_idx = idx(:,swapped);

       idx = cat(1,idx,add_idx);
       idx = unique(idx,'rows'); % remove identical copies

    else % because already sorted, know don't have to keep looking

       break;

    end

  end

end