Сортировать 3 списка в соответствии с их значениями

Question

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

Соотношение сортировки:

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

public static bool isGreater(List<double> first, List<double> second)
        {
            int firstCounter = 0;
            int secondCounter = 0;

            for (int i = 0; i < first.Count; i++)
            {
                if (first.ElementAt(i) > second.ElementAt(i))
                {
                    firstCounter++;
                }
                else if (first.ElementAt(i) < second.ElementAt(i))
                {
                    secondCounter++;
                }
            }

            if (firstCounter > secondCounter)
            {
                return true;
            }
            else
            {
                return false;
            }
        }

Но как я могу адаптировать этот код для 3 или даже n списков?

Answer 1

Что вам нужно сделать sort () коллекция списков, основанная на вашем определении порядка. Вы должны быть в состоянии использовать стандартную сортировку и предоставить ей свою функцию заказа.

Алгоритм будет выглядеть примерно так:

1. Создайте массив списков, которые вы хотите отсортировать.
2. Вызовите стандартный метод sort () для массивов, используйте процедуру, определенную выше, в качестве функции сравнения.

EDIT: Этот алгоритм должен дать вам максимум в O (M N lgN) (N списков каждого размера M). Я знаю немного более быстрый (логарифмический фактор) рандомизированный алгоритм, чтобы найти макс. Вы можете прочитать об этом здесь . Я бы не рекомендовал реализовывать этот алгоритм, если у вас нет огромного количества списков для обработки.

Answer 2

Вы должны быть в состоянии сделать это, используя LINQ и пользовательский IComparer для IEnumerable<double>.

public class EnumerableDoubleComparer : IComparer<IEnumerable<double>>
{
    public int Compare( IEnumerable<double> a, IEnumerable<double> b )
    {
        var counts = a.Select( (k,i) => new { Value = k, Index = i } )
                      .Join( b.Select( (k,i) => new { Value = k, Index = i } ),
                             outer => outer.Index,
                             inner => inner.Index,
                             (outer,inner) => outer.Value > inner.Value
                                                  ? "A"
                                                  : (inner.Value > outer.Value
                                                        ? "B"
                                                        : "" ) )
                      .GroupBy( listID => listID )
                      .Select( g => new { g.Key, Count = g.Count() } );

        // you could also use SingleOrDefault on the collection and check for null
        var aCount = counts.Where( c => c.Key == "A" )
                           .Select( c => c.Count )
                           .SingleOrDefault();
        var bCount = counts.Where( c => c.Key == "B" )
                           .Select( c => c.Count )
                           .SingleOrDefault();

        return aCount - bCount;
    }
}

Используется как:

var a = new double[] { 1, 1 };
var b = new double[] { 2, 2 };
var c = new double[] { 3, 3 };

var lists = new List<IEnumerable<double>> { a, c, b };

var ordered = lists.OrderByDescending( l => l, new EnumerableDoubleComparer() );

Answer 3

Пока количество элементов в каждом списке одинаково и известно, вот небольшой пример, который я обработал:

const int listSize = 6;

List<int> one = new List<int> { 0, 1, 2, 3, 4, 5 };
List<int> two = new List<int> { 10, 1, 9, 2, 8, 3 };
List<int> three = new List<int> { 5, 5, 5, 5, 5, 5 };

Dictionary<List<int>, int> lists = new Dictionary<List<int>, int>()
{
    {one, 0},
    {two, 0},
    {three, 0}
};

for (int i = 0; i < listSize; i++)
{
    var sortedAtIndex = lists.Keys.OrderByDescending(k => k[i]);
    lists[sortedAtIndex.ElementAt(0)]++;
}

// And to show you that it works...
foreach (var element in lists.OrderByDescending(k => k.Value)
    .Select(k => k.Key))
{
    Console.WriteLine("{0}", lists[element]);
}

Answer 4

Мне кажется, что у вас есть «внешний» список «внутренних» списков, и вы хотите отсортировать «внешний» список. Вы можете сделать это:

// Set up some input data
var outerList = new List<List<double>>();
outerList.Add(new List<double> { 2.0, 3.0, 3.0 });
outerList.Add(new List<double> { 1.0, 2.0, 3.0 });
outerList.Add(new List<double> { 2.0, 2.0, 3.0 });

// Sort the outer list
outerList.Sort((first, second) => isGreater(first, second) ? 1 : -1);

На самом деле, вам, вероятно, лучше изменить isGreater (который не может вернуть результат "оба списка равны", что может привести к путанице) в функцию CompareLists, которая возвращает -1, если первый аргумент меньше второго , 1, если первый аргумент больше, чем второй, и 0, если они равны. Тогда вы можете просто позвонить:

outerList.Sort(CompareLists);

Answer 5

Я немного отредактировал твой метод и добавил еще один:

private static List<double> GetGreater(List<double> first, List<double> second)
{
    int firstCounter = 0;
    int secondCounter = 0;

    for (int i = 0; i < first.Count; i++)
    {
        if (first.ElementAt(i) > second.ElementAt(i))
        {
            firstCounter++;
        }
        else if (first.ElementAt(i) < second.ElementAt(i))
        {
            secondCounter++;
        }
    }

    // return the greater list instead of bool
    return (firstCounter > secondCounter ? first : second);
}


public static List<double> Greater(params List<double>[] p)
{
    // assumes the first list is the greater, then check the others
    // this method assumes you will always pass at least 2 lists

    List<double> greater = p[0];

    for (var i = 1; i < p.Length; ++i)
    {
        greater = GetGreater(greater, p[i]);
    }

    return greater;
}

static void Main(string[] args)
{
    // lists used for this test
    var l1 = new List<double>() { 1, 222, 3 };
    var l2 = new List<double>() { 1, 2, 4 };
    var l3 = new List<double>() { 11, 222, 333 };

    var l4 = Greater(l1, l2, l3); // l3
}

Answer 6

var list11 = new List<double> { 1, 2, 3 };
var list22 = new List<double> { 4, 5, 3 };
var list33 = new List<double> { 4, 1, 0 };

int acounter = 0, bcounter = 0, ccounter;
list11.Select((o, i) => new { a = list11[i], b = list22[i] })
    .Aggregate(0, (init, item) => item.a > item.b
                                        ? acounter++
                                        : item.a == item.b
                                            ? bcounter
                                            : bcounter++);
if (acounter > bcounter)
{
    //Do the same for list11 and list33
}
else
{
    //Do the same for list22 and list33 
}

you can refactor it and write a function for two list and call that for every pair that you want.

Answer 7

Использовать массив для хранения счетчика для каждого списка.

Если у вас есть n списков. Ваш массив Counter

 void SortLists(List<List<double>> lists)
 {
 int[] counter = new int[lists.Count];

 for (int i = 0; i < lists[0].Count; i++)
 {
     double MaxValue = double.MinValue;
     int winningList = 0;

     for (int j = 0; j < lists.Count; j++)
     {
        if(lists[j].ElementAt(i) > MaxValue )
        {
            MaxValue = lists[j].ElementAt(i);
            winningList = j;
        }
     }

     counter[winningList]++;
 }

 // sort the counter array, in effect your lists are sorted.
 }

Answer 8

Во-первых, не будет ли проще использовать уже отсортированную коллекцию?

Для этого можно использовать Сортированный диктонар .

Что касается вашего вопроса о том, как применить его к n-спискам, используйте рекурсию, просто используйте коллекцию и следите за последним результатом. Это позволит вам сравнить первый и третий список, например, если результат первой итерации вашей рекурсивной функции возвращает первый список.

Answer 9

Множественность списков - иллюзия - список только один, но у каждого элемента есть атрибут, определяющий, из какого он списка.

Слияние списков, сортировка, а затем разделение на исходные списки.