1

Take for example this input array:

[2,7,1,4,9]

For this input, I need to produce an array of total 23 elements which contains two elements of 2, seven elements of 7, one element of 1, four elements of 4 and nine elements of 9. Example of output array:

[2,2,7,7,7,7,7,7,7,1,4,4,4,4,9,...]

However, this array needs to be ordered in the way that minimizes the number of same elements appearing next to each other. The example of such array would be something like this:

[7,2,9,4,9,1,7,...]

The primary goal is to minimize the number of the same adjacent elements.

Secondary goal is to distribute elements unbiased across resulting array if possible.

Any pseudo code or C#, java, ... would be helpful.

Dusan
  • 585
  • 6
  • 19
  • 3
    You apparently care a lot about the shuffle *not* being random (or at least, not randomly chosen from *all* permutations but only from those fulfilling a specific criteria). Is that an actual business requirement, or are you just scared of random numbers? ;-) –  Mar 05 '14 at 17:15
  • 1
    I am reading about that algorithm, but it seems it is just a plain random shuffler, does not minimize the same adjacent elements. – Dusan Mar 05 '14 at 17:15
  • @delnan yes it is a business requirement. Take for example a DJ which needs to play song A 10 times, song B 5 times and song C 7 times, ... but he needs an algorithm to make order of songs in such way that no same song is played twice in a row (if possible). – Dusan Mar 05 '14 at 17:18
  • 4
    @Dusan you may be interested in [I'd like to write an “ultimate shuffle” algorithm to sort my mp3 collection](http://programmers.stackexchange.com/questions/194480/id-like-to-write-an-ultimate-shuffle-algorithm-to-sort-my-mp3-collection) which specifically addresses the DJ problem. –  Mar 05 '14 at 17:24
  • 2
    @Dusan - with 57 views on your question, you have no idea who has up voted or down voted. Voting on SE is intentionally anonymous by design. I doubt gnat wasted a down vote on your question, but your response merely encourages others to downvote and then _not_ leave a comment explaining why. –  Mar 05 '14 at 19:26

2 Answers2

4

This can be seen as a traveling salesman problem:

  • each element is a node of your graph, labled with it's number
  • there are edges between each pair of nodes
  • the "distance" of getting from one node to another is 0 if the lables have different numbers, and 1 if the numbers are equal

Now you are looking for a route through this graph minimizing the total distance. Google for 

           traveling salesman <your_favorite_programming_language>

and you will find tons of example implementations with heuristic or brute-force approaches.

Doc Brown
  • 199,015
  • 33
  • 367
  • 565
  • Thanks for the answer. Can you suggest some decent heuristic for this specific 0-1 graph which is expected to work less than a second for the max 100 elements in the resulting array? – Dusan Mar 05 '14 at 19:19
  • @Dusan: no, but I suggest you implement one of the simpler suggestions from the Wikipedia article about TSP and test if it is good enough for your case. – Doc Brown Mar 05 '14 at 21:28
1

The resulting array only really needs to separate the largest elements, any smaller element will be trivially separated by the larger elements. So if we have 9, 7, 4, and 2:

999999999
9797979797979799
97 97 97 97 97 97 97 94 9

And now it's easy, because there are always enough spaces to insert smaller numbers (starting at the left)

974 974 974 972 972 97 97 94 9
U2EF1
  • 718
  • 4
  • 5