Danny Fox Danny Fox - 2 months ago 17
C# Question

Order List count 2 and 3 with respect to modulus 4

I have a list which I need to sort into an order provided it contains ALL of the numbers in its sequence:

Manually just setting them does not seem like the way to go about it.

I know how to order lists to be ascending or descending but having the modulus 4 is sending my head funny.

Modulus of 4 is due to this being linked to node neighbours on a grid

I do not know what order they are put into the list initially as it is random and changes every time - Procedural generation of grid connections

I do not want a new list, I just want to simply re-arrange the current one.

List Count of 3:

0, 1, 2

1, 2, 3

2, 3, 0

3, 0, 1

if (acceptedIndicies.Contains(0) && acceptedIndicies.Contains(1) && acceptedIndicies.Contains(2)) // Top-Right-Down
{
// Order List in the sequence
acceptedIndicies[0] = 0;
acceptedIndicies[1] = 1;
acceptedIndicies[2] = 2;
}
else if (acceptedIndicies.Contains(1) && acceptedIndicies.Contains(2) && acceptedIndicies.Contains(3)) // Right-Down-Left
{
// Order List in the sequence
acceptedIndicies[0] = 1;
acceptedIndicies[1] = 2;
acceptedIndicies[2] = 3;
}
else if (acceptedIndicies.Contains(2) && acceptedIndicies.Contains(3) && acceptedIndicies.Contains(0)) // Down-Left-Top
{
// Order List in the sequence
acceptedIndicies[0] = 2;
acceptedIndicies[1] = 3;
acceptedIndicies[2] = 0;
}
else if (acceptedIndicies.Contains(3) && acceptedIndicies.Contains(0) && acceptedIndicies.Contains(1)) // Left-Top-Right
{
// Order List in the sequence
acceptedIndicies[0] = 3;
acceptedIndicies[1] = 0;
acceptedIndicies[2] = 1;
}


List Count of 2:

0, 1

1, 2

2, 3

3, 0

if (acceptedIndicies.Contains(0) && acceptedIndicies.Contains(1))
{
// Order List in the sequence
acceptedIndicies[0] = 0;
acceptedIndicies[1] = 1;
}
else if (acceptedIndicies.Contains(1) && acceptedIndicies.Contains(2))
{
// Order List in the sequence
acceptedIndicies[0] = 1;
acceptedIndicies[1] = 2;
}
else if (acceptedIndicies.Contains(2) && acceptedIndicies.Contains(3))
{
// Order List in the sequence
acceptedIndicies[0] = 2;
acceptedIndicies[1] = 3;
}
else if (acceptedIndicies.Contains(3) && acceptedIndicies.Contains(0))
{
// Order List in the sequence
acceptedIndicies[0] = 3;
acceptedIndicies[1] = 0;
}

Answer

You can do the following:

  1. Build the valid modulus sequence. That's easy:

     var modulusSequence = Enumerable.Range(0, modulus);
    
  2. Now generate all valid modulus sequences for a given modulus. Thats easy too, just shift left or right a valid sequence we happen to know:

    private static IEnumerable<int> ShiftLeft(IEnumerable<int> sequence)
    {
        if (!sequence.Any())
            yield break;
    
        var first = sequence.Take(1).First();
        var tail = sequence.Skip(1);
    
        foreach (var i in tail)
        {
            yield return i;
        }
    
        yield return first;
    }
    
  3. And now you simply have to check if any given sequence contains all elements of a valid sequence and if it does, return the valid sequence.

    I do note that I'm not ordering your list, I'm returning a new one or null if the sequence is not valid.

    public static IEnumerable<int> GetOrderedSequence(IList<int> sequence, int modulus)
    {
        if (modulus < sequence.Count)
            throw new ArgumentOutOfRangeException(nameof(sequence), "Sequence can not contain more elements than specified modulus.");
    
        var modulusSequence = Enumerable.Range(0, modulus);
    
        for (var i = 0; i < modulus; i++)
        {
            var validSequence = modulusSequence.Take(sequence.Count);
    
            if (validSequence.All(item => sequence.Contains(item)))
                return validSequence;
    
            modulusSequence = ShiftLeft(modulusSequence);
        }
    
        return null;
    }
    

Is this faster / more efficient than your approach? Probably not. Is it prettier? I think so but its debatable. Is it more flexible? Oh yes!

If you are absolutely sure you are only going to need to check 2 and 3 long sequences with modulus 4 then you could keep your code. If not, implement a general purpose solution like the one I've shown you.