Need help with logic (C)

Question

I need to swap first n elements from two non repeating sequences(arrays), where n is a random integer.

Seq1: 1 4 5 6 9 8 2 3 7

Seq2: 3 9 1 2 8 7 4 5 6

If n = 4

Seq1: 3 9 1 2 | 9 8 2 3 7

Seq2: 1 4 5 6 | 8 7 4 5 6

Now i need to repair the sequence by replacing the repeated numbers after '|'.

How to do this?

This is my effort..

for(left1 = 0; left1<pivot; left1++)
  {
   for(right1 = pivot; right1 < no_jobs; right1++)
    {
     if(S1->sequence[left1] == S1->sequence[right1])
      {
        for(left2 = 0; left2<pivot; left2++)
        {
          for(right2 = pivot; right2<no_jobs; right2++)
          {
            if(S2->sequence[left2] == S2->sequence[right2])
            {
              swap_temp = S1->sequence[right1];
              S1->sequence[right1] = S2->sequence[right2];
              S2->sequence[right2] = swap_temp;
              break;
            }
          } 
        }
      }
    }
  }

Answer 1

Swapping the first n elements is straightforward using a single for loop.

for(int i = 0; i < n; i++){
   int tmp = array1[i];
   array1[i] = array2[i];
   array2[i] = tmp;
}

Now you need to find what has changed in the arrays. You can do this by comparing the parts you swapped.

int m1 = 0, m2 = 0;
int missing_array1[n];
int missing_array2[n];

for(int i = 0; i < n; i++){
    bool found = false;
    for(int j = 0; j < n; j++){
        if(array1[i] == array2[j]){
            found = true;
            break;
        } 
    }
    if(!found){
        missing_array2[m2++] = array1[i];
    }
}

for(int i = 0; i < n; i++){
    bool found = false;
    for(int j = 0; j < n; j++){
        if(array2[i] == array1[j]){
            found = true;
            break;
        } 
    }
    if(!found){
        missing_array1[m1++] = array2[i];
    }
}

missing_array2 now contains the numbers that are missing from array2. These are all the numbers that will be duplicated in array1. The same goes for missing_array1. Next you need to scan both arrays and replace the duplicates with the missing numbers.

while(m1 >= 0){
    int z = 0;
    while(missing_array1[m1] != array2[n + z]){
        z++;
    }
    array2[n + z] = missing_array2[m1--];
}

while(m2 >= 0){
    int z = 0;
    while(missing_array2[m2] != array1[n + z]){
        z++;
    }
    array1[n + z] = missing_array1[m2--];
}

In summary, you compare the parts you swapped to find the values that will be missing from each array. These value are also the values that will be duplicated in the opposite array. Then you scan each of the arrays and replace the duplicate values with one of the missing values (I assume you don't care which of the missing values, as long as all the values are unique.

Answer 2

If the swapped portions of the sequences contain the same values, then there would be no repeats - performing the swap would just shuffle the first n elements. So the values you need to repair are the values which occur in one of the swapped sequences

Firstly, I'd create a histogram of the n swapped elements, with those from sequence 1 counting as bit 0, and those from sequence 2 as bit 1. If any members of the histogram are non-zero, then they occur in one or the other sequence only.

If there are values requiring repair, then you can construct a look-up table of the values which require rewriting. This should map i to i unless i is one of the asymmetric values in the histogram, in which case it needs to map to the another asymmetric value.

Seq1: 1 4 5 6 9 8 2 3 7

Seq2: 3 9 1 2 8 7 4 5 6

If n = 4

Seq1: 3 9 1 2 | 9 8 2 3 7

Seq2: 1 4 5 6 | 8 7 4 5 6

histogram

value    1 2 3 4 5 6 7 8 9 
count    3 1 1 2 2 2 0 0 1

mapping for sequence 1 ( while histogram [S1[i]] & 1, replace[S1[i]] with S2[i] )

value    1 2 3 4 5 6 7 8 9 
replace  1 6 5 4 5 6 7 8 4

apply mapping to sequence 1 for i > n

Seq1:    3 9 1 2 | 9 8 2 3 7
replace  - - - - | 4 8 6 5 7
result   3 9 1 2 | 4 8 6 5 7

mapping for sequence 2 ( while histogram [S2[i]] & 2, replace[S2[i]] with S1[i] )

value    1  2  3  4  5  6  7  8  9 
replace  1  2  3  9  3  2  7  8  9 

apply mapping to sequence 1 for i > n

Seq2:    1 4 5 6 | 8 7 4 5 6
replace  - - - - | 8 7 9 3 2
result   1 4 5 6 | 8 7 9 3 2

Alternatively, replace with the next value with the other bit set in the histogram (the iterated replace will also need to check for replacing a value with itself); I'm assuming it doesn't really matter what value is used as the replacement as long as the values in the result are unique.