Shuffle an array based on some rules

Question

I have a set of images. The length is variable. It could be anything up to about 30 images. Each image can have up to 10 tags. Images may share some, all or none of their tags. I need to select a random 5 from this set of images. This selection should follow the following rules in order of high priority to low:

1. Two images with the exact same tag(s) MUST NOT appear next to each other unless no other option is available.
2. Which two images appear next to each other should be decided by a weight system that favours images that share less tags or none at all. The more different tags two images have, the more likely they should be to appear side by side and vice versa.
3. Rule 2 also applies to the entire set of 5, but to a lesser degree. It means we prefer the selected 5 to share as few tags with one another as possible, but this should not take priority over rule 1 and 2.
4. (Optional) When selected images share tags, the more tags they share, the further apart they should be from each other.
5. (Optional) As a bonus, it would be nice not to sacrifice randomness because of rule 3 and 4, but this is more of a nice-to-have and is not necessary.

I'm looking for an algorithm that can help me solve the above problem. This is part of a real-world application UI and as a result, it'd be best if it doesn't take more than a second to calculate the set of 5. Anything longer than a second is bad. Even a second is too long.

If anyone has a solution that takes up to a minute or so, I might be able to do some pre-processing on the data so I am still open to it.

Answer 1

I would like you to note that the selection cannot be fully random.. Assume there are 10 total images.

• 5 have the same tags
• 5 have a single but unique tag

Then the algorithm will Always choose the same 5 images (And will Always skip the other 5 images).

Luckily there's an algorithm that can help you easily. Note that this algorithm skips points 4/5 (which you claim are optional).

Foreach image => sort its tags alphabetically

Find the longest tag

Postfix the same letter to all the tags in order to make them the same lenght

In example if you have the tags cherry,optimization,google those tags are transformed into

cherryXXXXXX
optimization
googleXXXXXX

Foreach image, make a string that is made by concatenation of all its tags. Then sort those strings alphabetically.

In Example:

• Image1 - tags: B, EE, A
• Image2 - tags: A, C
• Image2 - tags: Z

The final strings would be

AXBXEE
AXCX
ZX

Put your strings in a doubly linked, linkedlist, select a random element, then skip "some elements" (in example if you have 300 strings, you can select the first random and then skip 40-60 strings ) and take another element.

This algorithm is not complex, and not cheap, but is a good start point, note that your algorithm have to be a euristic-based (or greedy) algorithm because I fear your problem has a big computational complexity (still checking that, I'll update later this answer).

An alternative algorithm complexity (n number of images)

Assume the number of tags is limite to 10.

set all scores to 0
foreach img in images
    foreach img2 in images
       img.score -= TagsInCommon(img,img2)

for (int i = 0; i<5; i++)
{
    images.SortBy( x => x.score);
    img = images.RemoveFirst(); // pick image with highest score
    foreach img in images // (we have removed the first image here)
       foreach img2 in images
           img.score -= TagsInCommon(img,img2) //adapt score slightly
}

The above algorithm has a complexity of roughly

O(n^2 + nlogn + n)

where n is number of images (I did not check complexity ineherent in string lenghts, number of tags etc.).

This algorithm basically is another algorithm with a greedy approach, image with unique tags will be the first selected images, while images that are heavily tagged will be putted to the end of the list (and possibly are never sorted out). Plus we are adapting the score during execution to remove tags that we have already drawed.

A better alternative would be (instead of removing Always the first element) to select a random element with a distribution that favours the elements with higher score (but at same time do not forbid to draw elements with low score).

This algorithm will probably will take less of a second even with something like 100 thousand images.

A distribution like the following would suffice: