我如何实现 N 选择 K，允许元素重复，并对具有重复元素的输出进行低优先级

本文关键字：元素 输出 优先级 实现 何实现 选择 许元素 | 更新日期: 2024-11-03 19:12:07

>我需要一种算法来返回来自 n 个元素的所有 K 元素组合，除了对象可以重复。例如，考虑以下对象：A、B、C那么输入和输出的关系如下（Input_Of_Algorithm->输出）：

0 -> A
1 -> B
2 -> C
3 -> A,B
4 -> A,C
5 -> B,C
6 -> A,A
7 -> B,B
8 -> C,C
9 -> A,B,C
10-> A,A,B
11-> A,A,C
12-> A,B,B
13-> A,C,C
14-> B,B,C
15-> B,C,C
16-> A,A,A
17-> B,B,B
18-> C,C,C
19-> A,A,B,C
20-> A,B,B,C
21-> A,B,C,C
.
.
.
and so on ...

关键是 0..2、3..5、6..8 和类似集群内的顺序并不重要。算法的重要部分是具有重复对象的聚类具有较低的优先级。这意味着AAA，BBB，CCC总是在AAB，AAC，ABB，ACC，BBC，BCC之后。此外，AAB，AAC，ABB，ACC，BBC，BCC总是在ABC之后。有什么想法吗，我该如何实现这个算法？

我如何实现 N 选择 K，允许元素重复，并对具有重复元素的输出进行低优先级

此解决方案涉及将几个组合枚举算法粘贴在一起。它的效率相当高。在 Python 3 中：

def integer_partitions(length, total, bound=None, prefix=()):
  if length > 0:
    if bound is None or bound > total:
      bound = total
    for part in range((total - 1 + length) // length, bound + 1):
      yield from integer_partitions(length - 1, total - part,
                                    part, prefix + (part,))
  else:
    yield prefix

内部步骤如下所示。

def strings_from_partitions(letters, partition, prefix=''):
  if letters:
    for part in sorted(set(partition), reverse=True):  # toss duplicates
      residual = list(partition)
      residual.remove(part)
      yield from strings_from_partitions(letters[1:], residual,
                                         prefix + letters[0] * part)
  else:
    yield prefix

把它们放在一起。

def strings(letters):
  total = 1
  while True:
    for partition in integer_partitions(len(letters), total):
      yield from strings_from_partitions(letters, partition)
    total += 1
相关文章：