Pythonic способ создать массив с записями, уникальными для строки и столбца

Question

У меня есть несколько выборок, и я хочу выбрать случайное подмножество из образцов определенной длины и повторять этот процесс до тех пор, пока каждая выборка не произойдет 3 раза, ни одна выборка не будет встречаться дважды в данной строке.

Например,:

samples=range(12)
l=6
repeats=3

Я ожидаю 6 рядов из 6 образцов.Я хотел бы иметь что-то вроде:

[1, 2, 11, 7, 0, 3]
[2, 5, 0, 7, 10, 3]
[11, 0, 8, 7, 6, 1]
[4, 11, 5, 9, 3, 6]
[4, 9, 8, 1, 10, 2]
[9, 5, 6, 4, 8, 10]

Я попробовал следующее, но это работало только в одном случае (случайно), когда образцы были выбраны одинаково, я обычно получаю

ValueError: sample larger than population

Код:

import random
samples=range(12)
measured={key:0 for key in samples}
while len(samples)>0:
    sample=random.sample(samples,6)
    print sample
    for s in sample:
        measured[s]+=1
        if measured[s]==3:
            samples.remove(s)

Мне было интересно, есть ли способ настроить numpy.random.choice или itertools.permutations, но они не сработали из-за указанных выше ограничений.

Есть липример того, как я пропускаю или мне нужно работать с вложенными циклами / ifs?

Answer 1

Возможно, я неправильно понимаю, но исходя из вашего названия, вы на самом деле хотите, чтобы сетка чисел из samples удовлетворяла следующим условиям:

1. Записи уникальны для каждой строки и столбца
2. Каждый элемент в samples повторяется самое большее repeats раз

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

Одним из возможных решений является заполнение вашей сетки по одному элементу за раз, переходя от первого элемента (вверху слева) к последнему (внизу справа). В каждом месте вы случайным образом выбираете из набора «допустимых» значений, которые будут значениями, которые еще не были выбраны для этой строки или столбца, и теми, которые еще не были выбраны repeats раз.

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

Вот одна реализация, которую я придумал, используя numpy:

import numpy as np

samples=range(12)
l=6
repeats=3

def try_make_grid(samples, l, repeats, max_tries=10):
    try_number = 0
    while(try_number < max_tries):
        try:
            # initialize lxl grid to nan
            grid = np.zeros((l, l))*np.nan

            counts = {s: 0 for s in samples}  # counts of each sample
            count_exhausted = set()           # which samples have been exhausted
            for i in range(l):
                for j in range(l):
                    # can't use values that already happened in this row or column
                    invalid_values = set(np.concatenate([grid[:,j], grid[i,:]]))
                    valid_values = [
                        v for v in samples if v not in invalid_values|count_exhausted
                    ]
                    this_choice = np.random.choice(a=valid_values)
                    grid[i,j] = this_choice

                    # update the count and check to see if this_choice is now exhausted
                    counts[this_choice] += 1
                    if counts[this_choice] >= repeats:
                        count_exhausted.add(this_choice)
            print("Successful on try number %d" % try_number)
            return grid
        except:
            try_number += 1
    print("Unsuccessful")

Пример сетки:

np.random.seed(42)
grid = try_make_grid(samples, l, repeats)
#Successful on try number 6
print(grid)
#[[10.  5.  8. 11.  3.  0.]
# [ 0. 11.  4.  8.  2.  5.]
# [ 1.  6.  0.  2.  7.  3.]
# [ 3.  2.  7. 10. 11.  9.]
# [ 4.  1.  9.  6.  8.  7.]
# [ 6.  9. 10.  5.  1.  4.]]

Как видите, каждая строка и столбец уникальны, и каждое значение было выбрано не более repeats раз (в этом случае все они выбраны ровно repeats раз).

from collections import Counter
print(Counter(grid.ravel()))
#Counter({10.0: 3,
#         5.0: 3,
#         8.0: 3,
#         11.0: 3,
#         3.0: 3,
#         0.0: 3,
#         4.0: 3,
#         2.0: 3,
#         1.0: 3,
#         6.0: 3,
#         7.0: 3,
#         9.0: 3})

Answer 2

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

from collections import Counter
from itertools import chain
from pprint import pprint
import random


def pick_subset(population, length, repeat, max_iterations=1000000):
    iterations = 0

    while iterations < max_iterations:
        # Get subset where every sample value occurrs at exactly "repeat" times.
        while iterations < max_iterations:
            iterations += 1
            subset = [random.sample(population, length) for i in range(length)]
            measure = Counter(chain.from_iterable(subset))
            if all((iterations == repeat for iterations in measure.values())):
                break

        # Check whether there are no more than 2 repeats in per row.
        if all((all((iterations < 2 for iterations in Counter(row).values()))
                   for row in subset)):
            break

    if iterations >= max_iterations:
        raise RuntimeError("Couldn't match criteria after {:,d}".format(iterations))
    else:
        print('Succeeded after {:,d} iterations'.format(iterations))
        return subset


samples = range(12)
length = 6
repeat = 3

subset = pick_subset(samples, length, repeat)

print('')
print('Selected subset:')
pprint(subset)

# Show that each sample occurs exactly three times.
freq_counts = Counter(chain.from_iterable(subset))
print('')
print('Overall sample frequency counts:')
print(', '.join(
        '{:2d}: {:d}'.format(sample, cnt) for sample, cnt in freq_counts.items()))


# Show that no sample occurs more than twice in a each row.
print('')
print('Sample frequency counts per row:')
for i, row in enumerate(subset):
    freq_counts = Counter(row)
    print('  row[{}]: {}'.format(i, ', '.join(
            '{:2d}: {:d}'.format(sample, cnt) for sample, cnt in freq_counts.items())))

Пример вывода:

Succeeded after 123,847 iterations

Selected subset:
[[4, 9, 10, 2, 5, 7],
 [5, 8, 6, 0, 11, 1],
 [1, 8, 3, 10, 7, 0],
 [7, 3, 2, 4, 11, 9],
 [0, 10, 11, 6, 1, 2],
 [8, 3, 9, 4, 6, 5]]

Overall sample frequency counts:
 0: 3,  1: 3,  2: 3,  3: 3,  4: 3,  5: 3,  6: 3,  7: 3,  8: 3,  9: 3, 10: 3, 11: 3

Sample frequency counts per row:
  row[0]:  2: 1,  4: 1,  5: 1,  7: 1,  9: 1, 10: 1
  row[1]:  0: 1,  1: 1,  5: 1,  6: 1,  8: 1, 11: 1
  row[2]:  0: 1,  1: 1,  3: 1,  7: 1,  8: 1, 10: 1
  row[3]:  2: 1,  3: 1,  4: 1,  7: 1,  9: 1, 11: 1
  row[4]:  0: 1,  1: 1,  2: 1,  6: 1, 10: 1, 11: 1
  row[5]:  3: 1,  4: 1,  5: 1,  6: 1,  8: 1,  9: 1