我正在使用Python 3,尝试找到一种方法来获取列表的所有排列并强制执行一些限制。
例如,我有一个列表L=[1, 2, 3, 4, 5, 6, 7]
我想找到所有排列。但是,我的限制条件是:
- 1应始终出现在2之前。
- 3应出现在4之前,而4应出现在5之前。
- 最后,6应出现在7之前。
当然,我可以生成所有排列,并忽略那些不符合这些约束条件的排列,但我认为这不是高效的做法。
我正在使用Python 3,尝试找到一种方法来获取列表的所有排列并强制执行一些限制。
例如,我有一个列表L=[1, 2, 3, 4, 5, 6, 7]
我想找到所有排列。但是,我的限制条件是:
当然,我可以生成所有排列,并忽略那些不符合这些约束条件的排列,但我认为这不是高效的做法。
import itertools
groups = [(1,2),(3,4,5),(6,7)]
groupdxs = [i for i, group in enumerate(groups) for j in range(len(group))]
old_combo = []
for dx_combo in itertools.permutations(groupdxs):
if dx_combo <= old_combo: # as simple filter
continue
old_combo = dx_combo
iters = [iter(group) for group in groups]
print [next(iters[i]) for i in dx_combo]
groupdxs
。) 这里有一篇论文详细说明了一个O(1)算法。permutations
函数的第二个参数。这很整洁! - Katriellist(itertools.permutations((0,0))
-> [(0, 0), (0, 0)]
,即itertools.permutations()
在任何情况下都会生成N!
个排列。 - jfsdef partial_permutations(*groups):
groups = list(filter(None, groups)) # remove empties.
# Since we iterate over 'groups' twice, we need to
# make an explicit copy for 3.x for this approach to work.
if not groups:
yield []
return
for group in groups:
for pp in partial_permutations(*(
g[1:] if g == group else g
for g in groups
)):
yield [group[0]] + pp
list(partial_permutations((1,2),(3,4,5),(6,7)))
返回[]
)。 - andrew cooke一种方法是采用其中一种交换算法,当您要将元素交换到其最终位置时,请检查它是否按正确顺序排列。下面的代码就是这样做的。
但首先让我展示它的用法:
L = [1, 2, 3, 4, 5, 6, 7]
constraints = [[1, 2], [3, 4, 5], [6, 7]]
A = list(p[:] for p in constrained_permutations(L, constraints)) # copy the permutation if you want to keep it
print(len(A))
print(["".join(map(str, p)) for p in A[:50]])
以及输出:
210
['1234567', '1234657', '1234675', '1236457', '1236475', '1236745', '1263457', '1263475', '1263745', '1267345', '1324567', '1324657', '1324675', '1326457', '1326475', '1326745', '1342567', '1342657', '1342675', '1345267', '1345627', '1345672', '1346527', '1346572', '1346257', '1346275', '1346725', '1346752', '1364527', '1364572', '1364257', '1364275', '1364725', '1364752', '1362457', '1362475', '1362745', '1367245', '1367425', '1367452', '1634527', '1634572', '1634257', '1634275', '1634725', '1634752', '1632457', '1632475', '1632745', '1637245']
但现在是代码:
def _permute(L, nexts, numbers, begin, end):
if end == begin + 1:
yield L
else:
for i in range(begin, end):
c = L[i]
if nexts[c][0] == numbers[c]:
nexts[c][0] += 1
L[begin], L[i] = L[i], L[begin]
for p in _permute(L, nexts, numbers, begin + 1, end):
yield p
L[begin], L[i] = L[i], L[begin]
nexts[c][0] -= 1
def constrained_permutations(L, constraints):
# warning: assumes that L has unique, hashable elements
# constraints is a list of constraints, where each constraint is a list of elements which should appear in the permatation in that order
# warning: constraints may not overlap!
nexts = dict((a, [0]) for a in L)
numbers = dict.fromkeys(L, 0) # number of each element in its constraint
for constraint in constraints:
for i, pos in enumerate(constraint):
nexts[pos] = nexts[constraint[0]]
numbers[pos] = i
for p in _permute(L, nexts, numbers, 0, len(L)):
yield p
[3 1 2 ...]
是合法的,但[1 3 2 ...]
不合法(“1 应该始终在 2 前面”)。 - mathematical.coffee