Criar muitos constrangidos permutação, aleatória de uma lista

Question

Eu preciso fazer uma lista aleatória de permutações. Os elementos podem ser qualquer coisa, mas assumir que eles são os números inteiros de 0 a x-1. Eu quero fazer listas y, cada uma contendo elementos z. As regras são que nenhuma lista pode conter o mesmo elemento duas vezes e que ao longo do todo das listas, o número de vezes que cada um dos elementos é utilizada é a mesma (ou tão próximo quanto possível). Por exemplo, se os elementos são 0,1,2,3, Y é 6, e Z é 2, em seguida, uma solução possível é:

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

Cada linha tem apenas elementos únicos e nenhum elemento foi usado mais de 3 vezes. Se y foram de 7, em seguida, 2 elementos seria usado 4 vezes, o resto 3.

Answer 1

Esta poderia ser melhorado, mas parece fazer o trabalho (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, uma maneira de aproximar o seguinte:

1 - embaralhar sua lista

2 - dar os primeiros elementos y para formar a próxima linha

4 - repeat (2) enquanto você tem os números na lista

5 -. Se você não tem número suficiente para terminar a lista, reorganizar a lista original e tomar os elementos em falta, certificando-se de que você faz números não retomar

6 - Iniciar mais no passo (2), desde que você precisar de linhas

Eu acho que isso deve ser tão aleatório como você pode fazê-lo e com certeza vai seguir os seus critérios. Além disso, você tem muito pouco testes para elementos duplicados.

Answer 3

Em primeiro lugar, você sempre pode aleatoriamente tipo da lista, no final, de modo de não se preocupar vamos sobre fazer "permutações aleatórias" (duro); e apenas se preocupar com a 1) fazer permutações (fácil) e 2) randomizing-los (fácil).

Se você quer "verdadeiramente" grupos aleatórios, você tem que aceitar que randomização, por natureza, não permite, realmente, a restrição de "distribuição uniforme" dos resultados - você pode conseguir isso ou você pode obter uma série de similar- procurando queridos. Se você realmente quer uma distribuição uniforme, primeiro fazer os conjuntos distribuídos uniformemente e, em seguida, embaralhar-los como um grupo.

Você tem que usar cada elemento no conjunto x uniformemente? Não está claro a partir das regras que eu não poderia apenas fazer a seguinte interpretação:

Observe o seguinte: "sobre todas as listas, o número de vezes que cada um dos elementos é usado é o mesmo (ou o mais próximo possível)"

Com base nesses critérios, e a regra de que z

Agora eu não usar 2 ou 3, mas você não disse que eu tinha que usar todos eles. Se eu tivesse que usá-los todos e eu não me importo de ser capaz de provar que eu sou "o mais próximo possível" para uso mesmo, gostaria apenas de enumerar através de todos os itens através das listas, como este: 0,1 2,3 0,1 2,3 0,1 2,3

Finalmente, suponha que eu realmente tem que usar todos os elementos. Para calcular quantas vezes cada elemento pode repetir, eu só dou (y * z) / (contagem de x). Dessa forma, eu não tenho que sentar e preocupação sobre como dividir os itens na lista. Se houver um resto, ou o resultado for menor que 1, então eu sei que não vai ter um número exato de repetições, por isso, nesses casos, não importa muito para tentar desperdiçar energia computacional para torná-lo perfeito. Eu afirmo que o resultado mais rápido ainda é apenas para enumerar como acima, e usar o cálculo aqui para mostrar por que quer um resultado perfeito foi ou não alcançado. Um algoritmo de fantasia para extrato deste cálculo quantas posições serão duplicados poderiam ser alcançados, mas "é muito longo para caber aqui na margem".

* Cada lista tem o mesmo número z de elementos, por isso vai ser impossível fazer listas, onde z é maior do que x e ainda cumprir a regra de que nenhuma lista pode conter o mesmo elemento duas vezes. Portanto, esta regra exige que z não pode ser maior do que x.

Answer 4

Com base em novos detalhes nos comentários, a solução pode ser simplesmente uma implementação de um algoritmo padrão aleatório geração permutação. Há uma longa discussão de algoritmos de geração de permutação aleatória aqui:

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

(De pesquisa do Google: geração permutação aleatória)

Answer 5

Isso funciona em 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

Exemplo de uso:

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