Créer de nombreuses permutations aléatoires et contraintes d'une liste

Question

Je dois faire une liste aléatoire de permutations. Les éléments peuvent être tout sauf supposer qu'ils sont les entiers 0 à x-1. Je veux faire y des listes, chacune contenant z éléments. Les règles sont qu'aucune liste ne peut contenir deux fois le même élément et que sur toutes les listes, le nombre d'utilisations de chaque élément est identique (ou aussi proche que possible). Par exemple, si mes éléments sont 0,1,2,3, y est 6 et z est 2, une solution possible est:

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

Chaque ligne ne comporte que des éléments uniques et aucun élément n'a été utilisé plus de 3 fois. Si y était 7, 2 éléments seraient utilisés 4 fois, le reste 3.

Answer 1

Cela pourrait être amélioré, mais cela semble faire l'affaire (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, une façon de s'en approcher:

1 - mélangez votre liste

2 - prenez les y premiers éléments pour former la rangée suivante

4 - répéter (2) tant que vous avez des numéros dans la liste

5 - Si vous n'avez pas assez de nombres pour terminer la liste, remaniez la liste d'origine et prenez les éléments manquants, en vous assurant de ne pas reprendre les numéros.

6 - Recommencez à l'étape (2) tant que vous avez besoin de lignes

Je pense que cela devrait être aussi aléatoire que possible et que vous suivrez certainement vos critères. De plus, vous avez très peu de tests pour les éléments en double.

Answer 3

Tout d’abord, vous pouvez toujours trier la liste de manière aléatoire à la fin. Ne vous inquiétez donc pas pour faire & "permutations aléatoires &"; (difficile); et ne vous souciez que de 1) faire des permutations (facile) et 2) de les randomiser (facile).

Si vous voulez & "vraiment &" groupes aléatoires, vous devez accepter le fait que la randomisation par nature ne permet pas vraiment la contrainte de & "même la distribution &"; des résultats - vous pouvez obtenir cela ou une série de résultats similaires. Si vous voulez vraiment une distribution uniforme, commencez par répartir les ensembles de manière uniforme, puis distribuez-les au hasard en groupe.

Devez-vous utiliser chaque élément du jeu x de manière uniforme? D'après les règles, il n'est pas clair que je ne puisse pas simplement interpréter l'interprétation suivante:

Notez les points suivants: & "; sur toutes les listes, le nombre d'utilisations de chaque élément est identique (ou aussi proche que possible) &";

Sur la base de ce critère et de la règle qui z < x *, je postule que vous pouvez simplement énumérer tous les éléments sur toutes les listes. Vous faites donc automatiquement une liste des éléments énumérés à la position z. Votre exemple ne remplit pas la règle ci-dessus aussi fidèlement que ma version. En utilisant votre exemple de x = {0,1,2,3} y = 6 et z = 2, je reçois: 0,1 0,1 0,1 0,1 0,1 0,1

Maintenant, je n'ai pas utilisé 2 ou 3, mais vous n'avez pas dit que je devais les utiliser tous. Si je devais les utiliser tous et que cela ne me dérange pas de pouvoir prouver que je suis & "Aussi proche que possible &"; pour un usage identique, je voudrais simplement énumérer tous les éléments à travers les listes, comme ceci: 0,1 2,3 0,1 2,3 0,1 2,3

Enfin, supposons que je dois vraiment utiliser tous les éléments. Pour calculer le nombre de répétitions de chaque élément, il suffit de prendre (y * z) / (nombre de x). De cette façon, je n'ai pas à m'asseoir et à m'inquiéter de la répartition des éléments de la liste. S'il y a un reste ou si le résultat est inférieur à 1, alors je sais que je ne pourrai pas obtenir le nombre exact de répétitions, alors dans ces cas, peu importe d'essayer de gaspiller de l'énergie de calcul pour le rendre parfait. Je soutiens que le résultat le plus rapide reste simplement à énumérer comme ci-dessus, et utilise le calcul ici pour montrer pourquoi un résultat parfait a été atteint ou non. Un algorithme sophistiqué permettant d'extraire de ce calcul le nombre de positions en doublons pourrait être atteint, mais & "Il est trop long pour tenir ici dans la marge &";

.

* Chaque liste a le même nombre d'éléments z, il sera donc impossible de créer des listes où z est supérieur à x tout en respectant la règle selon laquelle aucune liste ne peut contenir deux fois le même élément. Par conséquent, cette règle exige que z ne soit pas supérieur à x.

Answer 4

Sur la base de nouveaux détails dans les commentaires, la solution peut simplement être une implémentation d’un algorithme de génération de permutation aléatoire standard. Vous trouverez une longue discussion sur les algorithmes de génération de permutation aléatoire ici:

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

(recherche Google: génération de permutation aléatoire)

Answer 5

Ceci fonctionne 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

Exemple d'utilisation:

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