Python создание массива перестановок с условиями для пула значений на каждом уровне массива

Question

Концептуально я пытаюсь построить массивы возможных перестановок из пула из 10 значений, например, [0-9], где у вас есть выбор 3 для каждого элемента на основе ранжирования. Так, скажем, первый выбранный элемент был 0, тогда следующий возможный пул значений для выбора будет 1,2,3. Если три затем было выбрано [0,3], то следующий выбор будет иметь пул [1,2,4] и так далее. Я хотел бы это для 5 уровней, но, конечно, пытался закодировать решение, которое было произвольным для количества уровней, значений и ограничивающих условий. Цель состоит в том, чтобы все перестановки передавались обратно во вложенном массиве. Я буду использовать этот массив для построения DataFrame для визуализации.

Моей первой попыткой было создание всех перестановок для 10 значений с использованием itertools permutations, а затем удалить из них те, которые не соответствуют моему условию, на основе расстояния от предыдущей записи. Это казалось неэффективным, но мне также было трудно пригладить условие удаления.

edit: я не правильно указал, что процесс выбора всегда начинается с [0,1,2] в качестве первого выбора. Дополнительные варианты добавляются на каждом уровне в соответствии со следующим доступным рангом, вплоть до максимального ранга, скажем, 10. Таким образом, если 2 выбрано на первом уровне, то вместо него появляется «3». [0,1,3] доступны следующие варианты. Если выбрано 1, то на следующем уровне вы можете выбрать [0,3,4]. Это продолжается до тех пор, пока вы не достигнете максимальной длины, скажем, 5 сделанных выборов.

Answer 1

Хорошо, если я правильно понимаю, это процесс, который вы описываете:

Reserve: [3, 4, 5, 6, 7, 8, 9]
Pool: [0, 1, 2]
Chosen: []

Пока у нас еще нет 5 Chosen элементов, удалите любой элемент из Pool и добавить его к выбранной последовательности. Затем удалите элемент first из Reserve и добавьте его в пул. Повторите при необходимости.

Я собираюсь использовать P для размера пула и N для длины выбранной последовательности. Поэтому в этом примере P = 3 и N = 5.

Я все еще немного не уверен, что именно этот процесс вы намереваетесь описать, так как кажется, что 7, 8 и 9 никогда не появятся в выбранной последовательности. , но вы говорите, что пытаетесь найти общее решение, поэтому я предполагаю, что «резерв» на самом деле неограниченного размера.

И ваш вопрос, как мы перечисляем все возможные выбранные последовательности?

Единственный выбор, который вы можете сделать во время этого процесса, - какой элемент извлечь из пула. У вас всегда есть выбор P (= 3). Эти варианты всегда будут разными (так как есть только один из каждого предмета). Пока вы уверены, что не существует двух разных последовательностей вариантов, которые могли бы привести к одной и той же последовательности предметов, теперь вы можете видеть, что у вас есть точно P ^N возможных последовательностей. Единственное, что остается сделать - это преобразовать последовательность индексов выбора в последовательность значений выбора. Вместо того, чтобы делать что-то умное, я предлагаю просто выполнить алгоритм, который мы описали выше.

from itertools import (product, count)

def generate_sequences(pool_size, n):
    for choice_sequence in product(range(pool_size), repeat=n):
        pool = list(range(pool_size))
        sequence = []
        reserve = count(pool_size)
        for choice_index in choice_sequence:
            sequence.append(pool[choice_index])
            pool[choice_index] = next(reserve)
        yield sequence

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

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

---

Здесь не указан вопрос, может ли быть ограничен базовый набор элементов (назовем его размер R). Очевидно, что это должен быть случай, когда R ≥ N, или вы просто не можете выбрать N элементов вообще. Однако, если R

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