Создайте множество ограниченных случайных перестановок списка

Это можно было бы улучшить, но, похоже, это работает (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)

Хорошо, один из способов приблизиться к этому:

1 - перемешать список

2 - возьмите y первых элементов, чтобы сформировать следующую строку

4 - повторять (2) до тех пор, пока у вас есть числа в списке

5 - если вам не хватает номеров, чтобы закончить список, перетасуйте первоначальный список и возьмите недостающие элементы, убедившись, что вы не набираете номера повторно.

6 - Начните сначала с шага (2), пока вам нужны строки

Я думаю, что это должно быть настолько случайным, насколько вы можете это сделать, и наверняка будет соответствовать вашим критериям. Кроме того, у вас очень мало тестов на повторяющиеся элементы.

Во-первых, вы всегда можете случайным образом отсортировать список в конце, поэтому давайте не будем беспокоиться о «случайных перестановках» (сложно); и просто беспокойтесь о 1) создании перестановок (легко) и 2) рандомизации их (легко).

Если вам нужны «по-настоящему» случайные группы, вы должны принять тот факт, что рандомизация по своей природе не допускает ограничения «равномерного распределения» результатов — вы можете получить это или вы можете получить набор похожих результатов. Если вы действительно хотите равномерного распределения, сначала сделайте наборы равномерно распределенными, а затем рандомизируйте их как группу.

Вы должны использовать каждый элемент в наборе x равномерно? Из правил не ясно, что я не мог просто сделать следующую интерпретацию:

Обратите внимание на следующее: «во всех списках количество использований каждого элемента одинаково (или максимально близко)».

Основываясь на этом критерии и правиле z ‹ x*, я постулирую, что вы можете просто перечислить все элементы во всех списках. Таким образом, вы автоматически составляете список y из элементов, перечисленных в позиции z. Ваш пример не соответствует приведенному выше правилу так точно, как моя версия. Используя ваш пример x={0,1,2,3} y=6 и z=2, я получаю: 0,1 0,1 0,1 0,1 0,1 0,1

Теперь я не использовал 2 или 3, но вы не сказали, что я должен использовать их все. Если бы мне пришлось использовать их все, и мне не нужно доказывать, что я «насколько возможно близок» к равномерному использованию, я бы просто перечислил все элементы в списках, например: 0,1 2 ,3 0,1 2,3 0,1 2,3

Наконец, предположим, что мне действительно нужно использовать все элементы. Чтобы вычислить, сколько раз может повторяться каждый элемент, я просто беру (y*z)/(количество x). Таким образом, мне не нужно сидеть и беспокоиться о том, как разделить элементы в списке. Если есть остаток или результат меньше 1, то я знаю, что не получу точного количества повторений, поэтому в этих случаях не имеет большого значения пытаться тратить вычислительную энергию, чтобы сделать его идеальным. Я утверждаю, что самый быстрый результат по-прежнему состоит в том, чтобы просто перечислить, как указано выше, и использовать расчет здесь, чтобы показать, почему идеальный результат был или не был достигнут. Причудливый алгоритм для извлечения из этого расчета, сколько позиций будет дубликатами, может быть достигнут, но «это слишком долго, чтобы поместиться здесь на полях».

*Каждый список имеет одинаковое количество элементов z, поэтому невозможно составить списки, в которых z больше x, и при этом соблюдать правило, согласно которому ни один список не может содержать один и тот же элемент дважды. Следовательно, это правило требует, чтобы z не могло быть больше x.

Основываясь на новых деталях в комментариях, решение может быть просто реализацией стандартного алгоритма генерации случайных перестановок. Здесь подробно обсуждаются алгоритмы генерации случайных перестановок:

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

(Из поиска Google: генерация случайных перестановок)

Это работает в Руби:

# 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

Пример использования:

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

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