2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Частично упорядоченная последовательность
Сообщение27.03.2015, 19:17 
Аватара пользователя
Надо сгенерировать частично упорядоченную последовательность производной длины, чтобы затем сравнить скорость ее обработки разными алгоритмами.
Как это можно реализовать? Самое тупое - разбить массив на две части, первую часть заполнить случайно, а вторую - в определенном порядке.
Но, может быть, можно использовать какую-нибудь медленно возрастающую функцию, которая дает целые значения и на некотором отрезке много раз меняет монотонность, а потом стабилизируется?
Или, может, заполнить массив элементами идеалов достаточно большого числового кольца $Z/nZ$? Как раз получится набор упорядоченных множеств, но при этом сам массив упорядочен не будет.

 
 
 
 Re: Частично упорядоченная последовательность
Сообщение27.03.2015, 20:01 
Вы сейчас под частично упорядоченной последовательностью понимаете частично упорядоченное множество или нет?
Если да, то описанные алгоритмы Вам не помогут, если нет, то непонятно, что Вы хотите. $(1;3;2;4)$ является частично упорядоченной последовательностью или нет?

 
 
 
 Re: Частично упорядоченная последовательность
Сообщение27.03.2015, 20:05 
Аватара пользователя
Sonic86 в сообщении #996627 писал(а):
Вы сейчас под частично упорядоченной последовательностью понимаете частично упорядоченное множество или нет?
Если да, то описанные алгоритмы Вам не помогут, если нет, то непонятно, что Вы хотите. $(1;3;2;4)$ является частично упорядоченной последовательностью или нет?

Я не знаю, что понимается под этим. Сказано "частично упорядоченная последовательность" чисел, и все. Вряд ли это имеет отношение к теории множеств.

 
 
 
 Re: Частично упорядоченная последовательность
Сообщение27.03.2015, 20:17 
Сгенерируйте упорядоченную последовательность и случайно поменяйте местами несколько элементов

 
 
 
 Re: Частично упорядоченная последовательность
Сообщение27.03.2015, 20:30 
Аватара пользователя
Progger в сообщении #996639 писал(а):
Сгенерируйте упорядоченную последовательность и случайно поменяйте местами несколько элементов

И правда ведь. Отличная идея.

 
 
 
 Re: Частично упорядоченная последовательность
Сообщение27.03.2015, 21:51 

(Оффтоп)

Nurzery[Rhymes] в сообщении #996629 писал(а):
Sonic86 в сообщении #996627 писал(а):
Вы сейчас под частично упорядоченной последовательностью понимаете частично упорядоченное множество или нет?
Если да, то описанные алгоритмы Вам не помогут, если нет, то непонятно, что Вы хотите. $(1;3;2;4)$ является частично упорядоченной последовательностью или нет?

Я не знаю, что понимается под этим. Сказано "частично упорядоченная последовательность" чисел, и все. Вряд ли это имеет отношение к теории множеств.
Nurzery[Rhymes] в сообщении #996646 писал(а):
Progger в сообщении #996639 писал(а):
Сгенерируйте упорядоченную последовательность и случайно поменяйте местами несколько элементов

И правда ведь. Отличная идея.
Видимо, типичный программизм :|

 
 
 
 Re: Частично упорядоченная последовательность
Сообщение27.03.2015, 22:25 
Неупорядоченность бывает разная. Например, перестановка минимального элемента в конец.

 
 
 
 Re: Частично упорядоченная последовательность
Сообщение27.03.2015, 22:48 
Аватара пользователя
Я уточнил, что требуется.
Цитата:
Насчет частично упорядоченной Вы совершенно правы. Сколько таких кусков
и какой они длины - на Ваш вкус. Скажем, если вся последовательность
состоит из 10000 элементов, то каждый кусок можно взять длиной 100
(корень из 10000).

Да, свапнуть несколько элементов будет достаточно)

 
 
 
 Re: Частично упорядоченная последовательность
Сообщение27.03.2015, 23:32 
Мой пример характерен тем, что хотя почти вся последовательность отсортирована, тем не менее ни один элемент не находится на своём месте.

 
 
 [ Сообщений: 9 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group