3

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. – Robert van Dijk Nov 12 '14 at 14:05
  • 1
    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. – Robert van Dijk Nov 12 '14 at 14:06
  • did you try to search for "shuffle" / "weighted shuffle"? – gnat Nov 12 '14 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) – Robert van Dijk Nov 12 '14 at 15:12
  • 2
    @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. – Jan Doggen Nov 12 '14 at 15:36
2

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

  • start with a random shuffle or weighted shuffle

  • 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.

1

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) 

--Add weight for each letter
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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.