Crear muchas permutaciones aleatorias y restringidas de una lista

Question

Necesito hacer una lista aleatoria de permutaciones.Los elementos pueden ser cualquier cosa menos asumir que son números enteros del 0 al x-1.Quiero hacer listas y, cada una de las cuales contenga elementos z.Las reglas son que ninguna lista puede contener el mismo elemento dos veces y que en todas las listas, el número de veces que se usa cada elemento es el mismo (o lo más cercano posible).Por ejemplo, si mis elementos son 0,1,2,3, y es 6 yz es 2, entonces una posible solución es:

0,3
1,2
3,0
2,1
0,1
2,3

Cada fila tiene sólo elementos únicos y ningún elemento se ha utilizado más de 3 veces.Si y fuera 7, entonces se usarían 2 elementos 4 veces, el resto 3.

Answer 1

Esto podría mejorarse, pero parece funcionar (Python):

import math, random


def get_pool(items, y, z):
    slots = y*z

    use_each_times = slots/len(items)
    exceptions = slots - use_each_times*len(items)


    if (use_each_times > y or
        exceptions > 0 and use_each_times+1 > y):
        raise Exception("Impossible.")


    pool = {}
    for n in items:
        pool[n] = use_each_times

    for n in random.sample(items, exceptions):
        pool[n] += 1

    return pool

def rebalance(ret, pool, z):
    max_item = None
    max_times = None

    for item, times in pool.items():
        if times > max_times:
            max_item = item
            max_times = times


    next, times = max_item, max_times

    candidates = []
    for i in range(len(ret)):
        item = ret[i]

        if next not in item:
            candidates.append( (item, i) )


    swap, swap_index = random.choice(candidates)

    swapi = []
    for i in range(len(swap)):
        if swap[i] not in pool:
            swapi.append( (swap[i], i) )


    which, i = random.choice(swapi)

    pool[next] -= 1
    pool[swap[i]] = 1
    swap[i] = next

    ret[swap_index] = swap

def plist(items, y, z):
    pool = get_pool(items, y, z)

    ret = []
    while len(pool.keys()) > 0:
        while len(pool.keys()) < z:
            rebalance(ret, pool, z)

        selections = random.sample(pool.keys(), z)

        for i in selections:
            pool[i] -= 1
            if pool[i] == 0:
                del pool[i]

        ret.append( selections )

    return ret


print plist([0,1,2,3], 6, 2)

Answer 2

Ok, una forma de aproximar eso:

1 - baraja tu lista

2 - toma los primeros elementos y para formar la siguiente fila

4 - repite (2) mientras tengas números en la lista

5 - si no tienes suficientes números para terminar la lista, reorganiza la lista original y toma los elementos que faltan, asegurándote de no volver a tomar números.

6 - Comience de nuevo en el paso (2) siempre que necesite filas

Creo que esto debería ser lo más aleatorio posible y seguramente seguirá sus criterios.Además, tienes muy pocas pruebas para detectar elementos duplicados.

Answer 3

Primero, siempre puedes ordenar la lista aleatoriamente al final, así que no nos preocupemos por hacer "permutaciones aleatorias" (difíciles);y solo preocúpate por 1) hacer permutaciones (fácil) y 2) aleatorizarlas (fácil).

Si desea grupos "verdaderamente" aleatorios, debe aceptar que la aleatorización por naturaleza realmente no permite la restricción de una "distribución uniforme" de los resultados; puede obtener eso o puede obtener una serie de grupos de apariencia similar.Si realmente desea una distribución uniforme, primero distribuya los conjuntos de manera uniforme y luego aleatorícelos como grupo.

¿Tienes que utilizar cada elemento del conjunto x de manera uniforme?De las reglas no queda claro que no pudiera simplemente hacer la siguiente interpretación:

Tenga en cuenta lo siguiente:"en todas las listas, el número de veces que se utiliza cada elemento es el mismo (o lo más cercano posible)"

Con base en este criterio y la regla de que z < x*, postulo que simplemente se pueden enumerar todos los elementos en todas las listas.Entonces automáticamente crea una lista y de los elementos enumerados en la posición z.Su ejemplo no cumple la regla anterior tan estrechamente como lo hará mi versión.Usando su ejemplo de x={0,1,2,3} y=6 y z=2, obtengo:0,1 0,1 0,1 0,1 0,1 0,1

Ahora no usé 2 o 3, pero no dijiste que tenía que usarlos todos.Si tuviera que usarlos todos y no me importa poder demostrar que estoy "lo más cerca posible" de un uso uniforme, simplemente enumeraría todos los elementos a través de las listas, de esta manera:0,1 2,3 0,1 2,3 0,1 2,3

Finalmente, supongamos que realmente tengo que usar todos los elementos.Para calcular cuántas veces se puede repetir cada elemento, simplemente tomo (y*z)/(recuento de x).De esa manera, no tengo que sentarme y preocuparme por cómo dividir los elementos de la lista.Si hay un resto, o el resultado es menor que 1, entonces sé que no obtendré un número exacto de repeticiones, por lo que en esos casos, no importa mucho intentar desperdiciar energía computacional para hacerlo perfecto.Sostengo que el resultado más rápido sigue siendo simplemente enumerar como se indicó anteriormente y utilizar el cálculo aquí para mostrar por qué se logró o no un resultado perfecto.Se podría lograr un algoritmo sofisticado para extraer de este cálculo cuántas posiciones estarán duplicadas, pero "es demasiado largo para caber aquí en el margen".

*Cada lista tiene el mismo número z de elementos, por lo que será imposible hacer listas donde z sea mayor que x y aun así cumplir la regla de que ninguna lista puede contener el mismo elemento dos veces.Por tanto, esta regla exige que z no pueda ser mayor que x.

Answer 4

Según los nuevos detalles de los comentarios, la solución puede ser simplemente una implementación de un algoritmo estándar de generación de permutaciones aleatorias.Aquí hay una larga discusión sobre los algoritmos de generación de permutaciones aleatorias:

http://www.techuser.net/randpermgen.html

(De la búsqueda de Google:generación de permutación aleatoria)

Answer 5

Esto funciona en Ruby:

# list is the elements to be permuted
# y is the number of results desired
# z is the number of elements per result
# equalizer keeps track of who got used how many times
def constrained_permutations list, y, z
  list.uniq! # Never trust the user. We want no repetitions.
  equalizer = {}
  list.each { |element| equalizer[element] = 0 }

  results = []
  # Do this until we get as many results as desired
  while results.size < y
    pool = []
    puts pool
    least_used = equalizer.each_value.min
    # Find how used the least used element was
    while pool.size < z
      # Do this until we have enough elements in this resultset
      element = nil
      while element.nil?
        # If we run out of "least used elements", then we need to increment
        # our definition of "least used" by 1 and keep going.
        element = list.shuffle.find do |x|
          !pool.include?(x) && equalizer[x] == least_used
        end
        least_used += 1 if element.nil?
      end
      equalizer[element] += 1
      # This element has now been used one more time.
      pool << element
    end
    results << pool
  end
  return results
end

Uso de muestra:

constrained_permutations [0,1,2,3,4,5,6], 6, 2
=> [[4, 0], [1, 3], [2, 5], [6, 0], [2, 5], [3, 6]]
constrained_permutations [0,1,2,3,4,5,6], 6, 2
=> [[4, 5], [6, 3], [0, 2], [1, 6], [5, 4], [3, 0]]
enter code here

Answer 6

http://en.wikipedia.org/wiki/Fisher-Yates_shuffle