python - 如何生成没有 “moving” 零的列表的排列。在 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á - 它现在可以工作了 - 在获得“肉”的排列后，我进一步获得了“0”位置和 yield 的所有可能组合 每个排列的每组可能的“0位置”的一个排列 非 0 的:

from itertools import permutations, combinations

def permut_with_pivot(sequence, pivot=0):
    pivot_indexes = set()
    seq_len = 0
    def yield_non_pivots():
        nonlocal seq_len
        for i, item in enumerate(sequence):
            if item != pivot:
                yield item
            else:
                pivot_indexes.add(i)
        seq_len = i + 1

    def fill_pivots(permutation):
        for pivot_positions in combinations(range(seq_len), len(pivot_indexes)):
            sequence = iter(permutation)
            yield tuple ((pivot if i in pivot_positions else next(sequence)) for i in range(seq_len))

    for permutation in permutations(yield_non_pivots()):
        for filled_permutation in fill_pivots(permutation):
            yield filled_permutation

(我使用了 Python 的第 3 个“nonlocal”关键字——如果你还在使用 Python 2.7， 你将不得不采取另一种方法，比如让 seq_len 成为一个包含单个项目的列表，然后你可以在内部函数上替换)

我的第二次尝试(有效的实际上是第三次)

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

from itertools import permutations

def non_repeating_permutations(seq):
    seen = set()
    for permutation in permutations(seq):
        hperm = hash(permutation)
        if hperm in seen:
            continue
        seen.add(hperm)
        yield permutation