Бредятинка родилась в ходе трёпа-охаивания разных алгоритмов сортировки.
Насчёт того, что свойства стабильности и упорядоченности ортогональны.

Если это так, то почему бы не сделать алгоритм, обратный сортировке (т.е. random_shuffle), но при этом стабильный.
То есть, чтоб выполнялось stable_sort(stable_shuffle(xs)) == stable_sort(xs)

Ещё одно требование — это равномерность, т.е. чтобы генерируемые перестановки были равновероятны.

Навскидку, я знаю тупой алгоритм с квадратной сложностью. Кто лучше?

Здравствуйте, Кодт, Вы писали:

Т.е. тебе нужен random_shuffle который бы сохранял порядок элементов с одинаковыми значеними? Чем плохо собрать их в ведра (бакеты), а потом каждое ведро раскидать равномерно по массиву?

К>Если это так, то почему бы не сделать алгоритм, обратный сортировке (т.е. random_shuffle), но при этом стабильный.
К>То есть, чтоб выполнялось stable_sort(stable_shuffle(xs)) == stable_sort(xs)
К>Ещё одно требование — это равномерность, т.е. чтобы генерируемые перестановки были равновероятны.
К>Навскидку, я знаю тупой алгоритм с квадратной сложностью. Кто лучше?

вешаем на каждый объект два тега:
(1) рандомный тег (64 или 128-битный).
(2) исходный индекс объекта в массиве.

Достаточно очевидно, что полученные тройки <Object, RandomTag, IndexTag> можно легко упорядочит таким образом, чтобы при сортировке сохранялась "стабильность", при этом остальные элементы перетасовывались рандомно.

Здравствуйте, С3141566=Z, Вы писали:

СZ>Т.е. тебе нужен random_shuffle который бы сохранял порядок элементов с одинаковыми значеними? Чем плохо собрать их в ведра (бакеты), а потом каждое ведро раскидать равномерно по массиву?

1. Дополнительная память.
2. Какое время?

Здравствуйте, watchyourinfo, Вы писали:

W>Достаточно очевидно, что полученные тройки <Object, RandomTag, IndexTag> можно легко упорядочит таким образом, чтобы при сортировке сохранялась "стабильность", при этом остальные элементы перетасовывались рандомно.

Вообще неочевидно.

Поле Index уникально, поле Random — может быть уникально (ничего нельзя сказать).
Поэтому лексикографическое сравнение по ключу
— <Index,...> — эквивалентно сравнению по <Index>, сортировка приведёт к тривиальной перестановке
— <Random,...> — с большой вероятностью (если не налетим на коллизии случайного ключа) даст нестабильное random_shuffle
— <Object,Index,...> — стабильная сортировка в чистом виде
— <Object,Random,...> — нестабильная (я бы сказал, дестабилизирующая) сортировка

Здравствуйте, Кодт, Вы писали:


К>1. Дополнительная память.
Так вроде не было ничего про нее?
К>2. Какое время?
В бакеты собрать O(N*log(N)), раскидать считать надо. cкорее всего будет O(M * log(M) ).

К>1. Дополнительная память.
К>2. Какое время?

память да.

Время, если рандомные теги не проблема, то O(N*lgN) очевидно.

Если быть педантичными, то нужно учитывать вероятность коллизий рандомных тегов (и что-то предпринимать в этом случае). А тогда worst case убегает далеко. То есть тут среднюю сложность нужно считать, а не worst case.

Здравствуйте, С3141566=Z, Вы писали:

К>>1. Дополнительная память.
СZ>Так вроде не было ничего про нее?

Приветствуются любые варианты. Можно с дополнительной памятью, можно без.

К>Вообще неочевидно.

К>Поле Index уникально, поле Random — может быть уникально (ничего нельзя сказать).
К>Поэтому лексикографическое сравнение по ключу
К>- <Index,...> — эквивалентно сравнению по <Index>, сортировка приведёт к тривиальной перестановке
К>- <Random,...> — с большой вероятностью (если не налетим на коллизии случайного ключа) даст нестабильное random_shuffle
К>- <Object,Index,...> — стабильная сортировка в чистом виде
К>- <Object,Random,...> — нестабильная (я бы сказал, дестабилизирующая) сортировка


рандомные теги мы считаем уникальными. Что очевидно достигается на практике, битность тега увеличиваем, если что.

