rearrange array such that no two adjacent elements are the same

Question

Suppose you have a list of characters. Arrange the characters in the array in such a way that no two adjacent elements are the same.

Constraints No of characters~ 10^6

Sample Input - [‘c’, ‘d’, ‘d’, ‘a’, ‘a’, ‘x’ , ‘d’]

Sample Output - [‘a’, ‘d’, ‘x’, ‘c’, ‘d’, ‘a’, ‘d’]

My Try:

a = ['a', 'a', 'b', 'c', 'c', 'b', 'd']
import random


for c, d in zip(a, a[1:]):
    if c != d:
        continue
    else:
        random.shuffle(a):

print(a)

function to check if new array has distinct adjacent elements:

def distinctAdjacentElement(a, n):
    m = dict()

    for i in range(n):
        if a[i] in m:
            m[a[i]] += 1
        else:
            m[a[i]] = 1
    mx = 0

    for i in range(n):
        if mx < m[a[i]]:
            mx = m[a[i]]

    if mx > (n+1) // 2:
        return True
    else:
        return False

There are multiple such arrays possible. Why would you expect this one? — Austin, Jan 18 '20 at 05:25
Input: `['a', 'a', 'a']`. Expected output: ??? Also, have you attempted solving this? If so, please share your code to avoid this being closed as "too broad". [This might help](https://codegolf.stackexchange.com/questions/6487/code-golf-mix-the-nuts-so-that-none-of-the-same-kind-are-touching) — ggorlen, Jan 18 '20 at 05:29
A solution that could be applied [Rearrange numbers in an array such that no two adjacent numbers are same](https://www.geeksforgeeks.org/rearrange-numbers-in-an-array-such-that-no-two-adjacent-numbers-are-same/) — DarrylG, Jan 18 '20 at 05:30
if thats the case then printing not posssible wpuld be fine @ggorlen — Mohit Harshan, Jan 18 '20 at 05:31
The question should be, 'is it possible to arrange the characters in a given sequence such that no two adjacent elements are identical?'. To make it more difficult, "How many such unique arrangements exist for the given sequence?" — neutrino_logic, Jan 18 '20 at 05:32
Usually, no one demands code here. We help you correct your code. — Austin, Jan 18 '20 at 05:33
You can follow algorithm described in https://stackoverflow.com/questions/43352265/rearrange-items-in-a-list-such-that-no-two-adjacent-are-same. The problem with your code is that you are doing just one pass through list and that random shuffle does not confirm that adjacents are different. — Austin, Jan 18 '20 at 05:46
i have to shuffle until the array has distinct adjascent elements, i have updated question @Austin — Mohit Harshan, Jan 18 '20 at 05:56

DarrylG · Accepted Answer · 2020-01-18T15:38:49.747

Based upon converting code from Java to Python from Rearrange characters in a string such that no two adjacent are same which includes a description of technique.

from collections import Counter
from heapq import heappush, heappop

# Function to rearrange character of a string 
# so that no char repeat twice 
def rearrange(s):
  # Use builtin function to count the freque3ncy of items
  count = Counter(s)

  # Insert all characters with their frequencies 
  # into a priority_queue (using a heap)
  pq = []
  for k, v in count.items():
    heappush(pq, (-v, k))  # Use negative to make max heap
                           # since heaps are normally a min heap

  # 'result' that will store resultant value
  result = [0]*len(s)

  # work as the previous visited element 
  # initial previous element be. ( '#' and 
  # it's frequency '-1' ) 
  prev = (1, '#')

  # traverse queue 
  ind = 0
  while pq:
    if ind >= len(s):
      break
    # pop top element from queue and add it 
    # to string. 
    k = heappop(pq)
    result[ind] = k[1]
    # If frequency of previous character is >= 0 that means it is useless, we 
    # need not to push it  (note this is oposite from original algorithm since
    # we are using a max heap by inverting the sign of the frequency counts
    if prev[0] < 0:
      heappush(pq, prev)

    # make current character as the previous 'char' 
    # decrease frequency by 'one' 
    prev = (k[0]+1, k[1])

    ind += 1

  # If length of the resultant string and original 
  # tring is not same then string is not valid 
  if ind != len(s):
    return None
  elif isinstance(s, list):
    return result
  else:
    return ''.join(result)

Test Cases

print(rearrange(['c', 'd', 'a', 'a', 'x', 'd']))
 >>> ['a', 'd', 'a', 'c', 'd', 'x']

print(rearrange(['b', 'b', 'a', 'a']))
 >>> ['a', 'b', 'a', 'b']

print(rearrange(['b', 'b', 'a', 'a', 'a', 'a']))
 >>> None

# Also handles strings
print(rearrange('bbaaa'))
>>> ababa

there are multiple outputs possibe right.. how to find all of them? — thomachan, Apr 29 '22 at 11:26
@thomachan -- There seems to be multiple methods for the original question such as [Shuffling a string so that no two adjacent letters are the same](https://stackoverflow.com/questions/39171840/shuffling-a-string-so-that-no-two-adjacent-letters-are-the-same). Perhaps the answer by Sergey Kalinichenko could be modified to find all of them. — DarrylG, Apr 29 '22 at 12:00

rearrange array such that no two adjacent elements are the same

1 Answers1