具有重复项的列表的排列

Question

我正在尝试制作一个整数分区生成器，其中顺序重要并且所有部分均小于k（例如，如果k = 10且n = 100，则[5, 95]无效，因为95> = 10 ）。我已经从this website复制了一个生成器（并对其进行了修改），其中order无关紧要，现在正在尝试制作一个通过每个分区排列的生成器。

我的主要问题是创建一个接受列表（分区）并有效输出该列表排列的函数。我已经通过使用itertools排列实现了一个低效的版本，其中包括：

set(itertools.permutations(partition))

这是非常低效的。当partition具有重复项时，将迭代所有重复项。例如，当partition = [1, 1, 1, 1, 1, 1, 1]时，itertools将遍历所有7个！ = 5040个分区，只有一个唯一的排列。

我该如何提高效率？我将考虑n的值在10 ^ 10或更高的数量级，因此效率非常重要。

如果有帮助，请注意分区的所有部分都小于k。

编辑：我想我（主要是）知道了。不过有一个错误。

def helper(current, index, available, freqList):
    if index >= len(freqList) or available == []:
        yield current
        return
    else:
        if freqList[index] != 0:
            for combo in itertools.combinations(available, freqList[index]):
                yield helper(new(current, index, combo), index + 1, delete(available, combo), freqList)
        else:
            yield helper(current, index + 1, available, freqList)
def permutations(partition, k):
    #returns permutations of partition

    length = len(partition)
    freqList = [partition.count(i) for i in range(k+1)]

    available = [i for i in range(length)]
    return helper([0]*length, 1, available, freqList)

[delete(L, T)返回L的副本，但不包含T中的元素。new(L, i, T)返回L的副本，但T中的所有索引均被i取代。

这样做基本上是遍历每个数字可以到达的位置的组合。假设分区中有10 1s，5 2s和7 3s。迭代1可能经过的空间。然后，假设1占用其他空间，它将遍历2可以经过的空间。最后，在1和2占据其空间的情况下，迭代3可以经过的空间。

此代码中有错误。由于某些原因，permutations返回生成器的生成器...生成器的列表嵌套m次，其中m是partition中的最大元素。例如，如果partition = [1, 1, 1, 3, 3, 3]。我必须做

for gen1 in permutations(partition, k):
    for gen2 in gen1:
        for gen3 in gen2:
            for partition in gen3:
                #something else

我不知道如何解决这个问题，但我认为这是一个问题。修复此问题将对您有所帮助。

Answer 1

一种方法是获取Heap's algorithm并稍加修改以不交换相同的元素：

def _unique_permutations(seq, k):
  if k == 1:
    yield seq
  else:
    yield from _unique_permutations(seq, k - 1)
    for i in range(k - 1):
      idx = 0 if k % 2 else i
      if seq[idx] != seq[k - 1]:  # a modification to not swap identical elements
        seq[idx], seq[k - 1] = seq[k - 1], seq[idx]
        yield from _unique_permutations(seq, k - 1)

def unique_permutations(seq):
  yield from _unique_permutations(seq[:], len(seq))

for perm in unique_permutations([1, 1, 2, 2, 2]):
  print(perm)