☰

셔플 강도 표시기를 기반으로 무작위 셔플 시퀀스를 얻는 방법은 무엇입니까?

tag-icon • tag-icon shell-script
셔플 강도 표시기를 기반으로 무작위 셔플 시퀀스를 얻는 방법은 무엇입니까?

범위 내에서 일련의 스크램블된 요소를 가져와야 하지만확실히하고 싶어얼마나이 시퀀스는 스크램블되어야 합니다.. 예를 들어 범위가 이라고 가정하면 1-10010개의 숫자 시퀀스를 원합니다. 다음 시퀀스는 모두 유효합니다.

{1,5,17,43,44,67,77,77,83,90}

{1,90,17,43,44,77,77,67,83,5}

{67,5,90,77,43,77,17,1,83,44}

보시다시피, 세 시퀀스의 모든 요소는 동일하지만 셔플 강도가 다릅니다. 첫 번째 시퀀스는 정렬되고(즉, 스크램블되지 않음) 두 번째 시퀀스는 약간 스크램블되며 마지막 시퀀스는 훨씬 더 많이 스크램블됩니다(아마도 이 시퀀스만 실제로 스크램블된 것일 수 있습니다 :)). 이제 나는 셔플 강도 표시기 또는 이라는 표시기를 기반으로 이러한 시퀀스를 얻을 수 있는 방법을 원합니다 si2.

내 방법

이 부분이 내 문제를 일으키지 않기를 바랍니다.XY 문제. 나는 내 접근 방식을 공유하고 싶을 뿐이며 질문의 요점은 아닙니다.그러나 이 섹션의 질문에 대한 답변이 제공된다면 기쁠 것입니다.

2,000,000 범위의 일련의 숫자를 얻기 위해 다음 일련의 명령을 사용했습니다 1-2000000.

for i in `seq 10000`; do 
    shuf -i 1-2000000 -r -n 100 | sort ; shuf -i 1-2000000 -r -n 100; 
    done > input

보시다시피, 시퀀스에는 교차 정렬되고 뒤섞인 100개의 숫자로 구성된 10,000개의 블록이 있습니다. 예를 들어, 150첫 번째 대신에 100두 50번째 대신에 사용할 수 있습니다 .섞는 힘4배가 됩니다. 그러나 이 접근 방식에는 (적어도 나에게는) 몇 가지 문제가 있습니다.

  • 이 방법은너무 느린( 그리고이유를 알고 싶습니다.청크가 클수록 작업 속도가 빨라진다는 것을 알았습니다. ).
  • 그것은 또한 필요하다수동 측정셔플의 강도를 나타내는 두 숫자 중 하나입니다.
  • 그리고 아마도 가장 중요한 것은,실제로 무작위 셔플이 아닙니다.. 보시다시피 블록 크기는 동일합니다.

이상적인 솔루션

이상적으로는 다음과 같은 옵션이 포함된 스크립트를 원합니다.

myshuf SI2 MIN MAX NUM [OUTPUT]

while은 순서 섞기 강도를 나타내는 시퀀스의 범위 와 크기를 MIN결정합니다 . 높을수록 셔플이 더 강해집니다. 0에서 10 사이가 됩니다. MAXNUMSI2SI2SI2

그래서

myshuf 0 0 2000000 2000000

0에서 2,000,000 사이의 2,000,000개 숫자로 구성된 정렬된 시퀀스를 제공합니다.

myshuf 10 0 2000000 2000000

정말 멋진 셔플링 시퀀스를 제공합니다.

왜 그런 시퀀스가 ​​필요한지 궁금하시다면 제가 몇 가지 정렬 알고리즘을 가지고 있고 각각을 시도해 보고 다양한 유형의 입력에 대한 시간 복잡도를 확인하고 싶다고 말씀드리고 싶습니다.

답변1

다양한 강도로 섞는 한 가지 방법은 정렬된 목록을 사용하여 다양한 수의 무작위 순열을 수행하는 것입니다(요소가 두 번 이상 이동되지 않도록 확인).

shuffle() {
  awk -v n="$1" '
    {line[NR]=$0; i[NR] = NR}
    END{
      if (n > NR/2) {
        print "two many permutations"
        exit(1)
      }
      srand()
      for (x = 1; x <= NR; x++) {
        # shuffle the list of indicies
        y = int(rand() * NR) + 1
        tmp = i[x]; i[x] = i[y]; i[y] = tmp
      }
      for (x = 1; x <= n; x++) {
        # get the lines to permute from the head of the shuffled
        # list of indices
        y = i[x*2-1]; z = i[x*2]
        tmp = line[y]; line[y] = line[z]; line[z] = tmp
      }
      for (x = 1; x <= NR; x++) print line[x]
    }'
}

$ seq 10 | shuffle 0 | paste -sd , -
1,2,3,4,5,6,7,8,9,10
$ seq 10 | shuffle 1 | paste -sd , -
1,2,6,4,5,3,7,8,9,10
$ seq 10 | shuffle 5 | paste -sd , -
9,6,5,10,3,2,8,7,1,4

shuffle 5어떤 요소도 원래 위치를 유지하지 않는다는 것을 보장합니다(셔플은 n2*n 요소가 다른 위치를 얻도록 보장합니다). 결코 달성하지 못할 셔플이 있습니다. 예를 들어 목록 1,2,3의 경우 가능한 결과는 2,1,3, 3,2,1및 뿐입니다 1,3,2. 아니요3,1,2

이를 통해 혼란이 덜할 수 있는 결과를 얻을 수도 있습니다 shuffle 5.6,7,8,9,10,1,2,3,4,5

관련 정보