How do you removing a cycle of integers (e.g. 1-2-3-1) from an array

Question

If you have an array of integers, such as 1 2 5 4 3 2 1 5 9 What is the best way in C, to remove cycles of integers from an array. i.e. above, 1-2-5-4-3-2-1 is a cycle and should be removed to be left with just 1 5 9.

How can I do this? Thanks!!

Answer 1

Build a graph and select edges based on running depth first search on it.

Mark vertices when you visit them, add edges as you traverse graph, don't add edges that have already been selected - they would connect previously visited components and therefore create a cycle.

From the array in your example we can't tell what is considered a cycle.

In your example both 2 -> 5 and 1 -> 5 as well as 1 -> 2 so in graph (?):

1 -> 2
|    |
|    V
+--> 5

So where is the information of which elements are connected?

Answer 2

A straight forward search in an array could look like this:

int arr[] = {1, 2, 5, 4, 3, 2, 1, 5, 9};
int len = 9;
int i, j;

for (i = 0; i < len; i++) {
   for (j = 0; j < i; j++) {
      if (arr[i] == arr[j]) {
         // remove elements between i and j
         memmove(&arr[j], &arr[i], (len-i)*sizeof(int));
         len -= i-j;
         i = j;
         break;
      }
   }
}

Answer 3

There is a simple way, with O(n^2) complexity: simply iterate over each array entry from the beginning, and search the array for the last identical value. If that is in the same position as your current position, move on. Otherwise, delete the sequence (except for the initial value) and move on. You should be able to implement this using two nested for loops plus a conditional memcpy.

There is a more complex way, with O(n log n) complexity. If your data set is large, this one will be preferable for performance, though it is more complex to implement and therefore more error-prone.

1) Sort the array - this is the O(n log n) part if you use a good sorting algorithm. Do so by reference - you want to keep the original. This moves all identical values together. Break sort-order ties by position in the original array, this will help in the next step.

2) Iterate once over the sorted array (O(n)), looking for runs of the same value. Because these runs are themselves sorted by position, you can trivially find each cycle involving that value by comparing adjacent pairs for equality. Erase (not delete) each cycle from the original array by replacing each value except the last with a sentinel (zero might work). Don't close the gaps yet, or the references will break.

NB: At this stage you need to ignore any endpoints that have already been erased from the array. Because they will resolve to sentinels, you simply have to be careful to not erase "runs" that involve the sentinel value at either end.

3) Throw away the sorted array, and use the sentinels to close the gaps in the original array. This should be O(n).

Actually implementing this in any given language is left as an exercise for the reader. :-)