Przetasuj tablicę tak, aby nie było dwóch sąsiednich elementów.

Question

Mam tablicę zawierającą ciągi. Kilka z tych ciągów może być takich samych i to jest w porządku. Mogą być w dowolnej kolejności, ale najprawdopodobniej są w porządku alfabetycznym. Mam następującą funkcję shuffle, która przetasuje wszystkie elementy. Jednak chcę dodać warunek, że żadne dwa z tego samego ciągu nie mogą przylegać do tablicy.

Na przykład jest to w porządku: ook eek ook monkey ook, ale nie jest to: ook ook eek ook monkey, ponieważ sąsiadujące są dwa ook. Zakłada się, że dane wejściowe zostały sprawdzone w taki sposób, że wszystkie duplikaty są mniejsze niż połowa całkowitej liczby elementów, więc istnieje zestaw nie sąsiednich rozwiązań. Na przykład ook ook ook eek zostanie odrzucony. Łańcuchy mogą zawierać spacje i znaki UTF-8, ale nie nowe linie - ciągi są w rzeczywistości plikami nazw obrazów.

Jak mogę zmienić funkcję shuffle, aby osiągnąć ten cel?

A może jest lepszy sposób to zrobić?

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

względu na odrzucenie pre-condition, możliwe jest, aby podzielić listę słów do kilku klas równoważności «» (ECS) - specjalny grup wyrazowych w każdym z których słowa są takie same, niezależnie od kryterium. Odrzucenie oznacza, że ​​nie ma więcej niż jedno WE, które znajduje się częściowo w jednej połowie listy, a częściowo w drugiej.

Odłóżmy część tego EC na bok, tak aby (1) pozostałą część zawierała nie więcej niż jedna z pozostałych połówek listy, a (2) połówki są ściśle równej wielkości. Następnie potasujemy połówki, każdą oddzielnie. Potem łączymy je, pierwsza połowa zajmuje dziwne elementy, podczas gdy wyrównania są na drugą połowę. Następnie losowo wstawiamy pozostałe elementy wcześniej odłożone na bok. Jest to dość proste, ponieważ wszystkie z nich należą do jednego WE i dlatego łatwo jest oznaczyć miejsca, w których mogą być i gdzie nie mogą.

Konstrukcja nie może zawierać dwóch sąsiednich elementów należących do jednego EC.

[EDIT:] Wreszcie, wykonanie tego, co powyżej.

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"