0

我正在处理覆盖数组,需要一些关于生成集(给定某些参数)的指导,以计算数组是否是覆盖数组。

我有两个输入来解析 -tv整数。v包含数组中唯一符号(整数)的数量。可以假定这是一组任何整数。整数t代表我想从这个集合中抓取的符号的长度。

因此,例如,假设v = 3{0,1,2}符号,并且t = 2。然后我将生成组合{ (0,0), (0,1), (0,2), (1,0), (1,1), (1,2), ..., (2,2) }。一般来说,我会生成v^t组合。我想知道是否有比我一直在使用的算法更好的算法,它的计算成本可能更低。

基本上我正在做的是在不同的基础上进行计数。因此,例如,在上面的示例中,我最初从一个t空间分配为 0 的数组开始。每次传递时,我都会递增最低有效位并将其转换为一个集合或其他一些数据结构来保存我的组合。一旦最低有效位溢出,我将其设置为 0 并递增下一个有效位。这一切都在不同的基础上计算。所以我最终会得到t=2and的以下输出v=3

00
01
02
10
11
12
20
21
22

我最大的问题是——这是一个排列还是组合问题?我对两者之间的细节有点模糊。我相信这是排列,因为重复发生了,因为顺序无关紧要。

同样,这个算法是否足够体面(可能)处理一个大的v?我得到的参数t是 2 或 3,但v未知。是否有一种众所周知的算法来计算符号的长度t集?v作为参考,我正在使用 C++ 来执行此操作。

4

1 回答 1

2

你正在处理variations with repetitions。在 SO 和整个 Internet 上都有很多示例。至于你的算法,它的复杂性至少是输出的大小——你已经指出了——它将是 Ω(v^t)。如果按位操作对您有用(即适合其余的实现),那么是的,您可以这样做。

于 2013-02-12T23:05:00.487 回答