Reinstall elements into an array without similar elements next to each other

Question

Suppose I have a set of blocks. 12 - red, 8 - blue, 5 - yellow, 1 - green. I need to create an algorithm that outputs these objects in one array without red blocks next to each other, without blue blocks next to each other, etc. The result should look something like this:

red, blue, red, blue, red, blue, yellow, blue, green, red, yellow, etc.

In my programming experience, so far I have come to places where I had to write an algorithm to do this more than once. The last time I did this was about 2 years ago, working to run. I implemented such an algorithm in python, but the source code is not available. I remember that it took me at least 100 lines.

Does this algorithm have a name? I do not want to repeat it again.

Answer 1

I do not know the name of this problem. Below is the algorithm that I decided to solve.

You need to track the number of remaining blocks.

repeat: output 1 block of largest color set. output 1 block from the second largest color set. 

conclusion:

rbrbrbrbrrrrrrrrrrrrrrr rrrrrgg

note: before running this algorithm, you need to check whether the largest color set exceeds 1 + the sum of other colors. If so, there is no solution.

Note: selection from the second largest set is not required. The second choice in the loop can come from any of the largest sets of colors.

Answer 2

Above my head, create a queue containing all the blocks that you want to insert in decreasing amounts (i.e. using the example above, the queue will have 12 reds, then 8 blues, then 5 yellow, and then 1 green). Insert an element from the queue into each even index of the array, and then each odd index (i.e., insert the red block with index 0,2,4,6,8,10,12,14,16,18,20,22, then insert the blues in 24,1,3,5,7,9,9,11,13, then insert the yellow spots on 15,17, 19,21 and insert the green color in 23)

Please note that for some combinations of blocks this task is impossible - before starting the algorithm, you should check that the set of blocks with the largest number does not have more blocks than the sum of all blocks divided by 2

Answer 3

• First you need to check if such an array exists.

  eg. if you have 4 red and only 1 blue, then it does not exist

  So, if the number of the largest collection is less than the sum of all other collections minus 1, then there is no feasible solution

• Then you just put all the elements of your largest collection, say red, like a list.

  Between each element of the list is a spot in which you can insert other elements.

   eg _ red _ red _ red _ red _ red _ red ... 

• Now you can insert a collection of other items in the collection into these places. The order of the collections does not matter.

   eg blue red blue red blue red blue red yellow red yellow red _ red _ red .. 

  You need to use these spots always from left to right (or always from right to left).

  Whenever you run out of spots, you start again from the left (or right) to insert elements into new places.

   eg green blue _ red _ blue _ red _ blue _ red _ blue _ red _ yellow _ red ...