Como obter uma sequência aleatoriamente aleatória baseada no indicador de intensidade aleatória?

Question

Eu preciso obter uma sequência de elementos embaralhados em um intervalo, mas eu quero determinar quanto essa sequência deve ser embaralhada . Por exemplo, suponha que nosso intervalo seja 1-100 e eu queira uma sequência de 10 números. Todas essas sequências são válidas:

{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}

Como você pode ver, todos os elementos das três sequências são os mesmos, mas eles são embaralhados com intensidade diferente. A primeira sequência é ordenada (isto é, não é embaralhada), a segunda é embaralhada um pouco e a última é embaralhada muito mais (e talvez apenas essa seja realmente embaralhada :)). Agora eu quero um método para que eu possa obter essas seqüências com base em um indicador chamado indicador de intensidade aleatória, ou si2 .

Minha abordagem

Espero que esta seção não torne minha pergunta um problema XY . Eu só quero compartilhar minha abordagem e não é o ponto da questão. No entanto, ficarei feliz se minhas perguntas nesta seção forem respondidas.

Eu usei a seguinte série de comandos para obter uma sequência de 2.000.000 de números no intervalo 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 

Como você pode ver, a sequência tem 10.000 pedaços de 100 números que são decifrados e sequenciados aleatoriamente. Eu posso, por exemplo, usar 150 ao invés do primeiro 100 e 50 ao invés de segundos, então a intensidade do shuffle é quadruplicada. Mas essa abordagem tem alguns problemas (pelo menos para mim).

• Essa abordagem é muito lenta (e eu quero saber o porquê. Descobri que quanto maiores os blocos, mais rápida será a operação.).
• Também requer determinação manual dos dois números que indique a intensidade de embaralhamento.
• E, talvez o mais importante, é que não foi aleatoriamente aleatoriamente . Como você pode ver, os tamanhos dos pedaços são os mesmos.

Solução ideal

Idealmente, quero um script com opções como esta:

myshuf SI2 MIN MAX NUM [OUTPUT] 

enquanto MIN e MAX determinam o intervalo, NUM determina o tamanho da sequência e SI2 é o indicador de intensidade aleatória. Quanto maior for o SI2 , mais barulhenta será a intensidade. SI2 estará entre 0 e 10.

Então

myshuf 0 0 2000000 2000000

fornece uma sequência classificada de 2.000.000 números entre 0 e 2.000.000 e

myshuf 10 0 2000000 2000000

dá uma sequência muito boa.

Se você é curioso para saber por que eu preciso dessas sequências, devo dizer que tenho alguns algoritmos de classificação e quero testar cada um deles e ver a complexidade do tempo deles em diferentes tipos de entradas.

    

Answer 1

Uma maneira de misturar com intensidade variada pode ser pegar uma lista ordenada e fazer um número variável de permutações aleatórias (certificando-se de que os elementos não sejam movidos mais de uma vez).

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 garantirá que nenhum dos elementos manterá sua posição original (embaralhar n garante que 2 * n elementos obtenham uma posição diferente). Existem alguns shufflings que nunca serão alcançados. Para uma lista 1,2,3, por exemplo, os únicos resultados possíveis são 2,1,3 , 3,2,1 e 1,3,2 . Não 3,1,2

Com um shuffle 5 , você também pode acabar com 6,7,8,9,10,1,2,3,4,5 , o que talvez não seja muito embaralhado.