Блог

Я хочу определить рекурсивную функцию, которая сортирует входной вектор и использует последовательность вторичных векторов для разрыва любых связей (или рандомизирует их, если у них заканчиваются векторы тай-брейков)

Учитывая некоторый входной вектор I и некоторую матрицу тай-брейков T , псевдокод для алгоритма выглядит следующим образом:

1. проверьте T , пусто ли, если да, мы достигли условия остановки, поэтому рандомизируйте ввод
2. получить порядок индексов для сортировки I , используя стандартную sort функцию matlab
3. поиск индексов повторяющихся значений
4. для каждого повторяющегося значения,
   • вызовите функцию рекурсивно T(:,1) со строками, соответствующими индексам этого повторяющегося значения, с T(:,2:end) (с соответствующими строками) в качестве новой матрицы тай-брейков — если пусто, то этот вызов просто вернет случайные индексы
   • исправьте порядок отсортированных индексов в исходной отсортированной I
5. возвращает отсортированные I и соответствующие индексы

Вот что у меня есть до сих пор:

 function [vals,idxs] = tiebreak_sort(input, ties)

% if the tiebreak matrix is empty, then return random
if isempty(ties)
    idxs = randperm(size(input,1));
    vals = input(idxs);
    return
end

% sort the input
[vals,idxs] = sort(input);

% check for duplicates
[~,unique_idx] = unique(vals);
dup_idx = setdiff(1:size(vals,1),unique_idx);

% iterate over each duplicate index
for i = 1:numel(dup_idx) 
    % resolve tiebreak for duplicates
    [~,d_order] = tiebreak_sort(ties(input==input(i),1),...
        ties(input==input(i),2:end));
        
    % fix the order of sorted indices (THIS IS WHERE I AM STUCK)
    idxs(vals==input(i)) = ...?
end

return 
 

Я хочу найти способ сопоставить выходные данные рекурсивного вызова с индексами in idxs , чтобы исправить их порядок на основе (возможно, рекурсивных) тай-брейков, но мой мозг запутывается в узлах, думая об этом..

Могу ли я просто использовать тот факт, что sort функция Matlabs стабильна и сохраняет исходный порядок, и сделать это следующим образом?

 % find indices of duplicate values
dups = find(input==input(i));

% fix the order of sorted indices
idxs(vals==input(i)) = dups(d_order);
 

Или это не сработает? есть ли другой способ сделать то, что я пытаюсь сделать, в целом?

Просто чтобы привести конкретный пример, это будет пример ввода:

 I = [1 2 2 1 2 2]'

T = [4 1 ;
     3 7 ;
     3 4 ;
     2 2 ;
     1 8 ;
     5 3 ]
 

и результат будет:

 vals = [1 1 2 2 2 2]'

idxs = [4 1 5 3 2 6]'
 

Здесь во входных данных явно есть дубликаты, поэтому функция вызывается рекурсивно для первого столбца матрицы тай-брейков, которая смогла исправить 1 s, но для этого потребовался второй рекурсивный вызов для 3 s первого столбца, чтобы разорвать эти связи.

Не нужно определять функцию, sortrows не так ли:

 [S idxs] = sortrows([I T]);
vals = S(:,1);