Erstellen Sie viele gezwungen, zufällige Permutation einer Liste

Question

Ich brauche eine zufällige Liste von Permutationen zu machen. Die Elemente können alles sein, aber davon ausgehen, dass sie die ganzen Zahlen 0 bis x-1 sind. Ich möchte y Listen machen, von denen jede z-Elemente. Die Regeln sind, dass keine Liste das gleiche Element enthalten kann zweimal, und dass über alle Listen, die Anzahl der einzelnen Elemente verwendet werden, ist das gleiche (oder so nahe wie möglich). Zum Beispiel, wenn meine Elemente 0,1,2,3 sind, y 6 ist und z 2 ist, dann ist eine mögliche Lösung:

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

Jede Reihe hat nur einzigartige Elemente und kein Element mehr als 3 mal verwendet wurde. Wenn y 7 ist, dann 2 mal Elemente 4 verwendet werden würden, der Rest 3.

Answer 1

Dies könnte verbessert werden, aber es scheint, den Job (Python) zu tun:

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, ein Weg zu nähern, dass:

1 - mische Liste

2 - nehmen die y ersten Elemente der nächsten Reihe bilden

4 - Wiederholung (2), solange Sie haben Zahlen in der Liste

5 - wenn Sie die Liste nicht genug Zahlen zu beenden, neu mischen die ursprüngliche Liste und die fehlenden Elemente nehmen, dafür, dass Sie Zahlen nicht wiederholen

.

6 - in Schritt vorn anfangen (2), solange Sie Zeilen benötigen

Ich denke, das wie zufällig sein sollte, wie Sie es und Willen machen kann sicher Ihre Kriterien folgen. Plus, haben Sie sehr wenig Tests für doppelte Elemente.

Answer 3

Sie können zunächst immer zufällig die Liste am Ende sortieren, also lassen Sie sich nicht darum, „zufällige Permutationen“ (hart) sorgen; und Sorge nur etwa 1) machen Permutationen (leicht) und 2) Randomisierung sie (leicht).

Wenn Sie „wirklich“ zufällig Gruppen wollen, müssen Sie von Natur aus, dass die Randomisierung akzeptieren erlaubt nicht wirklich für die Einschränkung von „gleichmäßige Verteilung“ der Ergebnisse - du das, oder Sie können einen Lauf von ähnlich- erhalten aussehend. Wenn Sie wirklich eine gleichmäßige Verteilung wollen, zuerst die Sätze gleichmäßig verteilt machen und sie dann als Gruppe randomisieren.

Müssen Sie jedes Element in dem Satz gleichmäßig x benutzen? Es ist nicht klar von den Regeln, die ich konnte nicht einfach die folgende Interpretation machen:

Beachten Sie Folgendes: „über alle Listen, die jeweils Elemente die Anzahl der Male verwendet werden, ist das gleiche (oder so nahe wie möglich)“

auf dieser Kriterien, und die Regel, dass z

Jetzt habe ich nicht verwenden 2 oder 3, aber du hast nicht gesagt, ich sie alle verwenden musste. Wenn ich sie alle und ich kümmern sich nicht zu verwenden, der Lage sein, zu beweisen, dass ich bin „so nah wie möglich“ zu vergleichmäßigen Nutzung, würde ich nur aufzuzählen über alle Elemente, die über die Listen, wie folgt aus: 0,1 2,3 0,1 2,3 0,1 2,3

Schließlich nehme ich wirklich alle Elemente müssen verwenden. Um zu berechnen, wie oft jedes Element wiederholen kann, nehme ich nur (y * z) / (Anzahl der x). Auf diese Weise habe ich nicht zu sitzen und Sorgen darüber, wie die Elemente in der Liste zu unterteilen. Wenn es ein Rest ist, oder das Ergebnis kleiner als 1 ist, dann weiß ich, dass ich nicht eine genaue Zahl der Wiederholungen erhalten, also in diesen Fällen ist es nicht viel Materie tut, um zu versuchen Rechen Energie zu verschwenden, um es perfekt zu machen. Ich behaupte, dass das schnellste Ergebnis immer noch nur wie oben, aufzuzählen und die Berechnung verwenden hier zu zeigen, warum entweder ein perfektes Ergebnis war oder wurde nicht erreicht. Ein extravaganter Algorithmus aus dieser Berechnung zu extrahieren, wie viele Positionen werden Duplikate erreicht werden könnten, aber „es zu lang ist hier am Rande zu passen“.

* Jede Liste hat die gleiche z Anzahl der Elemente, so wird es unmöglich sein, Listen zu machen, wobei z größer als x ist und nach wie vor die Regel erfüllen, die keine Liste zweimal das gleiche Element enthalten. Daher ist diese Regel verlangt, dass z nicht als x größer sein kann.

Answer 4

Auf der Grundlage neuer Informationen in den Kommentaren kann die Lösung einfach eine Implementierung eines Standard zufällige Permutation Erzeugungsalgorithmus sein. Es gibt eine lange Diskussion der zufälligen Permutation Erzeugungsalgorithmen hier:

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

(Von Google-Suche: zufällige Permutation Generation)

Answer 5

Dies funktioniert 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

Verwendungsbeispiel:

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