如何在不"移动"零的情况下生成列表的排列.在Python中

Question

使用该itertools工具,我有给定的数字列表的所有可能的排列,但如果列表如下:

List=[0,0,0,0,3,6,0,0,5,0,0]

itertools 并不"知道"迭代零是浪费的工作,例如以下迭代将出现在结果中:

List=[0,3,0,0,0,6,0,0,5,0,0]

List=[0,3,0,0,0,6,0,0,5,0,0]

它们是相同的但itertools只是取第一个零(例如)并将其移动到列表中的第四个位置,反之亦然.

问题是:我如何只迭代一些选定的数字并单独留下其他如零？它可以有或没有itertools.

Answer 1

Voil\xc3\xa1 - 现在可以工作了 - 在获得“肉”上的排列后，我进一步获得“0”位置的所有可能组合，并为每个排列的每个可能的“0位置”集合产生\none排列\n非 0 的：

\n\n

from itertools import permutations, combinations\n\ndef permut_with_pivot(sequence, pivot=0):\n    pivot_indexes = set()\n    seq_len = 0\n    def yield_non_pivots():\n        nonlocal seq_len\n        for i, item in enumerate(sequence):\n            if item != pivot:\n                yield item\n            else:\n                pivot_indexes.add(i)\n        seq_len = i + 1\n\n    def fill_pivots(permutation):\n        for pivot_positions in combinations(range(seq_len), len(pivot_indexes)):\n            sequence = iter(permutation)\n            yield tuple ((pivot if i in pivot_positions else next(sequence)) for i in range(seq_len))\n\n    for permutation in permutations(yield_non_pivots()):\n        for filled_permutation in fill_pivots(permutation):\n            yield filled_permutation\n

\n\n

（我已经使用了 Python 的 3 个“nonlocal”关键字 - 如果您仍在使用 Python 2.7，您将不得不采取另一种方法，例如创建seq_len一个包含单个项目的列表，然后您可以将其替换为内部函数）

\n\n

我的第二次尝试（有效的实际上是第三次）

\n\n

这是一种幼稚的方法，只保留已经“看到”的排列的缓存 - 它节省了对每个排列所做的工作，但不节省生成所有可能的排列的工作：

\n\n

from itertools import permutations\n\ndef non_repeating_permutations(seq):\n    seen = set()\n    for permutation in permutations(seq):\n        hperm = hash(permutation)\n        if hperm in seen:\n            continue\n        seen.add(hperm)\n        yield permutation\n

\n