В общей сложности n выберите k возможных комбинаций, соответствующих вашим критериям, с n = length и k = com_len. n choose k оценивается как n! / (k! * (n - k)!). Если вы генерируете все различные возможности, каждое из значений n появляется (n - 1)! / ((k - 1)! * (n - k)!) раз (https://math.stackexchange.com/q/26619/295281). Вы должны быть в состоянии решить эту проблему, предполагая, что z <= (n - 1)! / ((k - 1)! * (n - k)!), где z = counter_expected.
Для вашего примера:
n = 256k = 3 z = 100 <= 32385
Одним из распространенных способов генерации комбинаций в целом является пошаговое выполнение k битов через логический массив длины n, всегда увеличивая наименьший возможный бит. Всякий раз, когда увеличивается старший бит, все нижние биты сбрасываются в исходное положение. Вот пример последовательности:
0 0 0 0 3 2 1
0 0 0 3 0 2 1
0 0 0 3 2 0 1
0 0 0 3 2 1 0
0 0 3 0 0 2 1
...
3 2 0 0 1 0 0
3 2 0 1 0 0 0
3 2 1 0 0 0 0
Я пометил позиции, чтобы вы могли видеть, что, если значения отсортированы для начала, комбинации всегда будут выходить отсортированными. Имейте в виду, что вы можете реализовать это как массив n логических значений или k индексов. Оба имеют свои преимущества и недостатки.
Для вашего конкретного случая использования есть поворот. Вы не используете немного, если счет превысил определенное количество. Есть несколько способов пройти через биты, но все они сводятся к наличию счетного массива размером n.
Если n * z кратно k, вы автоматически сможете чтобы получить точные подсчеты во всех корзинах. Ни n, ни z сами по себе не должны быть кратны k. Однако, если это не так, у вас неизбежно будут переполнение или переполнение. Интуитивно понятно, что вы хотите сгенерировать цель из n * z общих значений, k за раз. Совершенно очевидно, что для того, чтобы это стало возможным, нужно умножить число на последующие.
Вы можете иметь два типа критериев выхода. Учитывая общее накопленное количество всех битов, s,
s >= n * z: все биты имеют счет не менее z. Максимум k - 1 битов имеют счетчик z + 1. s > n * z - k: все биты имеют счетчик z, кроме максимум k - 1 битов, поэтому добавление еще одной комбинации приведет к условию 1.
Одним из последних вариантов дизайна, который необходимо обсудить, является порядок перемещения битов. Поскольку генерация серии комбинаций исчерпывает ячейку, я хотел бы иметь возможность сохранять накопленные исчерпывающие ячейки последовательно, в предсказуемом порядке на одной стороне корзины. Это удалит много проверок из алгоритма. Таким образом, вместо увеличения минимально возможного бита, я буду увеличивать максимальный возможный бит и увеличивать тот, который находится ниже, всякий раз, когда он сбрасывается. В этом случае исчерпанные сегменты всегда будут самыми младшими битами.
Итак, давайте, наконец, прекратим делать недоказанные математически звучащие утверждения и покажем реализацию:
def generate_combos(n, k, z):
full_locs = np.arange(k + 1, dtype=np.uint)
full_locs[k] = n # makes partial vectorization easier
locs = full_locs[:k] # bit indices
counts = np.zeros(n, dtype=np.uint) # counter buckets
values = np.arange(n, dtype=np.uint) # values
min_index = 0 # index of lowest non-exhausted bin
for _ in range((n * z) // k):
counts[locs] += 1
yield values[locs]
if counts[min_index] == z:
# if lowest bin filled, shift and reset
min_index += np.argmax(counts[min_index:] < z)
locs[:] = min_index + np.arange(k)
else:
# otherwise, increment highest available counter
i = np.flatnonzero(np.diff(full_locs) > 1)
if i.size:
i = i[-1]
locs[i] += 1
# reset the remainder
locs[i + 1:] = locs[i] + np.arange(1, k - i)
else:
break
Используется условие 2. Если Вы хотите условие 1, добавьте следующие строки после:
if counters[-1] < z:
yield values[-k:]
Изменение l oop на что-то вроде for _ in range(-((n * z) // -k)): (любезность { ссылка }) не поможет, потому что счетчики не предназначены для его обработки.
Вот ссылка IDEOne , показывающая первые сто элементов generate_combos(256, 3, 10):
[0 1 2]
[0 1 3]
[0 1 4]
[0 1 5]
[0 1 6]
[0 1 7]
[0 1 8]
[0 1 9]
[ 0 1 10]
[ 0 1 11]
[2 3 4]
[2 3 5]
[2 3 6]
[2 3 7]
[2 3 8]
[2 3 9]
[ 2 3 10]
[ 2 3 11]
[ 2 3 12]
[4 5 6]
[4 5 7]
[4 5 8]
[4 5 9]
[ 4 5 10]
[ 4 5 11]
[ 4 5 12]
[ 4 5 13]
[6 7 8]
[6 7 9]
[ 6 7 10]
[ 6 7 11]
[ 6 7 12]
[ 6 7 13]
[ 6 7 14]
[ 8 9 10]
[ 8 9 11]
[ 8 9 12]
[ 8 9 13]
[ 8 9 14]
[ 8 9 15]
[10 11 12]
[10 11 13]
[10 11 14]
[10 11 15]
[10 11 16]
[12 13 14]
[12 13 15]
[12 13 16]
[12 13 17]
[12 13 18]
[13 14 15]
[14 15 16]
[14 15 17]
[14 15 18]
[14 15 19]
[14 15 20]
[15 16 17]
[16 17 18]
[16 17 19]
[16 17 20]
[16 17 21]
[16 17 22]
[16 17 23]
[17 18 19]
[18 19 20]
[18 19 21]
[18 19 22]
[18 19 23]
[18 19 24]
[18 19 25]
[19 20 21]
[20 21 22]
[20 21 23]
[20 21 24]
[20 21 25]
[20 21 26]
[20 21 27]
[21 22 23]
[22 23 24]
[22 23 25]
[22 23 26]
[22 23 27]
[22 23 28]
[22 23 29]
[24 25 26]
[24 25 27]
[24 25 28]
[24 25 29]
[24 25 30]
[24 25 31]
[24 25 32]
[26 27 28]
[26 27 29]
[26 27 30]
[26 27 31]
[26 27 32]
[26 27 33]
[26 27 34]
[28 29 30]
[28 29 31]
...
Обратите внимание, что после первые 10 элементов, 0 и 1, появились 10 раз. 2 и 3 появились один раз, поэтому они привыкли только после еще 9 итераций и т. Д.