bash – 随机播放一个数组,使得没有两个相同的元素相邻

我们将这个EC的一部分放在一边,以便(1)剩下的部分包含在列表剩余的一半中,并且(2)两半的大小严格相等.然后我们将两个人分开洗牌.在那之后,我们合并它们,前半部分占据奇数元素,而evens则是下半部分.然后我们随机插入先前放置的剩余元素.它非常简单,因为它们都属于一个EC,因此很容易标记它们可以存在的位置和不能存在的位置.

通过构造,可以没有属于一个EC的两个相邻元件.

[编辑：]最后,执行上面的内容.

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"