# An algorithm that spreads similar items across a list

I need an algorithm that distributes same items across a list, so maximizing the distance between occurrences.

E.g. I have a list of 15 items:

{a,b,c,c,c,d,e,f,f,f,g,h,h,i,j}

The algorithm should reorder these in such a way that all the duplicates are spread as uniformly as possible.

The mentioned list should result in something like this:

{c,f,a,h,b,c,d,e,c,f,g,c,h,i,j,f}

Preferably I'd like pseudo code, and even better would be TSQL (since that is the platform it needs to run on). It needs to process hundreds of these lists in one go.

I also tested a proposed method called 'Weighted shuffle' but this will still allow two of the same items in the list to appear next to each other even when this is not needed.

• My knowledge on these kind of algorithms is next to zero, so I've been trying to help myself with Google reading through hundreds of pages. But since I'm clueless to what I'm exactly searching for, how it is called or where I should look I've only run into different sorting methods and optimization problems. Nothing I can use or even able to translate to code. Nov 12, 2014 at 14:05
• Yes, this list of letters (in this case) is what should get reshuffled. Maybe I'm using a wrong term, but like I said above, I'm clueless to what it is I'm exactly looking for. I only know the begin and end situations I want to achieve. Nov 12, 2014 at 14:06
• did you try to search for "shuffle" / "weighted shuffle"?
– gnat
Nov 12, 2014 at 14:32
• Just typed out the weighted shuffle in SQL, the randomness throws it off. It can still come back with the same items next to each other even when it is possible to distribute them better (not next to each other) Nov 12, 2014 at 15:12
• @Robert "the randomness throws it off" No it does not. If it is truly random the same items can indeed be next to each other. No 'random' algorithm alone will get the job done, you need to control it, e.g. you could get each "random next character not matching the last one" but that does not guarantee the last two will not be equal - in which case you'll have to backtrack. Nov 12, 2014 at 15:36

First, make sure there is a solution according to your requirements (that means, there is not a single letter which occurs more that n/2 times, when n is the total number of elements).

Then I suggest you try the following

• afterwards, for each remaining pair of similar neighbours, pick one of the items, pick another randomly choosen item among those with different neighbours, and switch their places

• repeat the last step until all pairs are removed.

This approach will just make sure you get no neighboured pairs, but it does not maximize the possible distances between similar letters. If you want to achieve the latter (which is not clear from your question), I suggest you introduce a score function to your list, for example like this:

Score(list) := Sum(1/(abs(a-b)-0.999))
a,b

where the sum goes over all pairs (a,b) of positions of equal letters. The "-0.999" in the denominator makes sure the whole expression will become very big when there are 2 equal neighbours. Now, you can apply random swaps to your list and try to minimize the score function, for example by hill climbing or simulated annealing.

If you're only worried about spreading the similar rows apart, and not as bothered by making sure they are in regular intervals, you can use something like the following:

It determines a weight for each group of letters, then uses the ROW_NUMBER function to calculate a distribution of sorts. By tweaking the weighting and/or sorting in the final select, you may get the results you need.

CREATE TABLE #items (letter char(1))
INSERT INTO #items VALUES ('a')
INSERT INTO #items VALUES ('b')
INSERT INTO #items VALUES ('c')
INSERT INTO #items VALUES ('c')
INSERT INTO #items VALUES ('c')
INSERT INTO #items VALUES ('d')
INSERT INTO #items VALUES ('e')
INSERT INTO #items VALUES ('f')
INSERT INTO #items VALUES ('f')
INSERT INTO #items VALUES ('f')
INSERT INTO #items VALUES ('g')
INSERT INTO #items VALUES ('h')
INSERT INTO #items VALUES ('h')
INSERT INTO #items VALUES ('i')
INSERT INTO #items VALUES ('j')
ALTER TABLE #items ADD weight numeric(4,2)

DECLARE @itemcount numeric(4,2) = (SELECT COUNT(*) FROM #items)
UPDATE #items set weight = @itemcount / (SELECT COUNT(*) FROM #items i WHERE letter = #items.letter)

--Sort items by weight, using row_number to space out letter groups
;WITH cteNumbered AS (SELECT letter, weight, ROW_NUMBER() OVER (PARTITION BY letter ORDER BY letter) as rownum FROM #items)
SELECT letter from cteNumbered ORDER BY rownum * weight, weight desc, letter