13

We are given a string of the form: RBBR, where R - red and B - blue.

We need to find the minimum number of swaps required in order to club the colors together. In the above case that answer would be 1 to get RRBB or BBRR.

I feel like an algorithm to sort a partially sorted array would be useful here since a simple sort would give us the number of swaps, but we want the minimum number of swaps.

Any ideas?

This is allegedly a Microsoft interview question according to this.

efficiencyIsBliss
  • 3,043
  • 7
  • 38
  • 44
  • 1
    Smells like dynamic programming and A*-style pathfinding would be useful here. – Phrogz Jan 11 '11 at 04:37
  • I'm interested in the more general problem of the minimum number of swaps needed to sort balls of many colors. The algorithm I gave in my answer is linear on the number of balls, but factorial on the number of colors (as the number of possible target strings is a permutation of the colors involved). Is there a better way? – Null Set Jan 11 '11 at 13:06
  • @Null Set: @bronzerbeard wrote an answer citing the http://en.wikipedia.org/wiki/Dutch_national_flag_problem which is about sorting a 3-colors string. Maybe that could be a starting point. – Matthieu M. Jan 11 '11 at 13:37

6 Answers6

16

Take one pass over the string and count the number of reds (#R) and the number of blues (#B). Then take a second pass counting the number of reds in the first #R balls (#r) and the number of blue balls in the first #B balls (#b). The lesser of (#R - #r) and (#B - #b) will be the minimum number of swaps needed.

Null Set
  • 5,374
  • 24
  • 37
  • I am afraid I am out of my depth here. I just can't say if you are write or wrong, would you care to explain how you get those formulas ? – Matthieu M. Jan 11 '11 at 08:45
  • @Matthieu M.: As I understand, the target configuration must be one of the following two: `RR...RBB...B` or `BB...BRR...R`. The above just calculates which one of the two is cheaper to achieve via swaps. – Rafał Dowgird Jan 11 '11 at 11:25
  • @Matthieu Once you know how many reds and blues there are, you know exactly what the two possible ending strings look like, with either all the reds on the right or all the blues on the right. You only have to figure out which of those two strings is "closer" to the starting string. y – Null Set Jan 11 '11 at 12:54
  • 1
    @Matthieu: Once you know the number of reds and blues there are, you know exactly what the two possible ending strings look like, either all the reds on the right, or all the blues on the right. You just have to calculate which of these two strings is "closer" to the starting string. You can do this by counting the number of "holes" in the space you know will be full of reds or full of blues. Each spot not currently occupied by the target color requires a swap with a ball from the other side of the string. You then just have to pick the configuration that requires less swaps. – Null Set Jan 11 '11 at 13:00
  • Thanks, I had not understand that `#R - #r` was the number of "holes" in the `#R` first balls. Effectively, once you get it the rest seems pretty trivial. Nice solution. – Matthieu M. Jan 11 '11 at 13:35
3

We are given the string S that we have to convert to the final string F = R^a B^b or B^b R^a. The number of differences between S and F should be even because for every misplaced R there will be a complementary misplaced B. So why not find the minimum number of differences between S and both possible F's and divide that by 2?

For example, you're given S = RBRRBRBR which should convert to RRRRRBBB
or BBBRRRRR

Comparing the differences between S and F for each character for each possibility, there are 4 differences for each possible final string so regardless the minimum is 2 swaps.

aaa
  • 31
  • 3
0

Let's look at your example. You know that the end state will be RRBB or BBRR. In other words, the end state is always nRmB or mBnR, where n is the number of R's and m is the number o B's in your string. Since the end state is defined, maybe some sort of path-finding algorithm would be a good aproach for this? How about considering each swap as a state-change and thinking of a heuristic function to aproximate the number of left over swaps needed. I'm just throwing an idea in the air, but I hope this helps.

vitorbal
  • 2,871
  • 24
  • 24
0

Start with two indices simultaneously from the right and left end of the string. Advance the left index until you find an R. Advance the right index backwards until you find a B. Swap them. Repeat until the left index meets the right index, and count the swaps. Then, do the same, but look for B on the left and R on the right. The minimum is the lower of both swap counts.

Svante
  • 50,694
  • 11
  • 78
  • 122
0

I think the number of swaps can be derived from the number of inversions required to sort the vector. This is the example of doing the same with permutation vector.

Community
  • 1
  • 1
Ruslan Kabalin
  • 6,580
  • 2
  • 28
  • 20
0

This isn't a technical answer, but I looked at this more intuitively.

RRBBBBR is can be reduced to RBR, since a group of R's can be moved as a single block. This means that the array is really just a N sets of RB.

The only thing that matters is the number of N sets of RB blocks (including incomplete blocks for the last one).

  • RBR -> 1 swap to get to RRB (2 sets of RB block, RB and R)
  • RBRB-> 1 swap to get to RRBB (2 full sets of RB blocks)
  • RBRBRB-> 2 swaps to get to RRRBBB (3 full sets of RB blocks)
  • RBRBRBRB -> 4 sets of RB = 3 swaps

So to generalize this, the number of swaps needed = N sets of RB block (including incomplete blocks) and subtract 1.

takrl
  • 6,356
  • 3
  • 60
  • 69
steve8918
  • 1,820
  • 6
  • 27
  • 38