Shuffle an array based on some rules
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 =&gt; 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&lt;5; i++)
{
    images.SortBy( x =&gt; 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: