按元素（数组的子数组中的元素）降序对序列（数组中的子数组）进行排序

Question

几天来我一直在尝试使用 C# 找到解决此问题的方法。我能够按长度对它们进行排序，但我无法找出从最左边到最右边对数组进行排序的解决方案。

他们给出的提示是定义一个class序列来保存元素序列。我们将实现 IComparable<Sequence> 以递减顺序按长度比较序列（当长度相同时按递减顺序排列元素）。稍后我们将使用我们的 TreeMultiSet class。在内部，我们将保留 S 的前 10 个子序列，即 P 的幸运子序列的多集，按长度降序排列（当长度相同时，按内容降序排列）。当我们在多集中有 10 个子序列并且我们添加第 11 个序列时，它会在顺序中占据正确的位置，因为 IComparable<Sequence> 定义。之后我们可以删除第 11 个子序列，因为它不在前 10

这是问题所在：

给定一个包含 L 个整数 L（1 < L < 50,000）和一个数字 N 的序列 P。我们称 P 中整数的每个子序列为“幸运子序列”，其总和等于 N . 假设我们有一个序列 S，包含 P 的所有幸运子序列，并按长度降序排列。当长度相同时，序列按其元素降序排列：从最左边到最右边。编写一个程序来 return S

的前 10 个元素

示例：给定 N = 5 和序列 P = {1, 1, 2, 1, -1, 2, 3, -1, 1, 2, 3, 5, 1, -1, 2, 3}。序列S由P的以下13个子序列组成：

[1, -1, 2, 3, -1, 1] 
[1, 2, 1, -1, 2]
[3, -1, 1, 2]
[2, 3, -1, 1]
[1, 1, 2, 1]
[1, -1, 2, 3]
[1, -1, 2, 3]
[-1, 1, 2, 3]
[5, 1, -1]
[2, 3]
[2, 3] 
[2, 3]
[5]

我的解决方案：

其实看提示的时候没看懂所以想了个办法

class Find
    {
        //Function to manually create an array with N elements
        public static int[] ArrCreate(int n, int[] Arr)
        {
            for (int i = 0; i < n; i++)
            {
                Arr[i] = Convert.ToInt32(Console.ReadLine());
            }
            return Arr;
        }
        //Create a Dictionary class type to hold sub-array with sum of sub-array equal to given number k
        public static Dictionary<int, ArrayList> SubSeqEqual2N()
        {
            Console.WriteLine("Input k: ");
            int k = Convert.ToInt32(Console.ReadLine());
            Console.WriteLine("Input n element to create an Array: ");
            int n = Convert.ToInt32(Console.ReadLine());
            int[] Arr = new int[n];
            int[] newArr = ArrCreate(n, Arr);
            int keyIndex = 0;
            //ArrayList arlist = new ArrayList();
            Dictionary<int, ArrayList> SeqofLuckyArr = new Dictionary<int, ArrayList> { };
            //Create a loop to find sub-array with the sum equal to given number K.
            for (int i = 0; i < newArr.Length; i++)
            {
                int sum = 0;
                for (int j = i; j < newArr.Length; j++)
                {
                    sum = sum + newArr[j];
                    if (sum == k)
                    { 
                        //When sub-array with the sum equal to given number K is found then add them into a temp Arraylist, also increment the keyIndex.
                        keyIndex++;
                        ArrayList temp = new ArrayList();
                        for (int ko = i; ko <= j; ko++)
                        {
                            temp.Add(newArr[ko]);
                        }
                        //DEBUG PURPOSE
                        /*Console.Write("{");
                        foreach (var hehe in temp)
                        {
                            
                            Console.Write("{0}", string.Join(", ", hehe));
                            
                        }
                        Console.Write("}");
                        Console.WriteLine("");
                        arlist.AddRange(temp);*/
                        //Then add that temp array as value into a Dictionary <key,value>type with that KeyIndex.
                        SeqofLuckyArr.Add(keyIndex,temp);
                    }
                }
            }
            //DEBUG PURPOSE
            //My method to sort the sub-array in the Dictionary by sub-array length and by key index.
            foreach(KeyValuePair<int,ArrayList> kvp in SeqofLuckyArr.OrderByDescending(x => x.Value.Count).ThenBy(y => y.Key))
            {
                Console.Write("Key={0} ",kvp.Key);
                Console.Write(",");
                Console.Write("Value={ ");
                foreach (var hoho in kvp.Value)
                {
                    Console.Write("{0} ", string.Join(", ", hoho));
                }
                Console.WriteLine("}");
                Console.WriteLine("");
                arlist.AddRange(kvp.Value);
            }
            //DEBUG PURPOSE
            return SeqofLuckyArr;
        }
    }

