Olympiad tasks in industrial programming. Part 1

Working as a backend developer in the best company in the world, I ran into (or wanted to face) tasks that are very similar to those in Olympiad programming. It is about them that will be discussed. This is the first part of the article, in which I will give one task with a detailed explanation. If you are also interested in algorithms and data structures, then please under the cat!

Task 1.

Given: a list of unique objects (for simplicity, we take the numbers), which have a pattern in the order.

Limitations:
')

• number of elements up to 10 ^ 5;
• It is expensive to create a new list, so you need to change the same list.

It is necessary to mix the elements of the list so that not one element of the list stands in the same place, and also that the pattern in the order of succession breaks, that is, simply cyclically moving the elements to the right or left is not enough.

Decision:

Let the number of elements in the list be n. Since we need to ensure that each element does not stand in the same place, we will for each element with index i, which varies from (n-1) to 1, generate a random number — index from 0 to i is not inclusive. Thus, by obtaining a random index j, which is not equal to the current index i, we swap the elements at the i and j positions.

For example:

Our list = [1,7,5,2,6].

Fill in the trace table for better visibility of the algorithm, where i is renamed as rightIndex, and j is leftIndex.

rightIndex	leftIndex	List
four	one	[1,6,5,2,7]
3	2	[1,6,2,5,7]
2	0	[2,6,1,5,7]
one	0	[6,2,1,5,7]

Let's write down the initial list and the list which has turned out as a result of execution of the algorithm.

[1,7,5,2,6]

[6,2,1,5,7]

As we see, all the elements have moved to different places, and there is not a single element that remained in its place. If you notice, rightIndex always changes from the last index of the list to 1. And leftIndex is generated randomly so that it is strictly less than the correspondingIn corresponding to it at each iteration of the cycle, rightIndex. Due to this property, the final result is achieved.

We write the above method in C #. We parameterize it so that it can be used for any objects (numbers, strings, custom data types).

//     ,    public static void Shiffle<T>(this IList<T> list) { var random = new Random(); int maxIndex = list.Count - 1; for (int i = 0; i < maxIndex; i++) { int rightIndex = maxIndex - i; int leftIndex = random.Next(0, rightIndex); list.Swap(leftIndex, rightIndex); } } 

 //          public static void Swap<T>(this IList<T> list, int index1, int index2) { T c = list[index1]; list[index1] = list[index2]; list[index2] = c; } 

I laid out this function in my repository. Link to GitHub here .

If you do not agree with the correct operation of the algorithm or do not fully understand, then write in the comments, I will answer you.

If you have a faster solution, or a simpler one (of course, explaining it and of course with such limitations), then please indicate in the comments, I will be grateful.