Лексикографическое сравнение, конечно, здест не годится.

typedef std::tuple<Type, RandomTag, IndexTag> Triple;

bool operator<(Triple lhs, Triple rhs) {
    if (std::get<0>(lhs) == std::get<0>(rhs)) {
        return std::get<2>(lhs) < std::get<2>(rhs);
    }
    return std::get<1>(lhs) < std::get<1>(rhs);
}

Здравствуйте, watchyourinfo, Вы писали:

W>Если быть педантичными, то нужно учитывать вероятность коллизий рандомных тегов (и что-то предпринимать в этом случае). А тогда worst case убегает далеко. То есть тут среднюю сложность нужно считать, а не worst case.

Можно и худший случай оценить.
Опять же, какой случай будет худшим? Набор из элементов, принимающих одно значение, или поровну два значения, или что-нибудь экзотическое — N^2 элементов, принимающих N разных значений?

Здравствуйте, watchyourinfo, Вы писали:

W>Лексикографическое сравнение, конечно, здест не годится.
W>

W>typedef std::tuple<Type, RandomTag, IndexTag> Triple;

W>bool operator<(Triple lhs, Triple rhs) {
W>    if (std::get<0>(lhs) == std::get<0>(rhs)) {
W>        return std::get<2>(lhs) < std::get<2>(rhs);
W>    }
W>    return std::get<1>(lhs) < std::get<1>(rhs);
W>}
W>

Тогда докажи, что этот порядок тотальный. В чём я лично сомневаюсь.

Да собственно, вот тебе контрпример.
Набор ['x','x','y']
Кортежи [ ('x',789,0), ('x',123,1), ('y',456,2) ]

('x',123,1) < ('y',456,2) < ('x',789,0)
('x',123,1) > ('x',789,0)

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, С3141566=Z, Вы писали:

К>>>1. Дополнительная память.
СZ>>Так вроде не было ничего про нее?

К>Приветствуются любые варианты. Можно с дополнительной памятью, можно без.
Ну с дополнительной памятью O(N). Записываем все свободные ячейки в массиве. Берем очередное ведро (случайно или не случайно хороший вопрос) размером m. Берем фишера за йетса (толи O(m) толи O(m) * (1- экспоненциальная шняжка), вычеркиваем m свободных ячеек. В этим m ячеек суем содержимое ведра. C остальными работаем начиная с первого шага. Если ты жулик, то посчитаешь общее время -- O(n) (т.к. хэш таблица) + O(m)*(n/m), если нет, то O(n*log(n))

К>Навскидку, я знаю тупой алгоритм с квадратной сложностью. Кто лучше?

Тупой алгоритм без доп.памяти выглядит так

vector<T> data;

int const n = data.size();

// группируем элементы, чтобы одинаковые шли подряд
stable_sort(data.begin(), data.end());
// (можно не сортировать, но это будет многословно)
for(auto it = data.begin();
         it != data.end();
         it = stable_partition(it+1,data.end(),[it](T const& x) { return x==*it; })
   )
{}

// на итераторах лень переписывать, извините
int n = data.size();
for(int m = n; m >= 0; --m) {
  // предусловие: [0..m) ещё не перемешаны, и сгруппированы
  //              [m..n) уже перемешаны, их трогать нельзя
  int i = rand() % m; // i <- [0..m)
  while(i+1 < m && data[i] == data[i+1]) ++i; // находим последний элемент в группе
  // переносим data[i] в начало замороженной зоны
  rotate(data.begin()+i, data.begin()+i+1, data.begin()+m);
}

Если сплавить фазы группировки и перетасовки, можем выбросить группировку, и получить такую схему

for(i = 0; i < n; ++i) {
  // [0;i) перетасовано и заморожено, [i;n) - расходуется
  int r = i + rand() % (n-i);  // r <- [i;n)
  iterator q = find(data.begin()+i, data.begin()+r+1, data[r]); // находим первый элемент, равный случайно выбранному
  rotate(data.begin()+i, q, q+1); // переносим его в хвост замороженной зоны
}

Она тоже квадратная (хотя бы в силу того, что делаем вставку).

Здравствуйте, Кодт, Вы писали:

К> Бредятинка родилась в ходе трёпа-охаивания разных алгоритмов сортировки.
А если тупо подобрать какой-нибудь алгоритм стабильной сортировки и подсунуть ему функцию сравнения:
compare(x, y) { x == y ? 0 : randomMinusOneOrPlusOne() }
?

Как подбирать алгоритм не знаю.. Но как минимум какой-нибудь из тех, который не падает от нетранзитивного сравнения. Merge sort вроде должен прокатить.

Здравствуйте, ·, Вы писали:

·>А если тупо подобрать какой-нибудь алгоритм стабильной сортировки и подсунуть ему функцию сравнения:
·>compare(x, y) { x == y ? 0 : randomMinusOneOrPlusOne() }

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

Кроме того, "не падает" != "работает". Нарушение транзитивности обрушивает много чего в свойствах алгоритма.

Возьмём то же слияние. Допустим, у нас массив [a0 a1 a2 b3 b4 c5 c6 c7] (буква — значение, цифра — порядковый номер).\
Разбили пополам, [a0 a1 a2 b3], [b4 c5 c6 c7]
Случайно перетасовали каждую половинку, — допустим, что перетасовка оказалась тривиальной.
Теперь выполняем слияние.
1) a0 против b4 — поскольку randomMinusOneOrPlusOne(), то выбрали b4.
2) продолжаем слияние дальше... но увы, порядок уже нарушен, потому что b3 заведомо окажется позади.