我尝试先找到和等于给定数字K的子数组，然后将它们作为值添加到字典中，其键作为索引。然后使用 OrderByDecreasing 方法按长度对子数组进行排序。

结果：

Key=4 ,Value={ 1 -1 2 3 -1 1 }

Key=2 ,Value={ 1 2 1 -1 2 }

Key=1 ,Value={ 1 1 2 1 }

Key=3 ,Value={ 1 -1 2 3 }

Key=6 ,Value={ 2 3 -1 1 }

Key=7 ,Value={ 3 -1 1 2 }

Key=8 ,Value={ -1 1 2 3 }

Key=12 ,Value={ 1 -1 2 3 }

Key=11 ,Value={ 5 1 -1 }

Key=5 ,Value={ 2 3 }

Key=9 ,Value={ 2 3 }

Key=13 ,Value={ 2 3 }

Key=10 ,Value={ 5 }

但是结果和例子不一样。我的问题是我卡在“当长度相同时，序列按其元素降序排列：从最左边到最右边”。正如我所想的从最左到最右是子数组的关键索引从低到高。

谁能帮我找到按元素降序排列子数组的合适方法？如果我的版本也不适合在SO上提问我会删除我的问题。

谢谢！

Answer 1

看来问题只出在您的订单上。序列的内容与示例相同。

首先，您订购的线路不完全符合指定的规则：

foreach(KeyValuePair<int,ArrayList> kvp in SeqofLuckyArr
                                           .OrderByDescending(x => x.Value.Count)
                                           .ThenBy(y => y.Key))

[...] kept in decreasing order by their length. When the length is the same, the sequences are ordered in decreasing order by their elements: [...]

第一个顺序似乎是正确的 (OrderByDescending(x => x.Value.Count))，按序列长度的降序排列。第二次排序目前按序列的“关键索引”和升序排列。根据“幸运子序列”的内容，这应该是 descending/decreasing (ThenByDescending) 顺序。

解决所有这些问题的一种方法是引入一个 IComparer 实现，该实现有点类似于给定的提示。下面的 IComparer 能够将两个序列 (int[]) 作为输入并判断两个序列中的哪一个应该出现在另一个序列之前（请参阅 the documentation 以了解 return IComparer.Compare 的值表示：

public class IntArrayComparer : IComparer<int[]>
{
    public int Compare(int[] x, int[] y)
    {
        // Ensure we don't get a null-ref exception further down
        if (x == null || y == null)
            // x should come before (-1) or after (1) y (default ascending order)
            return y == null ? -1 : 1;
        
        // If the lengths are different, the length is the first ordering priority
        if (x.Length != y.Length)
            // Use the built-in 'CompareTo' method for the 'int' type
            return x.Length.CompareTo(y.Length);
        
        // Lengths are the same, so we compare the contents
        for (var i = 0; i < x.Length; i++)
        {
            var comparison = x[i].CompareTo(y[i]);
            // If the elements in the two seq. are different, we return the ordering
            if (comparison != 0)
                return comparison;
        }
        return 0;
    }
}

现在前面提到的你的订单行变得更简单了（主观意见:)）：

