How to shuffle a character array with no two duplicates next to each other?

Question

I was asked this question in an interview:

How to shuffle a character array with no two duplicates next to each other?

The algorithm I came up with was :

1. have a HashMap of Character, count of occurrence of Character pairs. With this find the count of duplicate vs unique elements.
2. If duplicate > unique, cannot form a shuffled array with no 2 duplicate elements next to each other (?)
3. if unique >= duplicate, have 2 stacks - 1 containing unique characters and one containing duplicate characters. Construct the resulting array in such a way that pop an element from unique stack first and pop an element from duplicate stack next. Repeat

For example:

[a,b,b,c] shuffled array with above algorithm - [a,b,c,b];

[b,b,b,c] unique < duplicate return error

But I am pretty sure I am overcomplicating the logic. Is there an easier and fool proof way to do this?

Answer 1

[ there is a test cases failing as was pointed in the comments]
So take care of the same if referring my answer I see, but it doesn't seem to work if you have 'a'->4, 'b'->2, and 'c'->1. Because the first step is "abc", leaving 'a'->3 'b'->1. But there is an answer: "ababaca". – user3386109

Case 1 : Build the basic algorithm

1. use a hashmap (key being the character and its occurance being the value) to count the occurances. This will give us buckets like if we have "cbaaba" will give 3 buckets with 'c' with value 1, 'a' with value 3 and 'b' with value 2.

2. Sort the buckets based on the occurances with element with most occurancr first. so now we have

'a' -> 3 , 'b' -> 2 , 'c' -> 1

3. Get the element from max occurance bucket, decrease its count by 1 in map and put it in result array. Follow this for subsequent occuance buckets based on the sorted occurance buckets.

result array will start with taking one each from 3 buckets in sorted fashion.

"abc" and now we have our buckets as 'a'->2 , 'b'-> 1 and 'c'-> 0

next we again try to get elemet each from sorted buckets (ignoring the buckets with 0 elements)

"abcab" now our buckets state become as : 'a'-> 1 , 'b'- > 0 and 'c'-> 0

next as above we proceed to have our result as

=> "abcaba".

Case 2 : if string is like "aaaabbbcccdd"

We will have buckets as

'a'--> 4
'b'--> 3
'c'--> 3
'd'--> 2

Here we have bucket of b and c having same size. When ever such situation occurs we have to perform an operation of JoinBuckets, It will join 'b' and 'c' in single bucket and 'bc' will be considered as a single element.

Now our buckets will be

'a'--> 4
'bc'--> 3
'd'--> 2

Now proceeding ahead in same manner as done in case 1, we try to build the result

=>result = "abcd"

'a'--> 3
'bc'--> 2
'd'--> 1

=>result = "abcdabcd"

'a'--> 2
'bc'--> 1
'd'--> 0

=>result = "abcdabcdabc"

'a'--> 1
'bc'--> 0
'd'--> 0

=>Final Result = "abcdabcdabca"

Answer 2

I would start with a very simple algorithm:

public static void shuffleWithoutRepetition(char[] chars, Random rnd) {
  if (tooManySameCharacters(chars))
    throw new IllegalArgumentException("Too many same characters");

  do {
    shuffle(chars, rnd); // See java.util.Collections.shuffle
  } while (containsRepetition(chars));
}

That way, you have some working code, and when it turns out to be too slow, you can optimize it later.

• This algorithm is very slow for shuffling aaaaaaaaaaaaaaabbbbbbbbbbbbbbb, which is bad.
• It generates each possible output with the same probability, which is good.

Answer 3

this is essentially a sorting question. It reminds me of 'peak finding' but in reverse, you want to in a sense 'create peaks' of unique items.

Also the logic of (2) is a bit off. If i have N repeated letters, I can still have no similar neighbors with N-2 of another letter:

'aaabb' -sort-> 'ababa'

this also demonstrates the issue of looking for 'uniques,' since you could very well have only letters that are duplicated somewhere in the array.

pseudo:

foreach letter in string{
  if next != self then happy, move to next

  if next == self, 
     loop until spot != self and swap

There may be a better way of divide and conquer to get through it in better time, but without actually testing it I'm not sure.

Answer 4

SCALA Code. Copy and paste this program and run.

def rearrange(xs : List[Char]) : List[Char] ={
xs match {
    case Nil => Nil
    case x :: xs1 => xs1 match {
    case Nil => x :: Nil
    case y :: ys1 =>
         if (x == y)  { 
              (x :: rearrange(ys1)) :+ y 
         }
         else
             x :: y :: rearrange(ys1)
         }
     }
}                                               
rearrange: (xs: List[Char])List[Char]

rearrange("hello".toList)