I have been trying for days to find a solution for this problem using c#. I was able to sort them by length but I cannot figure out the solution to sort the array by from their left-most to their right-most.
The hint they gave is to define a class Sequence to hold a sequence of elements. We will implement IComparable<Sequence> to compare sequences by length in decreasing order (and by elements in decreasing order when the length is the same). Later we will use our TreeMultiSet class. Inside we will keep the first 10 sub-sequences of S, i.e. multi-set of the lucky sub-sequences of P, kept in decreasing order by length (and in decreasing order of their content when the length is the same). When we have 10 sub-sequences inside the multi-set and we add 11th sequence, it would take its correct place in the order, because of the IComparable<Sequence> defined. After that we can delete the 11th subsequence, because it is not amongst the first 10
Here is the problem:
We are given a sequence P containing L integers L (1 < L < 50,000) and a number N. We call a “lucky sub-sequence within P” every subsequence of integers from P with a sum equal to N. Imagine we have a sequence S, holding all the lucky sub-sequences of P, kept in decreasing order by their length. When the length is the same, the sequences are ordered in decreasing order by their elements: from the leftmost to the rightmost. Write a program to return the first 10 elements of S
Example: We are given N = 5 and the sequence P = {1, 1, 2, 1, -1, 2, 3, -1, 1, 2, 3, 5, 1, -1, 2, 3}. The sequence S consists of the following 13 sub-sequences of P:
[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]
My solution:
Actually, when reading the hint I was not able to understand the idea so I came up with another way.
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;
}
}
I try to find the sub-array with the sum equal to the given number K first then add them into the Dictionary as value with its key as index. Then sort -sub-array by length use OrderByDecreasing method.
The result:
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 }
But the result is not the same as the example. My problem is that I am stuck at "When the length is the same, the sequences are ordered in decreasing order by their elements: from the leftmost to the rightmost". As I thought left-most to right most is the key index of the sub-array from low to high.
Can anyone help me to find the appropriate way to order the sub-array in decreasing order by the elements? If my edition is not also appropriate to ask on SO I will delete my question.
Thank you!
It seems the problem lies solely in your ordering. The contents of the sequences are identical to the example.
First, the line you are ordering doesn't quite follow the rules specified:
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: [...]
The first ordering seems correct (OrderByDescending(x => x.Value.Count)) by descending order of the sequences' length. The second ordering is currently ordered by the sequences' "key index" and in ascending order. This should have been in descending/decreasing (ThenByDescending) order based on the contents of the "lucky sub-sequences".
One way you can fix all this is by introducing an IComparer implementation a bit similar to the hint given. The IComparer below is able to take two sequences (int[]) as input and tell which of the two should come before the other (see the documentation for an explanation of what the return value of IComparer.Compare means):
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;
}
}
Now the previous mentioned line with your ordering becomes a little simpler (subjective opinion :)):
foreach(KeyValuePair<int,ArrayList> kvp in SeqofLuckyArr
.OrderByDescending(x => x.Value, new IntArrayComparer()))
Check out this fiddle for a test run of the ordering part.
Hint: You actually don't even need to store your subsequences in a Dictionary - a List would suffice.