2

我有以下问题。给定一个包含 n 个元素的集合 S，我需要生成所有可能的重复组合，而不考虑大小 k=1,2,...,m 的顺序。

例子：

n =3
S = {1,2,3}

所有可能的组合是：

k=1: 1,2,3

k=2: 11, 12, 13, 22, 23, 33

k=3: 111, 112, 113, 122, 123, 133, 222, 223, 233, 333.

k=4: 1111, 1112, 1113, ...

...

k=m: ...

显然，步骤 k 的组合可以使用在 k-1 处获得的组合来计算。什么是获得所有 k 的所有组合的最佳算法（伪代码）及其复杂性。

4

2 回答 2

0

我相信回答这个问题最自然的方法是使用递归。

没有真正的“好”方法可以解决这个问题，因为您必须通过每个排列组合，这将为您提供 ^n 运行时间。我在网上找到了这个例子，使用 java 有类似的问题。它以相同的方式工作，但使用字符串而不是整数数组。您应该能够很容易地进行转换。

public class MainClass {
  public static void main(String args[]) {
    permuteString("", "String");
  }

  public static void permuteString(String beginningString, String endingString) {
    if (endingString.length() <= 1)
      System.out.println(beginningString + endingString);
    else
      for (int i = 0; i < endingString.length(); i++) {
        try {
          String newString = endingString.substring(0, i) + endingString.substring(i + 1);

          permuteString(beginningString + endingString.charAt(i), newString);
        } catch (StringIndexOutOfBoundsException exception) {
          exception.printStackTrace();
        }
      }
  }
}

您可以很容易地添加一个 String.Repeat(n) 来重新创建问题的不同大小的组件。

于 2012-09-10T01:04:37.573 回答
0

您可以根据代码中真正需要的内容尝试 2 种方法。由于元素的数量可能会变得非常大，因此方法 1 可能不可行。方法 2 迭代所有可能对您的应用程序足够的解决方案。

方法一：递归生成所有组合

您从所有元素的有序集合开始（在您的示例 1..n 中）。该集合包含长度为 1 的所有组合。

然后创建一个包含长度为 1 的所有组合的新集合。您可以通过获取前一个集合的元素并附加所有可能大于或等于最后一个元素的其他元素来填充它。例如：如果您从集合中取出元素 1，则将其附加 1..n 以获取元素 11、12、13、...1n。如果您采用元素 3，那么您只需将其附加 3..n 即可获得元素 33,34,...3n。您重复该过程 k 次以获得长度为 k 的序列。

方法2：迭代组合

这些集合可能会变得非常大，您可以迭代所有解决方案。假设您需要长度为 k 的所有组合。

  1. 创建一个长度为 k 的向量并用第一个元素的 k 倍填充它（k=4 时为 1111）

  2. 将最后一个元素替换为其后继元素以创建新组合 (1112)。如果最后一个元素已经是集合 (n) 中的最大元素，则将其设置为第一个元素并增加倒数第二个元素。对于一组 2 个元素（1 和 2），1112 的后继将是 1121。递归地执行此添加。

这将遍历所有长度为 k 的组合。如果您还想要较低长度的组合，您可以通过查看向量的第一部分来找到它们。在示例中，它从 111 开始，当最后一个元素再次变为 1 时，找到长度 (k-1) 的新组合 (=112)

于 2012-09-10T22:39:14.380 回答