CODEWITHSUNDEEP
c#.net
Broom
Broom

Reputation: 596

Get array slices in length order

I have the following code to get a list of all possible slice start/end indexes, in order of descending slice length. I then iterate over the list and use it to slice up an array, breaking when I get a slice that I am looking for. I do this because I am looking for the largest slice that matches other parameters and I am looking to short cut past the other possible slices once I've found one.

I would prefer a couple of nested for loops to check the slice and move on, instead of having to get every possible range and sort them first, since the array can be up to a billion or so items large. I can't for the life of me figure out how to do it, or even how to phrase the question to search for it. Any help is appreciated.

byte[] data1 = { 54, 87, 23, 87, 45, 67, 7, 85, 65, 65, 3, 4, 55, 76, 65, 64, 5, 6, 4, 54, 45, 6, 4 };

List<Tuple<int, int>> ranges = new List<Tuple<int, int>>();
for (int i1 = 0; i1 < data1.Count(); i1++)
{
    for (int i2 = i1 + 1; i2 < data1.Count(); i2++)
    {
        ranges.Add(new Tuple<int, int>(i1, i2));
    }
}


ranges = ranges.OrderByDescending(x => x.Item2 - x.Item1).ToList();

Upvotes: 1

Views: 184

Answers (3)

Broom
Broom

Reputation: 596

I figured it out. Here's what I needed, to iterate over each array slice in reverse length order.

byte[] data1 = { 54, 87, 23, 87, 45, 67, 7, 85, 65, 65, 3, 4, 55, 76, 65, 64, 5, 6, 4, 54, 45, 6, 4 };


for (int length = data1.Count() - 1; length > 0; length--)
{
    int numberOfSlicesForLength = data1.Count() - length;

    for (int start = 0; start < numberOfSlicesForLength; start++)
    {
        byte[] sliceValues = data1.Skip(start).Take(length);
    }
}

Upvotes: 0

Peter Duniho
Peter Duniho

Reputation: 70652

If I understand the question correctly, you are looking for the largest subarray of an array (which you are calling a "slice"…maybe a term from some other programming language?) that meets some specific conditions. In your question, you are unspecific about the conditions themselves, so I assume that part is not important.

It seems what you are having difficulty with is arranging your code so that you necessarily inspect the longest subarrays first.

If all of that is correct, then you just need to arrange your loops differently. Currently, you are picking a starting index and then finding all subarrays that start at that index. Instead, since you want the longest subarrays to be inspect first, you should pick the length of the subarray, starting with the longest possible length, and select all subarrays that can be that long.

For example:

for (int i = data1.Length; i > 0; i--)
{
    for (int j = 0; j < data1.Length - i + 1; j++)
    {
        // inspect subarray starting at index j, having length i
    }
}

Upvotes: 1

Dmitry Egorov
Dmitry Egorov

Reputation: 9650

You may enumerate the slices directly by a couple of nested loops:

bool found = false;
for (int sliceLen = data1.Length; !found && sliceLen > 0; sliceLen--)
    for (int sliceStart = 0; !found && sliceStart + sliceLen <= data1.Length; sliceStart++)
        if (found = (
            data1[sliceStart] == data1[sliceStart + sliceLen - 1]   // check your condition here
        ))
            Console.WriteLine($"Found: {sliceStart}:{sliceLen}");

Demo: https://ideone.com/lZRNJm

Upvotes: 1

Related Questions