एक सरणी को घुमाएं ताकि कोई भी दो तत्व आसन्न

Question

मेरे पास एक सरणी है जिसमें तार शामिल हैं। उनमें से कई तार समान हो सकते हैं और यह ठीक है। वे शुरू करने के लिए किसी भी क्रम में हो सकते हैं, लेकिन अधिकतर वे वर्णानुक्रम में हैं। मेरे पास निम्नलिखित shuffle फ़ंक्शन है जो सभी तत्वों को घुमाएगा। हालांकि, मैं एक शर्त जोड़ना चाहता हूं कि सरणी में कोई भी दो स्ट्रिंग आसन्न न हो।

उदाहरण के लिए, यह ठीक है: ook eek ook monkey ook लेकिन यह नहीं है: ook ook eek ook monkey दो ook आसन्न हैं। यह माना जाता है कि इनपुट की जांच की गई है ताकि कोई भी डुप्लिकेट तत्वों की कुल संख्या के आधे से कम हो, इसलिए गैर-आसन्न समाधानों का एक सेट मौजूद है। उदाहरण के लिए, ook ook ook eek अस्वीकार कर दिया जाएगा। तारों में रिक्त स्थान और यूटीएफ -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

अस्वीकृति पूर्व शर्त को देखते हुए यह कई «तुल्यता कक्षाओं» (ईसीएस) में शब्द सूची विभाजित करने के लिए संभव है। अस्वीकृति का तात्पर्य है कि एक से अधिक ईसी नहीं है जो आंशिक रूप से सूची के एक आधे हिस्से में और आंशिक रूप से दूसरे में है।

हम इस ईसी का एक हिस्सा अलग रखते हैं, ताकि (1) शेष भाग सूची के शेष हिस्सों में से एक से अधिक में न हो, और (2) हिस्सों आकार में कड़ाई से बराबर हैं। फिर हम अलग-अलग हिस्सों को घुमाते हैं। उसके बाद, हम उन्हें विलय करते हैं, पहली छमाही विषम तत्वों पर कब्जा करते हैं, जबकि शाम दूसरी छमाही के लिए होते हैं। फिर हम पहले से अलग शेष तत्वों को यादृच्छिक रूप से सम्मिलित करते हैं। यह काफी सरल है, क्योंकि उनमें से सभी एक ईसी से संबंधित हैं और इस प्रकार उन स्थानों को चिह्नित करना आसान है जहां वे हो सकते हैं और जहां वे नहीं कर सकते हैं।

निर्माण के द्वारा, एक ईसी से संबंधित कोई भी दो निकट तत्व नहीं हो सकते हैं।

[संपादित करें]] अंत में, ऊपर क्या है इसका कार्यान्वयन।

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"