К>Тогда докажи, что этот порядок тотальный. В чём я лично сомневаюсь.
К>Да собственно, вот тебе контрпример.

согласен, я обосрался.

Тогда так:
(1) стабильно сортируем;
(2) за один проход навешиваем на каждый элемент RandomTag, но при этом навешиваем один и тот же тэг на одинаковые элементы (это легко так как они уже сгруппированы после шага 1);
(3) стабильно сортируем по тегу

Здравствуйте, watchyourinfo, Вы писали:

W>(1) стабильно сортируем;
W>(2) за один проход навешиваем на каждый элемент RandomTag, но при этом навешиваем один и тот же тэг на одинаковые элементы (это легко так как они уже сгруппированы после шага 1);
W>(3) стабильно сортируем по тегу

Твоя процедура состоит в том, что ты строишь случайную биективную (биективную ли?) функцию f из множеством фактических значений исходного типа элементов на, например, подмножество целых чисел. И сортируешь по ключу f(x).
Хоть стабильно, хоть нестабильно, но одинаковые элементы получают одинаковые ключи (а разные получают разные? как это обеспечить?) и после сортировки оказываются рядом.

Лучше сделать по-другому.
1) стабильно сортируем — точнее, стабильно группируем одинаковые элементы вместе (это более слабое требование, чем сортировка)
2) каждой серии одинаковых элементов навешиваем возрастающую случайную последовательность чисел из диапазона [0..M), где M — достаточно большое число
(как минимум, оно должно быть не меньше мощности самой большой серии одинаковых элементов; но можно взять за M размер всего массива или даже INT_MAX)
3) сортируем по этому ключу (нестабильно)

Основная сложность тут состоит в том, чтобы обеспечить (доказать) равномерность перемешивания.

Здравствуйте, Кодт, Вы писали:

К>Лучше сделать по-другому.
К>1) стабильно сортируем — точнее, стабильно группируем одинаковые элементы вместе (это более слабое требование, чем сортировка)
К>2) каждой серии одинаковых элементов навешиваем возрастающую случайную последовательность чисел из диапазона [0..M), где M — достаточно большое число
К>(как минимум, оно должно быть не меньше мощности самой большой серии одинаковых элементов; но можно взять за M размер всего массива или даже INT_MAX)
К>3) сортируем по этому ключу (нестабильно)

К>Основная сложность тут состоит в том, чтобы обеспечить (доказать) равномерность перемешивания.

Если уж делать (1), а потом развешивать тэги, то есть иметь по доп. int'у на ячейку, то проще сделать по-другому!
Просто раздаём случайные тэги ВСЕМ элементам массива, а потом на тэгах, соответствующим плато (отрезкам одинаковых исходных объектов) проводим сортировку тэгов. Ну и потом сортируем уже весь массив по тэгам...

По асимптоте получим те же O( N lnN ), в расходе памяти те же int на элемент, а перестановка гарантированно такая, какую хотим сгенерить...