对数组进行混洗,使得没有两个相同的元素相邻

Question

我有一个包含字符串的数组.其中几个字符串可以是相同的,也没关系.它们可以按任何顺序开始,但很可能是按字母顺序排列.我有以下shuffle功能,将洗牌所有元素.但是,我想添加一个条件,即数组中没有两个相同的字符串可以相邻.

例如,这很好:ook eek ook monkey ook但这不是:ook ook eek ook monkey因为两个ook是相邻的.假设已经检查了输入,使得任何重复小于元素总数的一半,因此存在一组非相邻解.例如,ook ook ook eek将被拒绝.字符串可以包含空格和UTF-8字符,但不包含新行 - 字符串实际上是图像的文件名.

如何修改shuffle功能以实现此目标？

或者有更好的方法吗？

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

给定拒绝前提条件，可以将单词列表分成几个 \xc2\xabe 等价类 \xc2\xbb (ECs) \xe2\x80\x94 特殊单词组，其中每个单词根据任何标准都是相同的。拒绝意味着不超过一个 EC 部分位于列表的一半中，部分位于列表的另一半中。

\n\n

我们将这个 EC 的一部分放在一边，以便 (1) 剩余部分最多包含在列表的剩余一半中，并且 (2) 这两半的大小严格相等。然后我们将两半分开，每一半都分开。之后，我们将它们合并，前半部分占据奇数元素，而偶数占据后半部分。然后我们随机插入之前放置的剩余元素。这很简单，因为它们都属于一个 EC，因此很容易标记它们可以在哪里和不能在哪里。

\n\n

通过构造，不能有两个相邻元素属于一个 EC。

\n\n

[编辑：] 最后，实现上述内容。

\n\n

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

\n