Создание случайного упорядоченного списка из упорядоченного списка

Question

У меня есть приложение, которое принимает результаты качества для производственного процесса и создает графики как для отображения диаграмм Парето плохих, так и для отображения производительности.

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

Одна из идей, которые у меня возникли, состоит в том, чтобы заполнить список хорошими номерами i, плохими номерами j, плохими номерами k и т. Д. И затем каким-то образом случайным образом отсортировать список перед вставкой в ​​базу данных.

Итак, мой вопрос, существует ли стандартный алгоритм для получения отсортированного списка значений и создания случайно отсортированного списка?

Answer 1

Вы захотите использовать алгоритм перемешивания . Убедитесь, что вы используете правильный алгоритм перемешивания, а не домашний, потому что он может вводить в данные некоторую форму неуловимого шаблона. См. этот пост Джеффа Этвуда о проблеме с использованием "достаточно случайных" перемешиваний.

Answer 2

Есть несколько готовых реализаций, таких как http://msdn.microsoft.com/en-us/library/bb385047.aspx и http://java.sun.com/javase/6/docs/api/java/util/Collections.html#shuffle(java.util.List)

Answer 3

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

Answer 4

Random rnd = new Random();
List<int> orderedList = new List<int>();
List<int> randomList = new List<int>();
while (orderedList.Count != 0)
{
    int index = rnd.Next(0, orderedList.Count);
    randomList.Add(orderedList[index]);
    orderedList.RemoveAt(index);
}

Answer 5

Зависит от того, что вам нужно для «случайности». Вероятно, самый простой способ - просто перебрать все элементы в хэш-набор и выполнить итерацию по результату. Порядок, который вы получите, будет детерминированным, но для большинства намерений и целей его можно считать случайным. Кроме того, вы можете генерировать случайные числа между [0..length] списка, выбирая элементы и помещая их в новый список. Предполагая, что удаление списка является постоянным временем, результатом будет случайный список, сгенерированный с эффективностью O (n).

Answer 6

Я использовал для этого цикл, который выполнялся несколько раз и генерировал два случайных числа в диапазоне от 0 до длины списка, а затем менял эти два элемента.

Answer 7

У нашего хозяина есть очень хорошая статья о перетасовке карт, я думаю, что некоторые хорошие идеи могут быть приняты
http://www.codinghorror.com/blog/archives/001008.html