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

Question

Мне нужно составить случайный список перестановок. Элементы могут быть любыми, но предполагают, что они являются целыми числами от 0 до x-1. Я хочу сделать y списков, каждый из которых содержит z элементов. Правила заключаются в том, что ни один список не может содержать один и тот же элемент дважды, и что во всех списках число раз, когда каждый элемент используется одинаково (или максимально близко). Например, если мои элементы 0,1,2,3, y равно 6, а z равно 2, то одно из возможных решений:

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

Каждая строка имеет только уникальные элементы, и ни один элемент не использовался более 3 раз. Если бы у было 7, то 2 элемента использовались бы 4 раза, остальные 3.

Answer 1

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

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

Answer 3

Это работает в 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

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

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 4

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

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

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

Answer 5

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

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

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

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

Исходя из этого критерия и правила z

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

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

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

Answer 6

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

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

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

4 - повторите (2), пока у вас есть номера в списке

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

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

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