Crea molte permutazioni casuali e vincolate di un elenco

Question

Devo fare un elenco casuale di permutazioni.Gli elementi possono essere tutt'altro che presupporre che siano numeri interi da 0 a x-1.Voglio creare y liste, ciascuna contenente z elementi.Le regole sono che nessuna lista può contenere lo stesso elemento due volte e che in tutte le liste, il numero di volte in cui ciascun elemento viene utilizzato è lo stesso (o il più vicino possibile).Ad esempio, se i miei elementi sono 0,1,2,3, y è 6 e z è 2, allora una possibile soluzione è:

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

Ogni riga ha solo elementi univoci e nessun elemento è stato utilizzato più di 3 volte.Se y fosse 7, allora 2 elementi verrebbero usati 4 volte, il resto 3.

Answer 1

Questo potrebbe essere migliorato, ma sembra fare il lavoro (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, un modo per approssimarlo:

1 - rimescola la tua lista

2 - prendi i primi elementi y per formare la riga successiva

4 - ripeti (2) finché hai numeri nell'elenco

5 - se non hai abbastanza numeri per finire la lista, rimescola la lista originale e prendi gli elementi mancanti, facendo attenzione a non ripetere i numeri.

6 - Ricomincia dal passaggio (2) finché sono necessarie righe

Penso che questo dovrebbe essere il più casuale possibile e seguirà sicuramente i tuoi criteri.Inoltre, hai pochissimi test per gli elementi duplicati.

Answer 3

Innanzitutto, puoi sempre ordinare in modo casuale l'elenco alla fine, quindi non preoccupiamoci di fare "permutazioni casuali" (difficile);e preoccupati solo di 1) creare permutazioni (facile) e 2) randomizzarle (facile).

Se vuoi gruppi "veramente" casuali, devi accettare che la randomizzazione per natura non consente realmente il vincolo di "distribuzione uniforme" dei risultati: potresti ottenerlo o potresti ottenere una serie di gruppi dall'aspetto simile.Se vuoi davvero una distribuzione uniforme, distribuisci prima i set in modo uniforme, quindi randomizzali come gruppo.

Devi utilizzare ogni elemento dell'insieme x in modo uniforme?Non è chiaro dalle regole che non potrei semplicemente dare la seguente interpretazione:

Tieni presente quanto segue:"in tutti gli elenchi, il numero di volte in cui ciascun elemento viene utilizzato è lo stesso (o il più vicino possibile)"

Sulla base di questo criterio e della regola z < x*, postulo che puoi semplicemente enumerare tutti gli elementi in tutti gli elenchi.Quindi crei automaticamente un elenco degli elementi enumerati nella posizione z.Il tuo esempio non soddisfa la regola di cui sopra tanto quanto lo farà la mia versione.Usando il tuo esempio di x={0,1,2,3} y=6 e z=2, ottengo:0,1 0,1 0,1 0,1 0,1 0,1

Ora non ne ho usati 2 o 3, ma non hai detto che dovevo usarli tutti.Se dovessi usarli tutti e non mi interessasse poter dimostrare di essere "il più vicino possibile" all'utilizzo uniforme, mi limiterei ad enumerare tutti gli elementi attraverso gli elenchi, in questo modo:0,1 2,3 0,1 2,3 0,1 2,3

Infine, supponiamo di dover davvero utilizzare tutti gli elementi.Per calcolare quante volte ciascun elemento può ripetersi, prendo semplicemente (y*z)/(conteggio di x).In questo modo, non devo sedermi e preoccuparmi di come dividere gli elementi nell'elenco.Se c'è un resto, o il risultato è inferiore a 1, allora so che non otterrò un numero esatto di ripetizioni, quindi in questi casi non ha molta importanza cercare di sprecare energia di calcolo per renderlo perfetto.Io sostengo che il risultato più veloce sia comunque semplicemente enumerare quanto sopra e utilizzare il calcolo qui per mostrare perché è stato o meno raggiunto un risultato perfetto.Si potrebbe ottenere un sofisticato algoritmo per estrarre da questo calcolo quante posizioni saranno duplicate, ma "è troppo lungo per rientrare qui nel margine".

*Ogni lista ha lo stesso numero z di elementi, quindi sarà impossibile creare liste in cui z è maggiore di x rispettando comunque la regola secondo cui nessuna lista può contenere lo stesso elemento due volte.Pertanto, questa regola richiede che z non possa essere maggiore di x.

Answer 4

Sulla base dei nuovi dettagli nei commenti, la soluzione potrebbe essere semplicemente un'implementazione di un algoritmo standard di generazione di permutazioni casuali.C'è una lunga discussione sugli algoritmi di generazione di permutazioni casuali qui:

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

(Dalla ricerca su Google:generazione di permutazioni casuali)

Answer 5

Funziona in 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

Utilizzo del campione:

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