Сортировка списка случайным образом по весам - PullRequest
Новая
       56

Сортировка списка случайным образом по весам

2 голосов
/ 03 апреля 2019

Идея состоит в том, что у меня есть список предметов, к каждому предмету прикреплен вес.Теперь я хочу рандомизировать порядок списка, но я также хочу принять во внимание вес, чтобы «сместить» процесс рандомизации.

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

Я знаю другие алгоритмы, которые дают ожидаемый результат.

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

Существует также другой алгоритм, который не требует создания диапазона, но ожидает, что начальный список будет в случайном порядке, а затем путем вычитания и проверки на x <=0, также принимает элементы один за другим, чтобы создать список случайного, но смещенного порядка элементов.Он выдает ожидаемые коэффициенты более миллиона попыток. </p>

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

Код C # для консольного приложения 

using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleTest1
{
    class Program
    {
        static void Main(string[] args)
        {
            var myList = new List<Item>
            {
                new Item { Name = "A70", Weight = 70},
                new Item { Name = "B20", Weight = 20},
                new Item { Name = "C10", Weight = 10},
            };

            var stats = new Dictionary<string, int>();
            myList.ForEach(x => stats.Add(x.Name, 0));

            var rnd = new Random();
            for (var i = 0; i < 1000000; ++i)
            {
                var newList = GetSorted(myList, rnd);
                ++stats[newList.First().Name];
            }

            var sum = stats.ToList().Sum(x => x.Value);
            stats.ToList().ForEach(x => Console.WriteLine($"{x.Key}: {((float)x.Value / sum * 100):0.00}%"));

            Console.ReadLine();
        }

        private static IEnumerable<Item> GetSorted(IEnumerable<Item> list, Random rnd)
        {
            return list
                .Select(x => new
                {
                    Order = x.Weight * rnd.NextDouble(),
                    Item = x
                })
                .OrderByDescending(x => x.Order)
                .Select(x => x.Item);
        }
    }

    class Item
    {
        public string Name { get; set; }
        public int Weight { get; set; }
    }
}

По этому коду я ожидаю, что вероятность каждого элемента будет впервая позиция списка должна быть очень похожа на вес каждого элемента.Вместо 70-20-10% я получаю примерно 85-13-2%.Похоже, что в игру вступает какая-то нелинейность, но я просто не понимаю этого сейчас.

Вопрос здесь состоит в том, чтобы понять, как работает данный код.Я знаю разные подходы, которые работают и дают ожидаемый результат.

Спасибо!

Ответы [ 2 ]

2 голосов
/ 03 апреля 2019

Вот объяснение.Для простоты рассмотрим более простой случай: 

var myList = new List<Item>
{
    new Item { Name = "A20", Weight = 20},
    new Item { Name = "B10", Weight = 10},
};

Мы определяем порядок сортировки путем умножения веса на случайное число.Если мы умножим вес A20 на любое число выше 0,5, он будет отсортирован первым, каким бы ни было случайное число для B10.Если мы умножим вес A20 на любое число ниже 0,5, то у него будет равный шанс с B10 на первое.Таким образом, распределение будет 75% / 25%, а не изначально интуитивно понятным 67% / 33%.

Чтобы исправить алгоритм, вы должны использовать квадратный корень из веса. 

.Select(x => new
{
    Order = Math.Sqrt(x.Weight) * rnd.NextDouble(),
    Item = x
})

Обновление: Квадрат не является хорошим решением.

0 голосов
/ 03 апреля 2019

Я исправил код для работы: 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication107
{
    class Program
    {
        static void Main(string[] args)
        {
             var myList = new List<Item>
            {
                new Item { Name = "A70", Weight = 70},
                new Item { Name = "B20", Weight = 90},
                new Item { Name = "C10", Weight = 100},
            };

            var stats = new Dictionary<string, int>();
            myList.ForEach(x => stats.Add(x.Name, 0));

            var rnd = new Random();
            for (var i = 0; i < 1000000; ++i)
            {
                var newList = GetSorted(myList, rnd);
                ++stats[newList.Name];
            }

            var sum = stats.ToList().Sum(x => x.Value);
            stats.ToList().ForEach(x => Console.WriteLine("{0}: '{1}", x.Key, ((float)x.Value / sum * 100)));

            Console.ReadLine();

        }
        private static Item GetSorted(List<Item> list, Random rnd)
        {
            Item results = null;
            int value = rnd.Next(0,100);
            for(int i = 0; i < list.Count(); i++)
            {
                if (value < list[i].Weight)
                {
                    results = list[i];
                    break;
                }
            }
            return results;
        }
    }

    class Item
    {
        public string Name { get; set; }
        public int Weight { get; set; }
    }
}
...