foreach(KeyValuePair<int,ArrayList> kvp in SeqofLuckyArr
                                           .OrderByDescending(x => x.Value, new IntArrayComparer()))

查看 this fiddle 以测试运行订购部分。

提示：实际上您甚至不需要将子序列存储在 Dictionary 中 - List 就足够了。

Answer 2

抱歉回复晚了。在参考上面的 Imcomparer 实现之后。我能够获得与示例相同的输出。这是我的代码，供遇到与我相同问题的任何人使用。

class Find
    {
        public static int[] ArrCreate(int n, int[] Arr)
        {
            for (int i = 0; i < n; i++)
            {
                Arr[i] = Convert.ToInt32(Console.ReadLine());
            }
            return Arr;
        }
        public static void SubSeqEqual2N()
        {
            Console.WriteLine("Input k: ");
            int k = Convert.ToInt32(Console.ReadLine());
            Console.WriteLine("Input n element to create an Array: ");
            int n = Convert.ToInt32(Console.ReadLine());
            int[] Arr = new int[n];
            int[] newArr = ArrCreate(n, Arr);
            //int keyIndex = 0;
            //ArrayList arlist = new ArrayList();
            //Dictionary<int, ArrayList> SeqofLuckyArr = new Dictionary<int, ArrayList> { };
            
            //Create a List of int array to store 
            List<int[]> luckyArray = new List<int[]>{ };
            for (int i = 0; i < newArr.Length; i++)
            {
                int sum = 0;
                for (int j = i; j < newArr.Length; j++)
                {
                    sum = sum + newArr[j];
                    if (sum == k)
                    {
                        //keyIndex++;
                        ArrayList temp = new ArrayList();
                        for (int ko = i; ko <= j; ko++)
                        {
                            temp.Add(newArr[ko]);
                        }

                        //Convert ArrayList temp into int array for applying IComparer.Compare<Int[],Int[]>
                        int[] luckySubArray = temp.ToArray(typeof(int)) as int[];
                        luckyArray.Add(luckySubArray);

                        //SeqofLuckyArr.Add(keyIndex,temp);
                    }
                }
            }
            var orderedSeq = luckyArray.OrderByDescending(s => s, new IntArrayComparer());           
            foreach(var seq in orderedSeq)
            {
                Console.Write("[ ");
                foreach (var i in seq)
                {
                    Console.Write("{0} ", string.Join(", ", i));
                }
                Console.Write(" ]");
                Console.WriteLine("");
            }

        }
    }
    public class IntArrayComparer : IComparer<int[]>
    {
        public int Compare(int[] x, int[] y)
        {
            // Ensure we don't get a null-ref exception further down
            if (x == null || y == null)
                // x should come before (-1) or after (1) y (default ascending order)
                return y == null ? -1 : 1;

            // If the lengths are different, the length is the first ordering priority
            if (x.Length != y.Length)
                // Use the built-in 'CompareTo' method for the 'int' type
                return x.Length.CompareTo(y.Length);

            // Lengths are the same, so we compare the contents
            for (var i = 0; i < x.Length; i++)
            {
                var comparison = x[i].CompareTo(y[i]);
                // If the elements in the two seq. are different, we return the ordering
                if (comparison != 0)
                    return comparison;
            }
            return 0;
        }
    }

并且输出：

[ 1 -1 2 3 -1 1  ]
[ 1 2 1 -1 2  ]
[ 3 -1 1 2  ]
[ 2 3 -1 1  ]
[ 1 1 2 1  ]
[ 1 -1 2 3  ]
[ 1 -1 2 3  ]
[ -1 1 2 3  ]
[ 5 1 -1  ]
[ 2 3  ]
[ 2 3  ]
[ 2 3  ]
[ 5  ]

按元素（数组的子数组中的元素）降序对序列（数组中的子数组）进行排序

Sort a sequence (a sub-array in a array) in decreasing order by their elements (elements in the sub-array of an array)

c#

icomparable