4

Estou desenvolvendo um programa e preciso gerar um array de 16 elementos, em que cada entrada é 0, 1 ou 2; e depois preciso verificar se esse array satisfaz certas condições. Para gerar este array, estou fazendo:

ni = np.array(np.random.randint(0,3))
for i in range(15):
    n1 = np.array(np.random.randint(0,3))
    ni = np.append(ni,n1)

O output é:

array([0, 0, 1, 0, 1, 2, 2, 0, 2, 1, 0, 1, 2, 1, 0, 2])

O problema é que este método as vezes gera arrays repetidos, o que atrapalha um pouco a performance do meu problema. Existe algum jeito de garantir que sempre será gerados novos arrays? No caso o array do output não poderia mais ser gerado.

3 Respostas 3

2

No fundo você quer "gerar N coisas aleatórias sem repetir" (vários arrays diferentes), então uma alternativa é seguir esta ideia:

  • gerar todas as possibilidades (supondo que a quantidade total é 'X')
  • escolher N índices aleatórios entre zero e X, e pegar as possibilidades que estão nestes índices

Para o primeiro passo, você pode usar itertools.product, e para o segundo passo, use random.sample para gerar os índices, e itertools.slice para pegar o elemento que está naquele índice. Algo assim:

import numpy as np
from itertools import product, islice
from random import sample

# números que podem estar no array
nums = range(0, 3)
# tamanho dos arrays
tamanho_arrays = 16
# gerar 20 arrays diferentes
quantidade = 20
# quantidade total de arrays possíveis
total_arrays_possiveis = len(nums) ** tamanho_arrays

# sample pega 20 índices aleatórios entre zero e o total de arrays possíveis
for indice in sample(range(total_arrays_possiveis), k=quantidade):
    # gera as possibilidades
    todos_possiveis = product(nums, repeat=tamanho_arrays)
    # pega somente a que está na posição do índice
    lista = next(islice(todos_possiveis, indice, indice + 1))
    array = np.array(lista) # gera o np.array
    print(array)

Usei itertools porque seria bem custoso gerar todas as possibilidades e mantê-las em memória. No seu caso específico, há três valores possíveis (os números 0, 1 e 2), em um array com 16 elementos, então o total de possibilidades é 316 (ou seja, 43.046.721 de possibilidades - mais de quarenta e três milhões de arrays possíveis).

Usando itertools, os elementos só são obtidos quando necessário, economizando memória (e tempo também, pois gerar tudo demoraria muito).

Com sample eu garanto que não haverá índices repetidos, e assim garanto que o array a ser obtido nunca será igual aos que já foram pegos anteriormente.


Guardar os arrays já obtidos em uma lista e ir vendo se os novos já existem nesta lista (como sugerido na outra resposta) também é uma opção, porém pode não escalar bem se a quantidade de arrays a serem gerados for muito grande. Por exemplo, se você quiser gerar 10 mil arrays diferentes, vai chegar uma hora que a lista terá, por exemplo, 9 mil arrays. Aí você terá que percorrer esses 9 mil pra ver se é repetido. Depois, percorre 9001, depois 9002, etc. É um algoritmo bem ineficiente (também chamado jocosamente de Shlemiel the painter’s algorithm) - claro que para valores pequenos a diferença será ínfima, mas lembre-se que "para valores pequenos, tudo é rápido".


E vale lembrar que itertools.product gera todos os arrays possíveis (inclusive aqueles em que todos os números são iguais). Mas isso não é um "bug", já que com randint isso também pode acontecer (só tem uma chance menor, mas sendo "aleatório", não é impossível).

2
2

Isso é um problema de algoritmo, e vejo diversas opções.

Para exemplificar, vou trabalhar com um array de 2 elementos:

  1. se você pensar, esse array pode ser representado por um numero que será escrito na base 3, sendo assim, os possíveis valores (para 2 dígitos) 0(00), 1(01), 2(02), 3(10), 4(11), 5(12), 6(20), 7(21), 8(22)

Sendo assim, voce pode gerar um número aleatório entre 0 e 8 (3n - 1) e converter ele para array.

Para facilitar, vamos falar de um array de 3 posições (numero entre 0 e 26):

number # número aleatório entre 0 e 26
array[2] = number % 3
number = number / 3
array[1] = number % 3
array[0] = number / 3

Assim, você pode manter o registro de arrays mantendo um registro do numero em um array de cache.

cache # array de 3^n posições inicializado com false em todas as posições

do
  number = random(0, 3^n)
while cache[number] # o numero tem que ser regerado ate se encontrar um que nunca foi usado

cache[number] = true

array = gerar_array_from_number(number)
  1. Gerar um string a partir do array e usar ela para checar se o array já foi gerado novamente:
string = array.join("")
  1. utilizar outra função para gerar um hash do array e checar se ele já foi gerado anteriormente

Outra opção é gerar vários números entre 0 e 3n - 1, e convertê-los para a base 3, obtendo assim o respectivo array:

import numpy as np
from random import sample

def gerar_array(x, base, size):
    digits = []
    while x:
        digits.insert(0, x % base)
        x //= base
    if len(digits) < size:
        digits = ([0] * (size - len(digits))) + digits
    return np.array(digits)

# números que podem estar no array estão entre 0 e n - 1
n = 3

# tamanho dos arrays
tamanho_arrays = 16
# gerar 20 arrays diferentes
quantidade = 20

for i in sample(range(n ** tamanho_arrays - 1), k=quantidade):
    print(gerar_array(i, n, tamanho_arrays))

sample garante que os números gerados não se repetem, assim nem precisaria de um cache para saber se são repetidos.

1
  • Gostei muito desta ideia e tomei a liberdade de adicionar um código em Python que a implementa. Claro que se não concordar, basta reverter a edição.
    – hkotsubo
    31/05/2021 às 14:23
1

Você não pode usar uma lista auxiliar? Caso possível é bem fácil: Crie essa lista e, após gerar o array de números aleatórios faça uma verificação, se a sequência for única é inserida no seu array, senão, gera uma nova sequência.

Algo mais ou menos assim:

lista = []
ni = np.array(np.random.randint(0,3))
for i in range(15):
    n1 = np.array(np.random.randint(0,3))
    ni = np.append(ni,n1)
if lista já contém o valor gerado:
   gera uma nova sequência aleatória
else:
   salva o valor gerado
    

A verificação pode ser de maneiras variadas, então você pode escolher a melhor para o seu caso.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .