#python #permutation
Вопрос:
У меня есть набор списков и список со всеми перестановками набора списков.
mylist = []
mylist.append(['a', 'b', 'c', 'd', 'e'])
mylist.append(['1', '2', '3', '4', '5'])
mylist.append(['f', 'g', 'h', 'i', 'j'])
# Print all permutations
print(list(itertools.product(*mylist)))
Выход
[('a', '1', 'f'), ('a', '1', 'g'), ('a', '1', 'h'), ('a', '1', 'i'), ('a', '1', 'j'), ('a', '2', 'f'), ('a', '2', 'g'), ('a', '2', 'h'), ('a', '2', 'i'), ('a', '2', 'j'), ('a', '3', 'f'), ('a', '3', 'g'), ('a', '3', 'h'), ('a', '3', 'i'), ('a', '3', 'j'), ('a', '4', 'f'), ('a', '4', 'g'), ('a', '4', 'h'), ('a', '4', 'i'), ('a', '4', 'j'), ('a', '5', 'f'), ('a', '5', 'g'), ('a', '5', 'h'), ('a', '5', 'i'), ('a', '5', 'j'), ('b', '1', 'f'), ('b', '1', 'g'), ('b', '1', 'h'), ('b', '1', 'i'), ('b', '1', 'j'), ('b', '2', 'f'), ('b', '2', 'g'), ('b', '2', 'h'), ('b', '2', 'i'), ('b', '2', 'j'), ('b', '3', 'f'), ('b', '3', 'g'), ('b', '3', 'h'), ('b', '3', 'i'), ('b', '3', 'j'), ('b', '4', 'f'), ('b', '4', 'g'), ('b', '4', 'h'), ('b', '4', 'i'), ('b', '4', 'j'), ('b', '5', 'f'), ('b', '5', 'g'), ('b', '5', 'h'), ('b', '5', 'i'), ('b', '5', 'j'), ('c', '1', 'f'), ('c', '1', 'g'), ('c', '1', 'h'), ('c', '1', 'i'), ('c', '1', 'j'), ('c', '2', 'f'), ('c', '2', 'g'), ('c', '2', 'h'), ('c', '2', 'i'), ('c', '2', 'j'), ('c', '3', 'f'), ('c', '3', 'g'), ('c', '3', 'h'), ('c', '3', 'i'), ('c', '3', 'j'), ('c', '4', 'f'), ('c', '4', 'g'), ('c', '4', 'h'), ('c', '4', 'i'), ('c', '4', 'j'), ('c', '5', 'f'), ('c', '5', 'g'), ('c', '5', 'h'), ('c', '5', 'i'), ('c', '5', 'j'), ('d', '1', 'f'), ('d', '1', 'g'), ('d', '1', 'h'), ('d', '1', 'i'), ('d', '1', 'j'), ('d', '2', 'f'), ('d', '2', 'g'), ('d', '2', 'h'), ('d', '2', 'i'), ('d', '2', 'j'), ('d', '3', 'f'), ('d', '3', 'g'), ('d', '3', 'h'), ('d', '3', 'i'), ('d', '3', 'j'), ('d', '4', 'f'), ('d', '4', 'g'), ('d', '4', 'h'), ('d', '4', 'i'), ('d', '4', 'j'), ('d', '5', 'f'), ('d', '5', 'g'), ('d', '5', 'h'), ('d', '5', 'i'), ('d', '5', 'j'), ('e', '1', 'f'), ('e', '1', 'g'), ('e', '1', 'h'), ('e', '1', 'i'), ('e', '1', 'j'), ('e', '2', 'f'), ('e', '2', 'g'), ('e', '2', 'h'), ('e', '2', 'i'), ('e', '2', 'j'), ('e', '3', 'f'), ('e', '3', 'g'), ('e', '3', 'h'), ('e', '3', 'i'), ('e', '3', 'j'), ('e', '4', 'f'), ('e', '4', 'g'), ('e', '4', 'h'), ('e', '4', 'i'), ('e', '4', 'j'), ('e', '5', 'f'), ('e', '5', 'g'), ('e', '5', 'h'), ('e', '5', 'i'), ('e', '5', 'j')]
Из приведенного выше списка я хочу извлечь 10 элементов при следующих условиях:
- Буква а должна появиться 6 раз, буква в-3 раза и буква с-1 раз.
- 5 должны появиться 5 раз (остальное случайно)
- Буква f должна появиться 2 раза, а буква i должна появиться 4 раза (остальное случайно).
Комментарии:
1. Почему бы вам несколько раз не взять один пункт из списка, пока у вас не будет 10 пунктов, удовлетворяющих всем условиям?
2. Или: почему бы вам не сгенерировать все возможные подмножества из 10 элементов списка и не выбрать первое, которое удовлетворяет всем условиям?
3. Все, что вам нужно, это написать функцию-генератор, которая будет принимать списки в качестве аргументов, перебирать произведение этих списков и выводить элементы, удовлетворяющие заданным условиям.
4. Какова здесь более широкая цель/контекст? Если вся ваша проблема имеет именно такую форму (одинаковое количество «а», » 5 » и т. Д.) Для одного и того же списка, решение не так сложно найти с помощью грубой силы. Вы пытаетесь обобщить это на более крупные списки и общие ограничения этой формы? Если это так, то подход к решению SAT начинает казаться многообещающим.
5. Кстати, эти условия не позволяют вам выбирать элемент случайным образом, основываясь только на одном условии. Например, окончательный список должен содержать элемент
('a', 5, ?), и простой алгоритм брутфорса легко не удовлетворит этому. Вероятно, вам следует добавить некоторую информацию о том, как вы хотите это применить.
Ответ №1:
Ваш список перестановок на самом деле содержит только комбинации. Чтобы наложить частоты на выбранные вами 10, вы можете предварительно заполнить части комбинаций требуемыми значениями, а остальные заполнить случайными значениями из оставшихся элементов соответствующего списка. Затем перетасуйте детали перед сборкой затем в 10 комбинаций элементов:
from random import choices,sample
part0 = sample(['a']*6 ['b']*3 choices("cde",k=1) ,10)
part1 = sample(['5']*5 choices("1234",k=5) ,10)
part2 = sample(['f']*2 ['i']*4 choices("ghj",k=4) ,10)
result = list(zip(part0,part1,part2))
Выход:
print(*result,sep="n")
('a', '5', 'i')
('a', '3', 'j')
('b', '5', 'i')
('a', '4', 'g')
('b', '5', 'h')
('b', '5', 'g')
('a', '4', 'f')
('a', '3', 'i')
('a', '1', 'i')
('d', '5', 'f')
____ 4 times 'i', 2 times 'f'
________ 5 times '5'
____________ 6 times 'a', 3 times 'b'
Обратите внимание, что это может привести к дублированию комбинаций. Чтобы обойти это, вы можете поместить 4 строки в цикл, который восстанавливает комбинации до тех пор, пока все они не будут различны (при ваших условиях и выборе из 10 это приводит в среднем к 3,75 попыткам).:
Например:
result = set()
while len(result) != 10:
part0 = sample(['a']*6 ['b']*3 choices("cde",k=1) ,10)
part1 = sample(['5']*5 choices("1234",k=5) ,10)
part2 = sample(['f']*2 ['i']*4 choices("ghj",k=4) ,10)
result = set(zip(part0,part1,part2))
Если вам действительно нужны перестановки, вы можете рандомизировать положение элементов, созданных zip:
...
result = set(map(lambda c:tuple(sample(c,3)),zip(part0,part1,part2)))
что затем приведет к фактическим перестановкам в результате (вероятность наличия дубликатов снижается, и в среднем требуется всего 1,22 попытки).:
('5', 'b', 'i')
('2', 'j', 'a')
('b', 'j', '5')
('g', '2', 'a')
('2', 'f', 'a')
('i', '5', 'a')
('g', '5', 'b')
('i', '1', 'a')
('d', '5', 'f')
('i', '4', 'a')
Комментарии:
1. Да, вы поняли: я сказал «перестановки», но я имел в виду комбинации.