Shuffle the array so that there are no two adjacent elements

Question

I have an array containing strings. Some of these lines may be the same, and this is normal. They can be in any order, but most likely they are in alphabetical order. I have the following shuffle function that will shuffle all the elements. However, I want to add the condition that two rows of the same row can be adjacent in an array.

For example, this is normal: ook eek ook monkey ook , but it is not: ook ook eek ook monkey , as the two ook are adjacent. It is assumed that the input has been checked so that any duplicates are less than half the total number of elements, so there are many non-contiguous solutions. For example, ook ook ook eek will be rejected. Lines can contain spaces and UTF-8 characters, but not new lines — lines are actually the name of the image file.

How to change the shuffle function to achieve this?

Or is there a better way to do this?

 shuffle() { # This function shuffles the elements of an array in-place using the # Knuth-Fisher-Yates shuffle algorithm. local i tmp size max rand # $RANDOM % (i+1) is biased because of the limited range of $RANDOM # Compensate by using a range which is a multiple of the array size. size=${#array[*]} max=$(( 32768 / size * size )) for ((i=size-1; i>0; i--)); do while (( (rand=$RANDOM) >= max )); do :; done rand=$(( rand % (i+1) )) tmp=${array[i]} array[i]=${array[rand]} array[rand]=$tmp done } 

Answer 1

Given the prerequisite for rejection, you can divide the list of words into several "equivalence classes" (EC) - special groups of words, in each of which the words will be the same by any criterion. Deviation implies that no more than one EC is partly in the half of the list and partly in the other.

We will postpone part of this EU, so (1) the remaining part is contained in no more than one of the remaining half of the list, and (2) the halves are strictly equal in size. Then we mix the halves, each individually. After that, we combine them, the first half takes odd elements, and the Evenks - for the second half. Then we randomly insert the remaining elements previously set aside. This is quite simple, since they all belong to the same EC, and therefore it is easy to mark the places where they can be and where they cannot.

By construction, there cannot be two adjacent elements belonging to the same EC.

[EDIT:] Finally, an implementation of what is above.

 shuffle() { local sort="$(sort <<<"$1" | sed "s/^/+/g")" local size="$(grep -c ^ <<<"$sort")" local take cntr head tail if [ "$sort" == "${sort%%$'\n'*}" ]; then # single line: nothing to shuffle echo "${sort#+}" return fi if [ $[size & 1] == 1 ]; then # enforcing equal halves, beginning to extract the middle take="$(head -$[size / 2 + 1] <<<"$sort" | tail -1)" fi cntr="$take" size=$[size / 2] head="$(head -$size <<<"$sort")" tail="$(tail -$size <<<"$sort")" while [ "$(head -1 <<<"$tail")" == "$(tail -1 <<<"$head")" ]; do # continue extracting the middle, if still left if [ -n "$cntr" -a "$cntr" != "$(tail -1 <<<"$head")" ]; then break else cntr="$(tail -1 <<<"$head")" fi ((--size)) head="$(head -$size <<<"$head")" tail="$(tail -$size <<<"$tail")" take="${take:+$take$'\n'}$cntr"$'\n'"$cntr" done sort=() for cntr in $(seq $size); do # transforming two line sets into a single interlaced array sort[$[cntr * 4 - 3]]="$(head -$cntr <<<"$head" | tail -1)" sort[$[cntr * 4 - 1]]="$(head -$cntr <<<"$tail" | tail -1)" done for cntr in $(seq $[size - 1]); do # shuffling each of the interlaced halves by Fisher-Yates head="${sort[$[cntr * 4 - 3]]}" tail=$[RANDOM % (size - cntr + 1) + cntr] sort[$[cntr * 4 - 3]]="${sort[$[tail * 4 - 3]]}" sort[$[tail * 4 - 3]]="$head" head="${sort[$[cntr * 4 - 1]]}" tail=$[RANDOM % (size - cntr + 1) + cntr] sort[$[cntr * 4 - 1]]="${sort[$[tail * 4 - 1]]}" sort[$[tail * 4 - 1]]="$head" done if [ -n "$take" ]; then # got a remainder; inserting tail=($(seq 0 $[size * 2])) for cntr in $(seq $[size * 2]); do # discarding potential places with remainder in proximity if [ "${sort[$[cntr * 2 - 1]]}" \ == "${take%%$'\n'*}" ]; then tail[$[cntr - 1]]="" tail[$[cntr]]="" fi done tail=(${tail[@]}) for cntr in $(seq 0 $[${#tail[@]} - 2]); do # shuffling the remaining places, also by Fisher-Yates head="${tail[$cntr]}" size=$[RANDOM % (${#tail[@]} - cntr) + cntr] tail[$cntr]="${tail[$size]}" tail[$size]="$head" done size="$(grep -c ^ <<<"$take")" while ((size--)); do # finally inserting remainders sort[$[${tail[$size]} * 2]]="${take%%$'\n'*}" done fi head=0 size="${#sort[@]}" while ((size)); do # printing the overall result if [ -n "${sort[$head]}" ]; then echo "${sort[$head]#+}" ((size--)) fi ((head++)) done } # a very simple test from the original post shuffle \ "ook ook eek ook monkey"